Skip to content

Instantly share code, notes, and snippets.

@xkizer
Last active April 22, 2022 00:42
Show Gist options
  • Save xkizer/ebb2aa47a58a8af7b4aa39a9d1344fd3 to your computer and use it in GitHub Desktop.
Save xkizer/ebb2aa47a58a8af7b4aa39a9d1344fd3 to your computer and use it in GitHub Desktop.
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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment