https://coins.github.io/numbers-js/src/numbers.js

1/**
2 * Extended Euclidean Algorithm
3 * 
4 * @param {BigInt} m The first number 
5 * @param {BigInt} n The second number
6 * @return [BigInt, BigInt, BigInt] 
7 *        a b Bézout coefficients 
8 *        d the greatest common divisor 
9 *
10 */
11export function egcd(m, n) {
12    let a1 = 1n;
13    let b1 = 0n;
14    let a = 0n;
15    let b = 1n;
16    let c = m;
17    let d = n;
18    let q = c / d;
19    let r = c % d;
20    while (r > 0n) {
21        let t = a1;
22        a1 = a;
23        a = t - q * a; // a1 - qa
24        t = b1;
25        b1 = b;
26        b = t - q * b; // b1 - qb
27        c = d;
28        d = r;
29        q = c / d;
30        r = c % d;
31    }
32    return [a, b, d];
33}
34
35
36/**
37 * Modular absolute value. 
38 * Adds the modulus until the value becomes positive.
39 * 
40 * @param {BigInt} x The element
41 * @return {BigInt} The element's absolute value.
42 *
43 */
44export function mod_abs(x, m) {
45    while (x < 0)
46        x = (m + x) % m
47    return x
48}
49
50/**
51 * Modular Inverse
52 * 
53 * @param {BigInt} x - The number
54 * @param {BigInt} m - The modulus
55 * @return {BigInt} The inverse of x
56 * 
57 */
58export function mod_inv(x, m) {
59    x = mod_abs(x, m)
60    const [a, b, g] = egcd(x, m)
61    if (g != 1n)
62        throw Error(`Inverse of ${x} doesn\'t exist mod ${m}`)
63    return a
64}
65
66/**
67 * Modular Exponentiation
68 * 
69 * @param {BigInt} a - The base
70 * @param {BigInt} b - The exponent (must be positive)
71 * @param {BigInt} m - The modulus
72 * @return {BigInt} The exponentiation
73 *
74 */
75export function mod_exp(a, b, m) {
76    if (b < 0n)
77        throw Error(`Exponent must be positive`)
78
79    a = mod_abs(a, m)
80    let result = 1n
81
82    while (b > 0) {
83        if (b & 1n) { // read the least significant bit
84            result = result * a % m
85        }
86
87        b >>= 1n // cut off the least significant
88        a = a * a % m
89    }
90    return result
91}
92
93
94/**
95 * Modular Square Root
96 * 
97 * @param {BigInt} x The number
98 * @param {BigInt} p The prime modulus
99 * @return {BigInt} The square root of x
100 *
101 */
102export function mod_sqrt(x, p) {
103    // TODO: implement other square root algorithms
104    if ((p % 4n) !== 3n) 
105        throw Error('Square root algorithm for (p mod 4 == 1) not implemented yet')
106    return mod_exp(x, (p + 1n) / 4n, p)
107}