composite_modulus_proofs 0.1.0

Proofs about several propoerties of a composite modulus - square-free, product of 2 primes, a blum integer
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

use crypto_bigint::{
    modular::{MontyForm, MontyParams},
    Concat, Uint,
};

/// Returns Euler's totient of composite number formed of the given primes which is `(p-1)*(q-1)`
pub fn euler_totient<const PRIME_LIMBS: usize, const OUTPUT_LIMBS: usize>(
    p: &Uint<PRIME_LIMBS>,
    q: &Uint<PRIME_LIMBS>,
) -> Uint<OUTPUT_LIMBS>
where
    Uint<PRIME_LIMBS>: Concat<Output = Uint<OUTPUT_LIMBS>>,
{
    p.wrapping_sub(&Uint::<PRIME_LIMBS>::ONE)
        .widening_mul(&q.wrapping_sub(&Uint::<PRIME_LIMBS>::ONE))
}

/// Given `r_p` and `r_q` satisfying `r = r_p mod p` and `r = r_q mod q` for primes `p` and `q`,
/// return `r mod p*q` using the Chinese Remainder Theorem. Works as follows:
/// `r = r_p mod p` => `r = r_p + t*p` and substitute for `r` in `r = r_q mod q` to get `r_p + t*p = r_q mod q`.
/// Calculate `t` as `t = (r_q - r_p)/p mod q` and substitute `t` in `r = r_p + t*p` to get `r = r_p + ((r_q - r_p)/p mod q)*p`
/// `p_inv = p^-1 mod q` and `q_mtg` are the Montgomery params for reducing mod `q`
pub fn crt_combine<const LIMBS: usize, const WIDE_LIMBS: usize>(
    r_p: &Uint<LIMBS>,
    r_q: &Uint<LIMBS>,
    p_inv: MontyForm<LIMBS>,
    p: &Uint<LIMBS>,
    q_mtg: MontyParams<LIMBS>,
) -> Uint<WIDE_LIMBS>
where
    Uint<LIMBS>: Concat<Output = Uint<WIDE_LIMBS>>,
{
    // r_q - r_p mod q
    let diff = MontyForm::new(r_q, q_mtg) - MontyForm::new(r_p, q_mtg);
    // (r_q - r_p)/p mod q
    let t = (diff * p_inv).retrieve();
    // ((r_q - r_p)/p mod q) * p + r_p
    t.widening_mul(p) + r_p.resize()
}

/// Returns true if `p mod 4 = 3`
pub fn is_3_mod_4<const LIMBS: usize>(p: &Uint<LIMBS>) -> bool {
    p.as_limbs()[0].0 & 3 == 3
}

/// Returns true if `p mod 8 = 3`
pub fn is_3_mod_8<const LIMBS: usize>(p: &Uint<LIMBS>) -> bool {
    p.as_limbs()[0].0 & 7 == 3
}

/// Returns true if `p mod 8 = 5`
pub fn is_5_mod_8<const LIMBS: usize>(p: &Uint<LIMBS>) -> bool {
    p.as_limbs()[0].0 & 7 == 5
}

#[cfg(test)]
mod tests {
    use super::*;
    use crypto_bigint::{Random, RandomMod, U128, U256, U64};
    use crypto_primes::generate_prime_with_rng;
    use rand_core::OsRng;

    #[test]
    fn check_mods() {
        let mut rng = OsRng::default();
        for _ in 0..1000 {
            let a = U64::random(&mut rng);
            let a_4 = a.rem(&U64::from(4u32).to_nz().unwrap());
            let a_8 = a.rem(&U64::from(8u32).to_nz().unwrap());
            if a_4 == U64::from(3u32) {
                assert!(is_3_mod_4(&a));
            }
            if a_8 == U64::from(3u32) {
                assert!(is_3_mod_8(&a));
            }
            if a_8 == U64::from(5u32) {
                assert!(is_5_mod_8(&a));
            }
        }
    }

    #[test]
    fn crt() {
        let mut rng = OsRng::default();

        macro_rules! check {
            ( $prime_type:ident, $product_type:ident ) => {
                let p = generate_prime_with_rng::<$prime_type>(&mut rng, $prime_type::BITS);
                let q = generate_prime_with_rng::<$prime_type>(&mut rng, $prime_type::BITS);
                let n = p.widening_mul(&q);
                let q_mtg = MontyParams::new(q.to_odd().unwrap());
                // p^-1 mod q
                let p_inv = MontyForm::new(&p, q_mtg).inv().unwrap();
                for _ in 0..100 {
                    let a = $product_type::random_mod(&mut rng, &n.to_nz().unwrap());
                    // a_p = a mod p
                    let a_p: $prime_type = a.rem(&p.resize().to_nz().unwrap()).resize();
                    // a_q = a mod q
                    let a_q: $prime_type = a.rem(&q.resize().to_nz().unwrap()).resize();
                    assert_eq!(
                        a,
                        crt_combine::<{ $prime_type::LIMBS }, { $product_type::LIMBS }>(
                            &a_p, &a_q, p_inv, &p, q_mtg
                        )
                    );
                }
            };
        }
        check!(U64, U128);
        check!(U128, U256);
    }
}