BigInt random numbers

Up a level : Algebra and Arithmetic
Previous page : RSA cryptosystem

In this page you can generate BigInt random numbers in between two given values, a, b including the given values, and check if large numbers are prime.

Generator 1 Generates a random big number between two numbers.
Generator 2 Generates a random number with a selected number of decimal digits or bits. Can also be used to check if a number is a prime number.

Generator 1

It first calculates the difference c=b-a, then it splits the value c in groups of 10 digits, starting from the most significant figure. It will then loop through c in the following way:

Let the result be “”.
Get the most significant part not yet handled, say f.
Generate a random integer between 0 and f, inclusive, say r.
If r=f, then set f to the next 10 digit part of c, else set f=10000000000. If so, use that f for all following part, except possibly the last where f=10^number of digits left.
Concatenate r to the result.
Repat from 3 until all parts of c is handled.
Finally, add back a.

This is the code. It is a metod inside an object.

randBigBetween: function (a, b) {
    let c = b - a;
    let str = c.toString();
    let length = str.length;
    let turns = Math.floor((length - 1) / 10) + 1; // The number of parts
    // that we will loop through. It will split the string in as many
    // 10 digit part as possible + possibly one part with less than 10 digits.
    let result = '';
    let start = 0; // These two are used to index the input string.
    let end = 10;
    let extract = true; // This is set if the factors are to be extracted from
    // the string.
    let num = 0; // This will be the randomly generated integer part.
    let factor = 0; // The factor used in the random part generator.
    for (let i = 0; i < turns; i++) {
      if (extract) {
        factor = Number(str.slice(start, end)) + 1;
        num = Math.floor(Math.random() * factor);
        if (num !== factor) {
          // In this case the rest of the number
          extract = false; // can contain any digits.
          factor = 10000000000;
        }
      } else {
        num = Math.floor(Math.random() * factor);
      }
      result += num;
      start = end;
      end += 10;
      if (end > length) {
        end = length;
        factor = 10 ** (end - start);
      }
    }
    return BigInt(result) + a;
  }

randBigBetween: function (a, b) {

let c = b - a;

let str = c.toString();

let length = str.length;

let turns = Math.floor((length - 1) / 10) + 1; // The number of parts

// that we will loop through. It will split the string in as many

// 10 digit part as possible + possibly one part with less than 10 digits.

let result = '';

let start = 0; // These two are used to index the input string.

let end = 10;

let extract = true; // This is set if the factors are to be extracted from

// the string.

let num = 0; // This will be the randomly generated integer part.

let factor = 0; // The factor used in the random part generator.

for (let i = 0; i < turns; i++) {

if (extract) {

factor = Number(str.slice(start, end)) + 1;

num = Math.floor(Math.random() * factor);

if (num !== factor) {

// In this case the rest of the number

extract = false; // can contain any digits.

factor = 10000000000;

}

} else {

num = Math.floor(Math.random() * factor);

}

result += num;

start = end;

end += 10;

if (end > length) {

end = length;

factor = 10 ** (end - start);

}

return BigInt(result) + a;

}

Generator 2

This is using the same method to generate a number as generator 1. It then checks if it is a prime number, if not it steps to the next likely prime number, and so on. For small numbers it does an exact test, for larger it uses 33 iterations of the Miller–Rabin test . That means that the risk for a false positive is in the order of 1/4³³, or 1.355·10^-20. In other worlds, virtually in existent.

You can store the generated random primes to use in the RSA-algorithm.

Up a level : Algebra and Arithmetic
Previous page : RSA cryptosystem

Last modified: Oct 29, 2023 @ 19:09