Skip to content

Instantly share code, notes, and snippets.

@paulmillr
Created March 3, 2023 00:52
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save paulmillr/08948297e60b54d1469ab5af7a48c633 to your computer and use it in GitHub Desktop.
Save paulmillr/08948297e60b54d1469ab5af7a48c633 to your computer and use it in GitHub Desktop.
jacobi symbol for bigints
function jacobi(a, n) {
if (n <= 0n) throw new Error('n must be positive integer');
if (n % 2n === 0n) throw new Error('n must be odd');
a %= n;
let result = 1;
while (a !== 0n) {
while (a % 2n === 0n) {
a /= 2n;
let n_mod_8 = n % 8n;
if (n_mod_8 === 3n || n_mod_8 === 5n) {
result = -result
}
}
let _a = a;
a = n, n = _a;
if (a % 4n === 3n && n % 4n === 3n) result = -result;
a %= n;
}
if (n === 1n) return result;
return 0n;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment