16916300058

Committed 12 Aug 2025 05:33PM UTC coverage: 91.189%. Remained the same

Build # 16916300058

Build Type

Pull #168

github

Committed by

web-flow

Commit Message

Merge 270f28fdd into 5fcd63151

Pull Request Pull Request #168: Update [CI/CD] 🧪 Test Coverage Runner

Run Details

440 of 477 branches covered (92.24%)

Branch coverage included in aggregate %.

450 of 499 relevant lines covered (90.18%)

36221900.13 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.57

/src/math_helper.ts

/**
 * Internal math utilities for cryptographic operations.
 * These functions are intended for internal use only within the crypto-rand package,
 * such as for testing purposes.
 */
import * as crypto from 'crypto';

/**
 * [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)
 * 
 * **Note:** If you understand how this works, it's unlike the situation described in Wikipedia: "For instance, in 2018, Albrecht et al.
 * were able to construct composite numbers that many cryptographic libraries, such as OpenSSL and GNU GMP, declared as prime,
 * demonstrating that these libraries were not implemented with an adversarial context in mind." ¯\_(ツ)_/¯
 * 
 * @param n - The number to test for primality
 * @param k - The number of iterations for the test (a.k.a accuracy 🎯)
 * @param getRandomBytes - Function to generate random bytes (defaults to crypto.randomBytes)
 * @param enhanced - Whether to use the enhanced [FIPS](https://en.wikipedia.org/wiki/Federal_Information_Processing_Standards) version
 * @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
 * @returns A boolean indicating whether the number is probably prime
 */
export function isProbablePrime(
    n: bigint,
    k: number,
    getRandomBytes: (size: number, randFill?: boolean) => Buffer | Uint8Array = crypto.randomBytes,
    enhanced: boolean = false,
    randFill?: boolean
): boolean {
    if (enhanced) {
        return isProbablePrimeEnhanced(n, k, getRandomBytes, randFill);
    } else {
        return isProbablePrimeStandard(n, k, getRandomBytes, randFill);
    }
}

/**
 * Standard implementation of the [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)
 * 
 * This function implements the classic Miller-Rabin algorithm for primality testing.
 * It's used internally by the `isProbablePrime` function when the enhanced parameter is false.
 * 
 * @param n - The number to test for primality
 * @param k - The number of iterations for the test (higher values increase accuracy)
 * @param getRandomBytes - Function to generate random bytes for witness selection
 * @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
 * @returns A boolean indicating whether the number is probably prime
 */
function isProbablePrimeStandard(
    n: bigint,
    k: number,
    getRandomBytes: (size: number, randFill?: boolean) => Buffer | Uint8Array,
    randFill?: boolean
): boolean {

    // Handle small numbers
    if (n <= 1n) return false;
    if (n <= 3n) return true;
    if (n % 2n === 0n) return false;

    // Write n-1 as 2ʳ × d where d is odd
    let r = 0;
    let d = n - 1n;
    while (d % 2n === 0n) {
        d /= 2n;
        r++;
    }

    // ⚙️ Witness loop
    for (let i = 0; i < k; i++) {
        // Generate a random integer a in the range [2, n-2]
        // Calculate how many bytes are needed to represent n
        const byteLength = Math.ceil(n.toString(2).length / 8);
        const randomBytes = getRandomBytes(byteLength, randFill);
        let a = BigInt('0x' + randomBytes.toString('hex')) % (n - 4n) + 2n;

        // Compute aᵈ mod n
        let x = modPow(a, d, n);

        if (x === 1n || x === n - 1n) continue;

        let continueWitness = false;
        for (let j = 0; j < r - 1; j++) {
            x = modPow(x, 2n, n);
            if (x === n - 1n) {
                continueWitness = true;
                break;
            }
        }

        if (continueWitness) continue;
        return false;
    }

    return true;
}

/**
 * Enhanced implementation of the [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) following [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) standard
 * 
 * This function implements the enhanced version of the [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)
 * as specified in the [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) standard.
 * It provides stronger guarantees than the standard [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) by including additional
 * checks such as [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor) verification between random witnesses and the tested number.
 * 
 * @param n - The number to test for primality
 * @param k - The number of iterations for the test (higher values increase accuracy)
 * @param getRandomBytes - Function to generate random bytes for witness selection
 * @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
 * @returns A boolean indicating whether the number is probably prime according to [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) criteria
 */
