cralgebra 0.2.1

A fast crypto algebra library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

use crate::*;

/// Miller-Rabin primality test.
///
/// Takes a candidate number `n` and a random `a` coprime to `n`.
/// If a true value is returned, the number may or
/// may not be prime. If a false value is returned,
/// the number is definitely composite.
pub fn miller_rabin<
    C,
    T: Clone + CyclicOrdZeroDyn<C> + ClosedSubDyn<C> + CenteredMulDyn<C> + OneDyn<C> + EuclidDyn<C>,
>(
    n: &T,
    a: &T,
    ctx: &C,
) -> bool {
    // TODO: checks
    if n.is_zero_d(ctx) || n.is_one_d(ctx) {
        return false;
    }
    let mc = (ModularCtx::new(n.clone(), ctx), ctx);
    let am = ModularDyn::new_d(a.clone(), &mc);
    let mut s = T::zero_d(ctx);
    let mut d = n.sub_d(&T::one_d(ctx), ctx);
    let two = T::one_d(ctx).add_d(&T::one_d(ctx), ctx);
    loop {
        let (q, r) = d.euclid_div_rem_d(&two, ctx);
        if !r.is_zero_d(ctx) {
            break;
        }
        d = q;
        s.add_assign_d(&T::one_d(ctx), ctx);
    }
    let mut x = am.pow_d(&d, &mc, ctx);
    if x.is_one_d(&mc) {
        return true;
    }
    loop {
        if x.add_d(&ModularDyn::one_d(&mc), &mc).is_zero_d(&mc) {
            return true;
        }
        if s.is_one_d(ctx) {
            return false;
        }
        x = x.mul_d(&x, &mc);
        s.sub_assign_d(&T::one_d(ctx), ctx);
    }
}

#[test]
fn miller_rabin_test() {
    let expected = [
        false, false, true, true, false, true, false, true, false, false, false, true, false, true,
        false, false, false, true, false, true, false, false, false, true, false, false, false,
        false, false, true, false, true, false, false, false, false, false, true, false, false,
        false, true, false, true, false, false, false, true, false, false, false, false, false,
        true, false, false, false, false, false, true, false, true, false, false, false, false,
        false, true, false, false, false, true, false, true, false, false, false, false, false,
        true, false, false, false, true, false, false, false, false, false, true, false, false,
        false, false, false, false, false, true, false, false,
    ];
    let a = Z2_8 { inner: 2 };
    for ni in (3..100).step_by(2) {
        let n = Z2_8 { inner: ni };
        let res = miller_rabin(&n, &a, &());
        assert_eq!(res, expected[ni as usize]);
    }
}