fn miller_rabin()

in crypto/src/prime.rs [213:263]

• 35 lines of code
• 7 McCabe index (conditional complexity)

fn miller_rabin(num: &BigUint, limit: usize) -> bool {
    // Iterations recommended for which  p < (1/2)^{80}
    //  500 bits => 6 iterations
    // 1000 bits => 3 iterations
    // 2000 bits => 2 iterations
    /// Factorize a number n = 2^r * d
    /// (i.e., 2^r is the largest power of 2 that divides the candidate).
    #[inline]
    fn factorize_pow_two(n: &BigUint) -> (u64, BigUint) {
        let d = n.clone();
        // FIXME: assumption - the power of two is not a BigUint
        let num_two_power = d.trailing_zeros().unwrap_or(0);

        (num_two_power, d >> num_two_power)
    }

    assert!(num > &(3.to_biguint().unwrap()));
    assert!(num.is_odd());

    let one = BigUint::one();
    let two = &one + &one;

    let (r, d) = factorize_pow_two(&(num - &one));
    assert_eq!((BigUint::one() << r) * (&d), num - &one);

    let mut rng = rand::thread_rng();

    for _ in 0..limit {
        // Random sample from [2, n-1) or [2, n-2]
        let a = rng.gen_biguint_range(&two, &(num - &one));
        let mut x = a.modpow(&d, num).to_bigint().unwrap();

        if x.is_one() || x == (num - &one).to_bigint().unwrap() {
            continue;
        } else {
            let mut counter = one.clone();
            // Repeat r - 1 times
            while counter < r.to_biguint().unwrap() {
                x = x.modpow(&(two.to_bigint().unwrap()), &(num.to_bigint().unwrap()));
                if x == (num - &one).to_bigint().unwrap() {
                    break;
                }
                counter += &one;
            }
            if counter == r.to_biguint().unwrap() {
                return false;
            }
        }
    }
    true
}