export function isProbablePrimeEnhanced(
    n: bigint,
    k: number,
    getRandomBytes: (size: number, randFill?: boolean) => Buffer | Uint8Array,
    randFill?: boolean
): boolean {

    // Handle small numbers
    if (n <= 1n) return false;
    if (n <= 3n) return true;
    if (n % 2n === 0n) return false;

    // Write n-1 as 2ʳ × d where d is odd (step 1 and 2 in FIPS 186-5)
    let a = 0;
    let m = n - 1n;
    while (m % 2n === 0n) {
        m /= 2n;
        a++;
    }

    // ⚙️ Witness loop (step 4 in FIPS 186-5)
    //
    // Note: This does not return multiple results with indicators, such as returning false with a reason STRING like "PROVABLY COMPOSITE WITH FACTOR," etc.
    // This is designed to be simple and straightforward, avoiding the complexity overhead of handling multiple results.
    for (let i = 0; i < k; i++) {
        // Generate a random integer b in the range [2, n-2] (steps 4.1 and 4.2)
        let b: bigint;
        do {
            // Calculate how many bytes are needed to represent n
            const byteLength = Math.ceil(n.toString(2).length / 8);
            const randomBytes = getRandomBytes(byteLength, randFill);
            b = BigInt('0x' + randomBytes.toString('hex')) % (n - 1n);
        } while (b <= 1n || b >= n - 1n);

        // Step 4.3: Check if b and n have a common factor
        const g = gcd(b, n);
        if (g > 1n) {
            return false;
        }

        // Step 4.5: Compute z = b^m mod n
        let z = modPow(b, m, n);

        // Step 4.6: If z = 1 or z = n-1, continue to next iteration
        if (z === 1n || z === n - 1n) continue;

        // Step 4.7: For j = 1 to a-1
        let j = 1;
        let isComposite = true;

        while (j < a) {
            // Step 4.7.1 and 4.7.2: x = z, z = x^2 mod n
            const x = z;
            z = modPow(x, 2n, n);

            // Step 4.7.3: If z = n-1, continue to next iteration
            if (z === n - 1n) {
                isComposite = false;
                break;
            }

            // Step 4.7.4: If z = 1, go to step 4.12
            if (z === 1n) {
                // Step 4.12: g = GCD(x-1, n)
                const g = gcd(x - 1n, n);

                // Step 4.13: If g > 1, return PROVABLY COMPOSITE WITH FACTOR
                if (g > 1n) {
                    return false;
                }

                // Step 4.14: Return PROVABLY COMPOSITE AND NOT A POWER OF A PRIME
                return false;
            }

            j++;
        }

        // If we've gone through all iterations of j and z is not n-1 or 1
        if (isComposite) {
            // Steps 4.8-4.11 are handled implicitly in the loop above

            // Step 4.12: g = GCD(z-1, n)
            const g = gcd(z - 1n, n);

            // Step 4.13: If g > 1, return PROVABLY COMPOSITE WITH FACTOR
            if (g > 1n) {
                return false;
            }

            // Step 4.14: Return PROVABLY COMPOSITE AND NOT A POWER OF A PRIME
            return false;
        }
    }

    // Step 5: Return PROBABLY PRIME
    return true;
}

/**
 * [Modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation): baseᵉˣᵖᵒⁿᵉⁿᵗ mod modulus
 * 
 * @param base - The base value
 * @param exponent - The exponent value
 * @param modulus - The modulus value
 * @returns The result of the modular exponentiation
 */
export function modPow(base: bigint, exponent: bigint, modulus: bigint): bigint {
    if (modulus === 1n) return 0n;

    let result = 1n;
    base = base % modulus;

    while (exponent > 0n) {
        if (exponent % 2n === 1n) {
            result = (result * base) % modulus;
        }
        exponent = exponent >> 1n;
        base = (base * base) % modulus;
    }

    return result;
}

/**
 * Calculate the [modular multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) using the [Extended Euclidean Algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm),
 * similar to operations performed in [Rijndael - AES](https://en.wikipedia.org/wiki/Advanced_Encryption_Standard).
 * 
 * **Note:** This is a helper function primarily intended for testing purposes.
 * Not recommended for production use as it may be vulnerable to timing attacks.
 * 
 * @param a - The number to find the inverse for
 * @param m - The modulus
 * @returns The [modular multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) inverse of a modulo m
 */
export function modInverse(a: bigint, m: bigint): bigint {
    // Extended Euclidean Algorithm to find modular multiplicative inverse
    let [old_r, r] = [a, m];
    let [old_s, s] = [1n, 0n];
    let [old_t, t] = [0n, 1n];

    while (r !== 0n) {
        const quotient = old_r / r;
        [old_r, r] = [r, old_r - quotient * r];
        [old_s, s] = [s, old_s - quotient * s];
        [old_t, t] = [t, old_t - quotient * t];
    }

    // If old_r != 1, then a and m are not coprime and inverse doesn't exist
    if (old_r !== 1n) {
        throw new Error('Modular inverse does not exist');
    }

    // Make sure the result is positive
    return (old_s % m + m) % m;
}

