composite_modulus_proofs/math/
misc.rs

1use crypto_bigint::{
2    modular::{MontyForm, MontyParams},
3    Concat, Uint,
4};
5
6/// Returns Euler's totient of composite number formed of the given primes which is `(p-1)*(q-1)`
7pub fn euler_totient<const PRIME_LIMBS: usize, const OUTPUT_LIMBS: usize>(
8    p: &Uint<PRIME_LIMBS>,
9    q: &Uint<PRIME_LIMBS>,
10) -> Uint<OUTPUT_LIMBS>
11where
12    Uint<PRIME_LIMBS>: Concat<Output = Uint<OUTPUT_LIMBS>>,
13{
14    p.wrapping_sub(&Uint::<PRIME_LIMBS>::ONE)
15        .widening_mul(&q.wrapping_sub(&Uint::<PRIME_LIMBS>::ONE))
16}
17
18/// Given `r_p` and `r_q` satisfying `r = r_p mod p` and `r = r_q mod q` for primes `p` and `q`,
19/// return `r mod p*q` using the Chinese Remainder Theorem. Works as follows:
20/// `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`.
21/// 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`
22/// `p_inv = p^-1 mod q` and `q_mtg` are the Montgomery params for reducing mod `q`
23pub fn crt_combine<const LIMBS: usize, const WIDE_LIMBS: usize>(
24    r_p: &Uint<LIMBS>,
25    r_q: &Uint<LIMBS>,
26    p_inv: MontyForm<LIMBS>,
27    p: &Uint<LIMBS>,
28    q_mtg: MontyParams<LIMBS>,
29) -> Uint<WIDE_LIMBS>
30where
31    Uint<LIMBS>: Concat<Output = Uint<WIDE_LIMBS>>,
32{
33    // r_q - r_p mod q
34    let diff = MontyForm::new(r_q, q_mtg) - MontyForm::new(r_p, q_mtg);
35    // (r_q - r_p)/p mod q
36    let t = (diff * p_inv).retrieve();
37    // ((r_q - r_p)/p mod q) * p + r_p
38    t.widening_mul(p) + r_p.resize()
39}
40
41/// Returns true if `p mod 4 = 3`
42pub fn is_3_mod_4<const LIMBS: usize>(p: &Uint<LIMBS>) -> bool {
43    p.as_limbs()[0].0 & 3 == 3
44}
45
46/// Returns true if `p mod 8 = 3`
47pub fn is_3_mod_8<const LIMBS: usize>(p: &Uint<LIMBS>) -> bool {
48    p.as_limbs()[0].0 & 7 == 3
49}
50
51/// Returns true if `p mod 8 = 5`
52pub fn is_5_mod_8<const LIMBS: usize>(p: &Uint<LIMBS>) -> bool {
53    p.as_limbs()[0].0 & 7 == 5
54}
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59    use crypto_bigint::{Random, RandomMod, U128, U256, U64};
60    use crypto_primes::generate_prime_with_rng;
61    use rand_core::OsRng;
62
63    #[test]
64    fn check_mods() {
65        let mut rng = OsRng::default();
66        for _ in 0..1000 {
67            let a = U64::random(&mut rng);
68            let a_4 = a.rem(&U64::from(4u32).to_nz().unwrap());
69            let a_8 = a.rem(&U64::from(8u32).to_nz().unwrap());
70            if a_4 == U64::from(3u32) {
71                assert!(is_3_mod_4(&a));
72            }
73            if a_8 == U64::from(3u32) {
74                assert!(is_3_mod_8(&a));
75            }
76            if a_8 == U64::from(5u32) {
77                assert!(is_5_mod_8(&a));
78            }
79        }
80    }
81
82    #[test]
83    fn crt() {
84        let mut rng = OsRng::default();
85
86        macro_rules! check {
87            ( $prime_type:ident, $product_type:ident ) => {
88                let p = generate_prime_with_rng::<$prime_type>(&mut rng, $prime_type::BITS);
89                let q = generate_prime_with_rng::<$prime_type>(&mut rng, $prime_type::BITS);
90                let n = p.widening_mul(&q);
91                let q_mtg = MontyParams::new(q.to_odd().unwrap());
92                // p^-1 mod q
93                let p_inv = MontyForm::new(&p, q_mtg).inv().unwrap();
94                for _ in 0..100 {
95                    let a = $product_type::random_mod(&mut rng, &n.to_nz().unwrap());
96                    // a_p = a mod p
97                    let a_p: $prime_type = a.rem(&p.resize().to_nz().unwrap()).resize();
98                    // a_q = a mod q
99                    let a_q: $prime_type = a.rem(&q.resize().to_nz().unwrap()).resize();
100                    assert_eq!(
101                        a,
102                        crt_combine::<{ $prime_type::LIMBS }, { $product_type::LIMBS }>(
103                            &a_p, &a_q, p_inv, &p, q_mtg
104                        )
105                    );
106                }
107            };
108        }
109        check!(U64, U128);
110        check!(U128, U256);
111    }
112}
composite_modulus_proofs/math/misc.rs

composite_modulus_proofs/math/
misc.rs
