tl;dr How do you get an extremely large 80 digit BigInt exact prime, not a "probable" prime? It appears the code I have found and attached below only gives you a "probable" prime. Now the question is how to then figure out if it is an "exact" prime (i.e. not probable, but actual)?
I was led to this BigInt "random value between" code for generating a random BigInt between a min and max, and this BigInt prime number test code, which I've pasted together below. I then added a simple while loop to generate a bigint of a certain magnitude, and check for prime (and in my case also that the prime is p ≡ 3 mod 4 (prime % 4 === 3):
let i = 0n
while (i < 1000000000n) {
let n = randomBigIntBetween(
1000000000100000000010000000001000000000100000000010000000001000000000n,
10000000001000000000100000000010000000001000000000100000000010000000001000000000n
)
if (isPrime(n) && n % 4n === 3n) {
console.log(String(n))
}
i++
}
function randomBigIntBetween(minInclusive, maxExclusive) {
var maxInclusive = (maxExclusive - minInclusive) - BigInt(1)
var x = BigInt(1)
var y = BigInt(0)
while(true) {
x = x * BigInt(2)
var randomBit = BigInt(Math.random()<0.5 ? 1 : 0)
y = y * BigInt(2) + randomBit
if(x > maxInclusive) {
if (y <= maxInclusive) { return y + minInclusive }
// Rejection
x = x - maxInclusive - BigInt(1)
y = y - maxInclusive - BigInt(1)
}
}
}
// Javascript program Miller-Rabin primality test
// based on JavaScript code found at https://www.geeksforgeeks.org/primality-test-set-3-miller-rabin/
// Utility function to do
// modular exponentiation.
// It returns (x^y) % p
function power(x, y, p)
{
// Initialize result
// (JML- all literal integers converted to use n suffix denoting BigInt)
let res = 1n;
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0n)
{
// If y is odd, multiply
// x with result
if (y & 1n)
res = (res*x) % p;
// y must be even now
y = y/2n; // (JML- original code used a shift operator, but division is clearer)
x = (x*x) % p;
}
return res;
}
// This function is called
// for all k trials. It returns
// false if n is composite and
// returns false if n is
// probably prime. d is an odd
// number such that d*2<sup>r</sup> = n-1
// for some r >= 1
function millerTest(d, n)
{
// (JML- all literal integers converted to use n suffix denoting BigInt)
// Pick a random number in [2..n-2]
// Corner cases make sure that n > 4
/*
JML- I can't mix the Number returned by Math.random with
operations involving BigInt. The workaround is to create a random integer
with precision 6 and convert it to a BigInt.
*/
const r = BigInt(Math.floor(Math.random() * 100_000))
// JML- now I have to divide by the multiplier used above (BigInt version)
const y = r*(n-2n)/100_000n
let a = 2n + y % (n - 4n);
// Compute a^d % n
let x = power(a, d, n);
if (x == 1n || x == n-1n)
return true;
// Keep squaring x while one
// of the following doesn't
// happen
// (i) d does not reach n-1
// (ii) (x^2) % n is not 1
// (iii) (x^2) % n is not n-1
while (d != n-1n)
{
x = (x * x) % n;
d *= 2n;
if (x == 1n)
return false;
if (x == n-1n)
return true;
}
// Return composite
return false;
}
// It returns false if n is
// composite and returns true if n
// is probably prime. k is an
// input parameter that determines
// accuracy level. Higher value of
// k indicates more accuracy.
function isPrime( n, k=40)
{
// (JML- all literal integers converted to use n suffix denoting BigInt)
// Corner cases
if (n <= 1n || n == 4n) return false;
if (n <= 3n) return true;
// Find r such that n =
// 2^d * r + 1 for some r >= 1
let d = n - 1n;
while (d % 2n == 0n)
d /= 2n;
// Iterate given nber of 'k' times
for (let i = 0; i < k; i++)
if (!millerTest(d, n))
return false;
return true;
}So far it printed out a few primes for me within the range, or what I think should be primes, right? I don't know enough of the math involved or the "miller test" for primes to know if this algorithm is actually finding an exact prime, or is finding something that might be a prime.
The author from the corresponding blog post opens by saying:
The Miller-Rabin Primality Test is a reliable test for prime numbers, even though it can only determine the probability that a number is prime.
(accentuation added)
So as far as I can tell, this algorithm seems to only get us part of the way there? What must we do so that we can build a list of what are guaranteed to be prime numbers? Assuming we want extremely large BigInt primes...
Actually, for my current use case, I need to find primes between 70 and 80 digits, but I would like to know how to find primes for arbitrary sized digits up to 65536 digits if possible.
Knowing that "a prime number has exactly two factors — 1 and the number itself", means we need to find the factors of the BigInt somehow, I think. That lead me here and also to this function:
function primeFactors(n){
const factors = []
let divisor = 2n
let i = 0
while (n > 2n) {
if (n % divisor == 0n) {
factors.push(divisor)
n = n / divisor
} else{
divisor++
}
i++
if (i % 100 === 0) {
console.log(i)
}
}
console.log(i)
return factors
}
I then added it to my original while loop:
while (true) {
let n = rbigint(
1000000000100000000010000000001000000000100000000010000000001000000000n,
10000000001000000000100000000010000000001000000000100000000010000000001000000000n
)
if (isPrime(n) && n % 4n === 3n) {
const factors = primeFactors(n)
console.log(factors)
console.log(String(n))
}
}
As you can see, I also added those console.log statements in order to debug how many iterations were going on, because calling primeFactor was hanging. Well after a few seconds I cancelled the process having logged 22481400 iterations without seemingly being close to finishing, I'm not sure how long it would take. Trying to only log every 10 million iterations, it just chugs away, never completing. I cancelled after 300000000 iterations to calculate the factors of the first number for which isPrime(n) && n % 4n === 3n was true. It seems we would need at least 300000000300000000300000000300000000300000000300000000 or some crazy number of iterations to complete the factorization.... I don't know how to calculate this part, but wondering how to get the prime anyways.
So the question is, how do I get an "exact" prime, not a "probable" prime, in JavaScript, when targeting these extremely large BigInt values?