/**
 * Async version of [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)
 * 
 * **Note:** If you understand how this works, it's unlike the situation described in Wikipedia: "For instance, in 2018, Albrecht et al.
 * were able to construct composite numbers that many cryptographic libraries, such as OpenSSL and GNU GMP, declared as prime,
 * demonstrating that these libraries were not implemented with an adversarial context in mind." ¯\_(ツ)_/¯
 * 
 * @param n - The number to test for primality
 * @param k - The number of iterations for the test (a.k.a accuracy 🎯)
 * @param getRandomBytesAsync - Async function to generate random bytes
 * @param enhanced - Whether to use the enhanced [FIPS](https://en.wikipedia.org/wiki/Federal_Information_Processing_Standards) version
 * @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
 * @returns A Promise that resolves to a boolean indicating whether the number is probably prime
 */
export async function isProbablePrimeAsync(
    n: bigint,
    k: number,
    getRandomBytesAsync: (size: number) => Promise<Buffer | Uint8Array>,
    enhanced: boolean = false,
    randFill?: boolean
): Promise<boolean> {
    if (enhanced) {
        return isProbablePrimeEnhancedAsync(n, k, getRandomBytesAsync, randFill);
    } else {
        return isProbablePrimeStandardAsync(n, k, getRandomBytesAsync, randFill);
    }
}

/**
 * Asynchronous implementation of the standard [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)
 * 
 * This function is the asynchronous version of `isProbablePrimeStandard`, implementing the classic
 * Miller-Rabin algorithm for primality testing. It's used internally by the `isProbablePrimeAsync`
 * function when the enhanced parameter is false.
 * 
 * @param n - The number to test for primality
 * @param k - The number of iterations for the test (higher values increase accuracy)
 * @param getRandomBytesAsync - Async function to generate random bytes for witness selection
 * @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
 * @returns A Promise that resolves to a boolean indicating whether the number is probably prime
 */
async function isProbablePrimeStandardAsync(
    n: bigint,
    k: number,
    getRandomBytesAsync: (size: number, randFill?: boolean) => Promise<Buffer | Uint8Array>,
    randFill?: boolean
): Promise<boolean> {

    // Handle small numbers
    if (n <= 1n) return false;
    if (n <= 3n) return true;
    if (n % 2n === 0n) return false;

    // Write n-1 as 2ʳ × d where d is odd
    let r = 0;
    let d = n - 1n;
    while (d % 2n === 0n) {
        d /= 2n;
        r++;
    }

    // ⚙️ Witness loop
    for (let i = 0; i < k; i++) {
        // Generate a random integer a in the range [2, n-2]
        // Calculate how many bytes are needed to represent n
        const byteLength = Math.ceil(n.toString(2).length / 8);
        const randomBytes = await getRandomBytesAsync(byteLength, randFill);
        let a = BigInt('0x' + randomBytes.toString('hex')) % (n - 4n) + 2n;

        // Compute aᵈ mod n
        let x = modPow(a, d, n);

        if (x === 1n || x === n - 1n) continue;

        let continueWitness = false;
        for (let j = 0; j < r - 1; j++) {
            x = modPow(x, 2n, n);
            if (x === n - 1n) {
                continueWitness = true;
                break;
            }
        }

        if (continueWitness) continue;
        return false;
    }

    return true;
}

/**
 * Asynchronous implementation of the enhanced [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) following [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) standard
 * 
 * This function is the asynchronous version of `isProbablePrimeEnhanced`, implementing the enhanced
 * version of the [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) as specified in the 
 * [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) standard.
 * It provides stronger guarantees than the standard [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) by including additional
 * checks such as [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor) verification between random witnesses and the tested number.
 * 
 * @param n - The number to test for primality
 * @param k - The number of iterations for the test (higher values increase accuracy)
 * @param getRandomBytesAsync - Async function to generate random bytes for witness selection
 * @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
 * @returns A Promise that resolves to a boolean indicating whether the number is probably prime according to [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) criteria
 */
