next-prime.js

let xn = (x, n) => x ** (n - 1n); // TODO: has a probably O(n!) complexity. More efficient algorithm needed.

function mod(x, n) {
    const _xn = xn(x, n);
    return (_xn - 1n) % n === 0n;
}

function withTimer(fn, timeName = 'Run time') {
    return (...args) => {
        console.time(timeName);
        const t = fn(...args);
        console.timeEnd(timeName);
        return t;
    };
}

/**
 * Get a random number between 1 and max, both exclusive. If max is 
 */
function getRandom(max) {
  max = Math.min(Number(max), Number.MAX_SAFE_INTEGER);
  return BigInt(Math.floor(Math.random() * (max - 2)) + 2);
}

/**
 * Find the next prime after the number. n is assumed to be large.
 */
function nextPrime(n) {
  n = BigInt(n);
  let nextNum = n - ((n + 1n) % 2n); // Ensure it's odd
  const numChecks = 64;
  
  while(true) {
    nextNum += 2n;  
    let isPrime = true;
  
    // Check 64 times
    for (let i = 0; i < numChecks; i++) {
      const witness = BigInt(getRandom(nextNum));
      const m = mod(witness, nextNum);
      
      if (!m) {
        // Not prime
        isPrime = false;
        break;
      }
    }
    
    if (isPrime) {
      // Most probably a prime
      return nextNum;
    }
  }
}