I'm implementing a Miller Rabin primality test using JavaScript BigInts.
The basic algorithm is no problem - I have that done, but it requires a random number in the range 0 to (number being tested-3). I can't use Math.random() and scale since I'm using BigInt.
This doesn't need to be cryptographically secure, just random enough, so I've opted for generating a string of randomly selected hex digits and converting that to a BigInt.
Here's the code:
function getRandomBigint(lower, upper) {
// Convert to hex strings so that we know how many digits to generate
let hexDigits = new Array(upper.toString(16).length).fill('');
let rand;
let newDigits;
do {
// Fill the array with random hex digits and convert to a BigInt
newDigits = hexDigits.map(()=>Math.floor(Math.random()*16).toString(16));
rand = BigInt('0x'+newDigits.join(''));
} while (rand < lower || rand > upper);
return rand;
}
The problem here is that the generated number could be out of range. This function handles that (badly) by iterating until it gets a number in range. Obviously, that could potentially take a very long time. In practice it has never iterated more than a couple of dozen times before delivering a number, but the nature of randomness means that the problem is 'out there' waiting to bite me!
I could scale or truncate the result to get it in range, rather than iterating, but I am concerned that this would affect the randomness. I already have some evidence that this is not as random as it might be, but that might not matter in this application.
So, two questions:
This is a JavaScript-only project - no libraries, please.
The Miller Rabin test is a probabilistic1 test. That is, it is deterministic for establishing that a number is not prime, but a prime indication is only that - an indication that a number might be prime.
The reason is that certain bases used in the test can result in a prime indication, even when the target number is not prime. The use of a random number as a base in the test allows for the test to be run repeatedly with a different base each time, thus increasing the probability that the result correctly indicates prime or not prime2.
Thus, the random numbers selected must just be less than the number being tested. There is no requirement for them to be selected from the complete range.
With this in mind I now have this:
function getRandomBigInt(upper) {
let maxInt = BigInt(Number.MAX_SAFE_INTEGER);
if (upper <= maxInt) {
return BigInt((Math.floor(Math.random()*Number(upper))));
} else {
return BigInt((Math.floor(Math.random()*Number.MAX_SAFE_INTEGER)));
}
}
9007199254740991 (Number.MAX_SAFE_INTEGER) should provide a sufficiently large range of numbers for this purpose. It works with my Miller-Rabin implementation as far as I have tested it so far.
1 Testing numbers up to 3,317,044,064,679,887,385,961,981 against a short specific list of bases will yield a definitive prime/not prime result.
2 For non-deterministic prime results it is still necessary to perform a deterministic test (such as trial division) to confirm.
A way to get random number in a range is
lower + rand() % (upper - lower)
rand() is any function that returns a random number larger than (upper - lower). The math can be done with Integer or Bigint.
function rand16() {
// 0 .. 2^16-1
return BigInt(Math.floor(Math.random()*65536));
}
function rand() {
// -2^63 .. 2^63-1
return BigInt( (((rand16() * 65536) + rand16())* 65536 + rand16()) * 65536 + rand16() );
}