export async function isProbablePrimeEnhancedAsync(
    n: bigint,
    k: number,
    getRandomBytesAsync: (size: number, randFill?: boolean) => Promise<Buffer | Uint8Array>,
    randFill?: boolean
): Promise<boolean> {

    // Handle small numbers
    if (n <= 1n) return false;
    if (n <= 3n) return true;
    if (n % 2n === 0n) return false;

    // Write n-1 as 2ʳ × d where d is odd (step 1 and 2 in FIPS 186-5)
    let a = 0;
    let m = n - 1n;
    while (m % 2n === 0n) {
        m /= 2n;
        a++;
    }

    // ⚙️ Witness loop (step 4 in FIPS 186-5)
    //
    // Note: This does not return multiple results with indicators, such as returning false with a reason STRING like "PROVABLY COMPOSITE WITH FACTOR," etc.
    // This is designed to be simple and straightforward, avoiding the complexity overhead of handling multiple results.
    for (let i = 0; i < k; i++) {
        // Generate a random integer b in the range [2, n-2] (steps 4.1 and 4.2)
        let b: bigint;
        do {
            // Calculate how many bytes are needed to represent n
            const byteLength = Math.ceil(n.toString(2).length / 8);
            const randomBytes = await getRandomBytesAsync(byteLength, randFill);
            b = BigInt('0x' + randomBytes.toString('hex')) % (n - 1n);
        } while (b <= 1n || b >= n - 1n);

        // Step 4.3: Check if b and n have a common factor
        const g = gcd(b, n);
        if (g > 1n) {
            return false;
        }

        // Step 4.5: Compute z = b^m mod n
        let z = modPow(b, m, n);

        // Step 4.6: If z = 1 or z = n-1, continue to next iteration
        if (z === 1n || z === n - 1n) continue;

        // Step 4.7: For j = 1 to a-1
        let j = 1;
        let isComposite = true;

        while (j < a) {
            // Step 4.7.1 and 4.7.2: x = z, z = x^2 mod n
            const x = z;
            z = modPow(x, 2n, n);

            // Step 4.7.3: If z = n-1, continue to next iteration
            if (z === n - 1n) {
                isComposite = false;
                break;
            }

            // Step 4.7.4: If z = 1, go to step 4.12
            if (z === 1n) {
                // Step 4.12: g = GCD(x-1, n)
                const g = gcd(x - 1n, n);

                // Step 4.13: If g > 1, return PROVABLY COMPOSITE WITH FACTOR
                if (g > 1n) {
                    return false;
                }

                // Step 4.14: Return PROVABLY COMPOSITE AND NOT A POWER OF A PRIME
                return false;
            }

            j++;
        }

        // If we've gone through all iterations of j and z is not n-1 or 1
        if (isComposite) {
            // Steps 4.8-4.11 are handled implicitly in the loop above

            // Step 4.12: g = GCD(z-1, n)
            const g = gcd(z - 1n, n);

            // Step 4.13: If g > 1, return PROVABLY COMPOSITE WITH FACTOR
            if (g > 1n) {
                return false;
            }

            // Step 4.14: Return PROVABLY COMPOSITE AND NOT A POWER OF A PRIME
            return false;
        }
    }

    // Step 5: Return PROBABLY PRIME
    return true;
}

/**
 * Calculate the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) (GCD) of two numbers using the [Euclidean algorithm](https://en.wikipedia.org/wiki/Greatest_common_divisor#Euclidean_algorithm)
 * 
 * @param a - First number
 * @param b - Second number
 * @returns The greatest common divisor of a and b
 */
export function gcd(a: bigint, b: bigint): bigint {
    while (b !== 0n) {
        const temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

1	/**
2	* Internal math utilities for cryptographic operations.
3	* These functions are intended for internal use only within the crypto-rand package,
4	* such as for testing purposes.
5	*/
6	import * as crypto from 'crypto';
7
8	/**
9	* [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)
10	*
11	* Note: If you understand how this works, it's unlike the situation described in Wikipedia: "For instance, in 2018, Albrecht et al.
12	* were able to construct composite numbers that many cryptographic libraries, such as OpenSSL and GNU GMP, declared as prime,
13	* demonstrating that these libraries were not implemented with an adversarial context in mind." ¯\_(ツ)_/¯
14	*
15	* @param n - The number to test for primality
16	* @param k - The number of iterations for the test (a.k.a accuracy 🎯)
17	* @param getRandomBytes - Function to generate random bytes (defaults to crypto.randomBytes)
18	* @param enhanced - Whether to use the enhanced [FIPS](https://en.wikipedia.org/wiki/Federal_Information_Processing_Standards) version
19	* @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
20	* @returns A boolean indicating whether the number is probably prime
21	*/
22	export function isProbablePrime(
23	n: bigint,
24	k: number,
25	getRandomBytes: (size: number, randFill?: boolean) => Buffer \| Uint8Array = crypto.randomBytes,	4,198✔
26	enhanced: boolean = false,	4,538✔
27	randFill?: boolean
28	): boolean {
29	if (enhanced) {	1,401,064✔
30	return isProbablePrimeEnhanced(n, k, getRandomBytes, randFill);	1,285,380✔
31	} else {
32	return isProbablePrimeStandard(n, k, getRandomBytes, randFill);	115,684✔
33	}
34	}
35
36	/**
37	* Standard implementation of the [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)
38	*
39	* This function implements the classic Miller-Rabin algorithm for primality testing.
40	* It's used internally by the `isProbablePrime` function when the enhanced parameter is false.
41	*
42	* @param n - The number to test for primality
43	* @param k - The number of iterations for the test (higher values increase accuracy)
44	* @param getRandomBytes - Function to generate random bytes for witness selection
45	* @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
46	* @returns A boolean indicating whether the number is probably prime
47	*/
48	function isProbablePrimeStandard(
49	n: bigint,
50	k: number,
51	getRandomBytes: (size: number, randFill?: boolean) => Buffer \| Uint8Array,
52	randFill?: boolean
53	): boolean {
54
55	// Handle small numbers
56	if (n <= 1n) return false;	115,684✔
57	if (n <= 3n) return true;	115,480✔
58	if (n % 2n === 0n) return false;	115,208✔
59
60	// Write n-1 as 2ʳ × d where d is odd
61	let r = 0;	114,052✔
62	let d = n - 1n;	114,052✔
63	while (d % 2n === 0n) {	114,052✔
64	d /= 2n;	225,448✔
65	r++;	225,448✔
66	}
67
68	// ⚙️ Witness loop
69	for (let i = 0; i < k; i++) {	114,052✔
70	// Generate a random integer a in the range [2, n-2]
71	// Calculate how many bytes are needed to represent n
72	const byteLength = Math.ceil(n.toString(2).length / 8);	261,728✔
73	const randomBytes = getRandomBytes(byteLength, randFill);	261,728✔
74	let a = BigInt('0x' + randomBytes.toString('hex')) % (n - 4n) + 2n;	261,728✔
75
76	// Compute aᵈ mod n
77	let x = modPow(a, d, n);	261,728✔
78
79	if (x === 1n \|\| x === n - 1n) continue;	261,728✔
80
81	let continueWitness = false;	145,122✔
82	for (let j = 0; j < r - 1; j++) {	145,122✔
83	x = modPow(x, 2n, n);	179,094✔
84	if (x === n - 1n) {	179,094✔
85	continueWitness = true;	37,714✔
86	break;	37,714✔
87	}
88	}
89
90	if (continueWitness) continue;	145,122✔
91	return false;	107,408✔
92	}
93
94	return true;	6,644✔
95	}
96
97	/**
98	* Enhanced implementation of the [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) following [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) standard
99	*
100	* This function implements the enhanced version of the [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)
101	* as specified in the [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) standard.
102	* It provides stronger guarantees than the standard [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) by including additional
103	* checks such as [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor) verification between random witnesses and the tested number.
104	*
105	* @param n - The number to test for primality
106	* @param k - The number of iterations for the test (higher values increase accuracy)
107	* @param getRandomBytes - Function to generate random bytes for witness selection
108	* @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
109	* @returns A boolean indicating whether the number is probably prime according to [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) criteria
110	*/
111	export function isProbablePrimeEnhanced(
112	n: bigint,
113	k: number,
114	getRandomBytes: (size: number, randFill?: boolean) => Buffer \| Uint8Array,
115	randFill?: boolean
116	): boolean {
117
118	// Handle small numbers
119	if (n <= 1n) return false;	1,285,380✔
120	if (n <= 3n) return true;	1,285,312✔
121	if (n % 2n === 0n) return false;	1,285,176✔
122
123	// Write n-1 as 2ʳ × d where d is odd (step 1 and 2 in FIPS 186-5)
124	let a = 0;	1,284,360✔
125	let m = n - 1n;	1,284,360✔
126	while (m % 2n === 0n) {	1,284,360✔
127	m /= 2n;	2,571,120✔
128	a++;	2,571,120✔
129	}
130
131	// ⚙️ Witness loop (step 4 in FIPS 186-5)
132	//
133	// Note: This does not return multiple results with indicators, such as returning false with a reason STRING like "PROVABLY COMPOSITE WITH FACTOR," etc.
134	// This is designed to be simple and straightforward, avoiding the complexity overhead of handling multiple results.
135	for (let i = 0; i < k; i++) {	1,284,360✔
136	// Generate a random integer b in the range [2, n-2] (steps 4.1 and 4.2)
137	let b: bigint;
138	do {	1,477,106✔
139	// Calculate how many bytes are needed to represent n
140	const byteLength = Math.ceil(n.toString(2).length / 8);	1,478,272✔
141	const randomBytes = getRandomBytes(byteLength, randFill);	1,478,272✔
142	b = BigInt('0x' + randomBytes.toString('hex')) % (n - 1n);	1,478,272✔
143	} while (b <= 1n \|\| b >= n - 1n);	1,477,689✔
144
145	// Step 4.3: Check if b and n have a common factor
146	const g = gcd(b, n);	1,477,106✔
147	if (g > 1n) {	1,477,106✔
148	return false;	243,358✔
149	}
150
151	// Step 4.5: Compute z = b^m mod n
152	let z = modPow(b, m, n);	1,233,748✔
153
154	// Step 4.6: If z = 1 or z = n-1, continue to next iteration
155	if (z === 1n \|\| z === n - 1n) continue;	1,233,748✔
156
157	// Step 4.7: For j = 1 to a-1
158	let j = 1;	1,102,442✔
159	let isComposite = true;	1,102,442✔
160
161	while (j < a) {	1,102,442✔
162	// Step 4.7.1 and 4.7.2: x = z, z = x^2 mod n
163	const x = z;	1,174,738✔
164	z = modPow(x, 2n, n);	1,174,738✔
165
166	// Step 4.7.3: If z = n-1, continue to next iteration
167	if (z === n - 1n) {	1,174,738✔
168	isComposite = false;	67,924✔
169	break;	67,924✔
170	}
171
172	// Step 4.7.4: If z = 1, go to step 4.12
173	if (z === 1n) {	1,106,814✔
174	// Step 4.12: g = GCD(x-1, n)
175	const g = gcd(x - 1n, n);	6✔
176
177	// Step 4.13: If g > 1, return PROVABLY COMPOSITE WITH FACTOR
178	if (g > 1n) {	6!
179	return false;	6✔
180	}
181
182	// Step 4.14: Return PROVABLY COMPOSITE AND NOT A POWER OF A PRIME
183	return false;	×
184	}
185
186	j++;	1,106,808✔
187	}
188
189	// If we've gone through all iterations of j and z is not n-1 or 1
190	if (isComposite) {	1,102,436✔
191	// Steps 4.8-4.11 are handled implicitly in the loop above
192
193	// Step 4.12: g = GCD(z-1, n)
194	const g = gcd(z - 1n, n);	1,034,512✔
195
196	// Step 4.13: If g > 1, return PROVABLY COMPOSITE WITH FACTOR
197	if (g > 1n) {	1,034,512✔
198	return false;	383,464✔
199	}
200
201	// Step 4.14: Return PROVABLY COMPOSITE AND NOT A POWER OF A PRIME
202	return false;	651,048✔
203	}
204	}
205
206	// Step 5: Return PROBABLY PRIME
207	return true;	6,484✔
208	}
209
210	/**
211	* [Modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation): baseᵉˣᵖᵒⁿᵉⁿᵗ mod modulus
212	*
213	* @param base - The base value
214	* @param exponent - The exponent value
215	* @param modulus - The modulus value
216	* @returns The result of the modular exponentiation
217	*/
218	export function modPow(base: bigint, exponent: bigint, modulus: bigint): bigint {
219	if (modulus === 1n) return 0n;	5,453,994✔
220
221	let result = 1n;	5,453,926✔
222	base = base % modulus;	5,453,926✔
223
224	while (exponent > 0n) {	5,453,926✔
225	if (exponent % 2n === 1n) {	2,531,302,854✔
226	result = (result * base) % modulus;	1,268,277,138✔
227	}
228	exponent = exponent >> 1n;	2,531,302,854✔
229	base = (base * base) % modulus;	2,531,302,854✔
230	}
231
232	return result;	5,453,926✔
233	}
234
235	/**
236	* Calculate the [modular multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) using the [Extended Euclidean Algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm),
237	* similar to operations performed in [Rijndael - AES](https://en.wikipedia.org/wiki/Advanced_Encryption_Standard).
238	*
239	* Note: This is a helper function primarily intended for testing purposes.
240	* Not recommended for production use as it may be vulnerable to timing attacks.
241	*
242	* @param a - The number to find the inverse for
243	* @param m - The modulus
244	* @returns The [modular multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) inverse of a modulo m
245	*/
246	export function modInverse(a: bigint, m: bigint): bigint {
247	// Extended Euclidean Algorithm to find modular multiplicative inverse
248	let [old_r, r] = [a, m];	4,420✔
249	let [old_s, s] = [1n, 0n];	4,420✔
250	let [old_t, t] = [0n, 1n];	4,420✔
251
252	while (r !== 0n) {	4,420✔
253	const quotient = old_r / r;	1,004,922✔
254	[old_r, r] = [r, old_r - quotient * r];	1,004,922✔
255	[old_s, s] = [s, old_s - quotient * s];	1,004,922✔
256	[old_t, t] = [t, old_t - quotient * t];	1,004,922✔
257	}
258
259	// If old_r != 1, then a and m are not coprime and inverse doesn't exist
260	if (old_r !== 1n) {	4,420✔
261	throw new Error('Modular inverse does not exist');	136✔
262	}
263
264	// Make sure the result is positive
265	return (old_s % m + m) % m;	4,284✔
266	}
267
268	/**
269	* Async version of [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)
270	*
271	* Note: If you understand how this works, it's unlike the situation described in Wikipedia: "For instance, in 2018, Albrecht et al.
272	* were able to construct composite numbers that many cryptographic libraries, such as OpenSSL and GNU GMP, declared as prime,
273	* demonstrating that these libraries were not implemented with an adversarial context in mind." ¯\_(ツ)_/¯
274	*
275	* @param n - The number to test for primality
276	* @param k - The number of iterations for the test (a.k.a accuracy 🎯)
277	* @param getRandomBytesAsync - Async function to generate random bytes
278	* @param enhanced - Whether to use the enhanced [FIPS](https://en.wikipedia.org/wiki/Federal_Information_Processing_Standards) version
279	* @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
280	* @returns A Promise that resolves to a boolean indicating whether the number is probably prime
281	*/
282	export async function isProbablePrimeAsync(
283	n: bigint,
284	k: number,
285	getRandomBytesAsync: (size: number) => Promise<Buffer \| Uint8Array>,
286	enhanced: boolean = false,	1,394✔
287	randFill?: boolean
288	): Promise<boolean> {
289	if (enhanced) {	1,394,070✔
290	return isProbablePrimeEnhancedAsync(n, k, getRandomBytesAsync, randFill);	1,302,926✔
291	} else {
292	return isProbablePrimeStandardAsync(n, k, getRandomBytesAsync, randFill);	91,144✔
293	}
294	}
295
296	/**
297	* Asynchronous implementation of the standard [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)
298	*
299	* This function is the asynchronous version of `isProbablePrimeStandard`, implementing the classic
300	* Miller-Rabin algorithm for primality testing. It's used internally by the `isProbablePrimeAsync`
301	* function when the enhanced parameter is false.
302	*
303	* @param n - The number to test for primality
304	* @param k - The number of iterations for the test (higher values increase accuracy)
305	* @param getRandomBytesAsync - Async function to generate random bytes for witness selection
306	* @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
307	* @returns A Promise that resolves to a boolean indicating whether the number is probably prime
308	*/
309	async function isProbablePrimeStandardAsync(
310	n: bigint,
311	k: number,
312	getRandomBytesAsync: (size: number, randFill?: boolean) => Promise<Buffer \| Uint8Array>,
313	randFill?: boolean
314	): Promise<boolean> {
315
316	// Handle small numbers
317	if (n <= 1n) return false;	91,144✔
318	if (n <= 3n) return true;	90,940✔
319	if (n % 2n === 0n) return false;	90,668✔
320
321	// Write n-1 as 2ʳ × d where d is odd
322	let r = 0;	89,784✔
323	let d = n - 1n;	89,784✔
324	while (d % 2n === 0n) {	89,784✔
325	d /= 2n;	177,716✔
326	r++;	177,716✔
327	}
328
329	// ⚙️ Witness loop
330	for (let i = 0; i < k; i++) {	89,784✔
331	// Generate a random integer a in the range [2, n-2]
332	// Calculate how many bytes are needed to represent n
333	const byteLength = Math.ceil(n.toString(2).length / 8);	141,382✔
334	const randomBytes = await getRandomBytesAsync(byteLength, randFill);	141,382✔
335	let a = BigInt('0x' + randomBytes.toString('hex')) % (n - 4n) + 2n;	141,382✔
336
337	// Compute aᵈ mod n
338	let x = modPow(a, d, n);	141,382✔
339
340	if (x === 1n \|\| x === n - 1n) continue;	141,382✔
341
342	let continueWitness = false;	102,220✔
343	for (let j = 0; j < r - 1; j++) {	102,220✔
344	x = modPow(x, 2n, n);	115,382✔
345	if (x === n - 1n) {	115,382✔
346	continueWitness = true;	15,806✔
347	break;	15,806✔
348	}
349	}
350
351	if (continueWitness) continue;	102,220✔
352	return false;	86,414✔
353	}
354
355	return true;	3,370✔
356	}
357
358	/**
359	* Asynchronous implementation of the enhanced [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) following [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) standard
360	*
361	* This function is the asynchronous version of `isProbablePrimeEnhanced`, implementing the enhanced
362	* version of the [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) as specified in the
363	* [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) standard.
364	* It provides stronger guarantees than the standard [Miller-Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) by including additional
365	* checks such as [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor) verification between random witnesses and the tested number.
366	*
367	* @param n - The number to test for primality
368	* @param k - The number of iterations for the test (higher values increase accuracy)
369	* @param getRandomBytesAsync - Async function to generate random bytes for witness selection
370	* @param randFill - Optional parameter to use [crypto.randomFill](https://nodejs.org/api/crypto.html#cryptorandomfillbuffer-offset-size-callback) instead of [crypto.randomBytes](https://nodejs.org/api/crypto.html#cryptorandombytessize-callback) (Node.js only)
371	* @returns A Promise that resolves to a boolean indicating whether the number is probably prime according to [FIPS 186-5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) criteria
372	*/
373	export async function isProbablePrimeEnhancedAsync(
374	n: bigint,
375	k: number,
376	getRandomBytesAsync: (size: number, randFill?: boolean) => Promise<Buffer \| Uint8Array>,
377	randFill?: boolean
378	): Promise<boolean> {
379
380	// Handle small numbers
381	if (n <= 1n) return false;	1,302,926✔
382	if (n <= 3n) return true;	1,302,722✔
383	if (n % 2n === 0n) return false;	1,302,450✔
384
385	// Write n-1 as 2ʳ × d where d is odd (step 1 and 2 in FIPS 186-5)
386	let a = 0;	1,301,566✔
387	let m = n - 1n;	1,301,566✔
388	while (m % 2n === 0n) {	1,301,566✔
389	m /= 2n;	2,602,898✔
390	a++;	2,602,898✔
391	}
392
393	// ⚙️ Witness loop (step 4 in FIPS 186-5)
394	//
395	// Note: This does not return multiple results with indicators, such as returning false with a reason STRING like "PROVABLY COMPOSITE WITH FACTOR," etc.
396	// This is designed to be simple and straightforward, avoiding the complexity overhead of handling multiple results.
397	for (let i = 0; i < k; i++) {	1,301,566✔
398	// Generate a random integer b in the range [2, n-2] (steps 4.1 and 4.2)
399	let b: bigint;
400	do {	1,442,002✔
401	// Calculate how many bytes are needed to represent n
402	const byteLength = Math.ceil(n.toString(2).length / 8);	1,442,858✔
403	const randomBytes = await getRandomBytesAsync(byteLength, randFill);	1,442,858✔
404	b = BigInt('0x' + randomBytes.toString('hex')) % (n - 1n);	1,442,858✔
405	} while (b <= 1n \|\| b >= n - 1n);	1,442,430✔
406
407	// Step 4.3: Check if b and n have a common factor
408	const g = gcd(b, n);	1,442,002✔
409	if (g > 1n) {	1,442,002✔
410	return false;	247,482✔
411	}
412
413	// Step 4.5: Compute z = b^m mod n
414	let z = modPow(b, m, n);	1,194,520✔
415
416	// Step 4.6: If z = 1 or z = n-1, continue to next iteration
417	if (z === 1n \|\| z === n - 1n) continue;	1,194,520✔
418
419	// Step 4.7: For j = 1 to a-1
420	let j = 1;	1,097,978✔
421	let isComposite = true;	1,097,978✔
422
423	while (j < a) {	1,097,978✔
424	// Step 4.7.1 and 4.7.2: x = z, z = x^2 mod n
425	const x = z;	1,144,126✔
426	z = modPow(x, 2n, n);	1,144,126✔
427
428	// Step 4.7.3: If z = n-1, continue to next iteration
429	if (z === n - 1n) {	1,144,126✔
430	isComposite = false;	48,538✔
431	break;	48,538✔
432	}
433
434	// Step 4.7.4: If z = 1, go to step 4.12
435	if (z === 1n) {	1,095,588✔
436	// Step 4.12: g = GCD(x-1, n)
437	const g = gcd(x - 1n, n);	4✔
438
439	// Step 4.13: If g > 1, return PROVABLY COMPOSITE WITH FACTOR
440	if (g > 1n) {	4!
441	return false;	4✔
442	}
443
444	// Step 4.14: Return PROVABLY COMPOSITE AND NOT A POWER OF A PRIME
445	return false;	×
446	}
447
448	j++;	1,095,584✔
449	}
450
451	// If we've gone through all iterations of j and z is not n-1 or 1
452	if (isComposite) {	1,097,974✔
453	// Steps 4.8-4.11 are handled implicitly in the loop above
454
455	// Step 4.12: g = GCD(z-1, n)
456	const g = gcd(z - 1n, n);	1,049,436✔
457
458	// Step 4.13: If g > 1, return PROVABLY COMPOSITE WITH FACTOR
459	if (g > 1n) {	1,049,436✔
460	return false;	387,984✔
461	}
462
463	// Step 4.14: Return PROVABLY COMPOSITE AND NOT A POWER OF A PRIME
464	return false;	661,452✔
465	}
466	}
467
468	// Step 5: Return PROBABLY PRIME
469	return true;	4,644✔
470	}
471
472	/**
473	* Calculate the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) (GCD) of two numbers using the [Euclidean algorithm](https://en.wikipedia.org/wiki/Greatest_common_divisor#Euclidean_algorithm)
474	*
475	* @param a - First number
476	* @param b - Second number
477	* @returns The greatest common divisor of a and b
478	*/
479	export function gcd(a: bigint, b: bigint): bigint {
480	while (b !== 0n) {	5,005,242✔
481	const temp = b;	2,817,146,896✔
482	b = a % b;	2,817,146,896✔
483	a = temp;	2,817,146,896✔
484	}
485	return a;	5,005,242✔
486	}

H0llyW00dzZ / crypto-rand / 16916300058

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous