crypto_bigint/int/
mod_symbol.rs

1//! Support for computing modular symbols.
2
3use crate::{Int, JacobiSymbol, Odd, Uint, word};
4
5impl<const LIMBS: usize> Int<LIMBS> {
6    /// Compute the Jacobi symbol `(self|rhs)`.
7    ///
8    /// For prime `rhs`, this corresponds to the Legendre symbol and
9    /// indicates whether `self` is quadratic residue modulo `rhs`.
10    #[must_use]
11    #[allow(clippy::cast_possible_truncation)]
12    pub const fn jacobi_symbol<const RHS_LIMBS: usize>(
13        &self,
14        rhs: &Odd<Uint<RHS_LIMBS>>,
15    ) -> JacobiSymbol {
16        let (abs, sign) = self.abs_sign();
17        let jacobi = abs.jacobi_symbol(rhs) as i64;
18        // (-self|rhs) = -(self|rhs) iff rhs = 3 mod 4
19        let swap = sign.and(word::choice_from_eq(rhs.as_ref().limbs[0].0 & 3, 3));
20        JacobiSymbol::from_i8(swap.select_i64(jacobi, -jacobi) as i8)
21    }
22
23    /// Compute the Jacobi symbol `(self|rhs)`.
24    ///
25    /// For prime `rhs`, this corresponds to the Legendre symbol and
26    /// indicates whether `self` is quadratic residue modulo `rhs`.
27    ///
28    /// This method executes in variable-time for the value of `self`.
29    #[must_use]
30    pub const fn jacobi_symbol_vartime<const RHS_LIMBS: usize>(
31        &self,
32        rhs: &Odd<Uint<RHS_LIMBS>>,
33    ) -> JacobiSymbol {
34        let (abs, sign) = self.abs_sign();
35        let jacobi = abs.jacobi_symbol_vartime(rhs);
36        JacobiSymbol::from_i8(
37            if sign.to_bool_vartime() && rhs.as_ref().limbs[0].0 & 3 == 3 {
38                -(jacobi as i8)
39            } else {
40                jacobi as i8
41            },
42        )
43    }
44}
45
46#[cfg(test)]
47mod tests {
48    use crate::{I64, I256, JacobiSymbol, U64, U256};
49
50    #[test]
51    fn jacobi_quad_residue() {
52        // Two semiprimes with no common factors, and
53        // f is quadratic residue modulo g
54        let f = I256::from(59i32 * 67);
55        let g = U256::from(61u32 * 71).to_odd().unwrap();
56        let res = f.jacobi_symbol(&g);
57        let res_vartime = f.jacobi_symbol_vartime(&g);
58        assert_eq!(res, JacobiSymbol::One);
59        assert_eq!(res, res_vartime);
60    }
61
62    #[test]
63    fn jacobi_non_quad_residue() {
64        // f and g have no common factors, but
65        // f is not quadratic residue modulo g
66        let f = I256::from(59i32 * 67 + 2);
67        let g = U256::from(61u32 * 71).to_odd().unwrap();
68        let res = f.jacobi_symbol(&g);
69        let res_vartime = f.jacobi_symbol_vartime(&g);
70        assert_eq!(res, JacobiSymbol::MinusOne);
71        assert_eq!(res, res_vartime);
72    }
73
74    #[test]
75    fn jacobi_non_coprime() {
76        let f = I256::from(4391633i32);
77        let g = U256::from(2022161u32).to_odd().unwrap();
78        let res = f.jacobi_symbol(&g);
79        let res_vartime = f.jacobi_symbol_vartime(&g);
80        assert_eq!(res, JacobiSymbol::Zero);
81        assert_eq!(res, res_vartime);
82    }
83
84    #[test]
85    fn jacobi_zero() {
86        assert_eq!(
87            I256::ZERO.jacobi_symbol(&U256::ONE.to_odd().unwrap()),
88            JacobiSymbol::One
89        );
90        assert_eq!(
91            I256::ZERO.jacobi_symbol_vartime(&U256::ONE.to_odd().unwrap()),
92            JacobiSymbol::One
93        );
94        assert_eq!(
95            I64::ZERO.jacobi_symbol_vartime(&U256::ONE.to_odd().unwrap()),
96            JacobiSymbol::One
97        );
98        assert_eq!(
99            I256::ZERO.jacobi_symbol_vartime(&U64::ONE.to_odd().unwrap()),
100            JacobiSymbol::One
101        );
102    }
103
104    #[test]
105    fn jacobi_neg_one() {
106        let f = I256::MINUS_ONE;
107        assert_eq!(
108            f.jacobi_symbol(&U256::ONE.to_odd().unwrap()),
109            JacobiSymbol::One
110        );
111        assert_eq!(
112            f.jacobi_symbol_vartime(&U256::ONE.to_odd().unwrap()),
113            JacobiSymbol::One
114        );
115        assert_eq!(
116            I64::MINUS_ONE.jacobi_symbol_vartime(&U256::ONE.to_odd().unwrap()),
117            JacobiSymbol::One
118        );
119        assert_eq!(
120            f.jacobi_symbol(&U256::from(3u8).to_odd().unwrap()),
121            JacobiSymbol::MinusOne
122        );
123        assert_eq!(
124            f.jacobi_symbol_vartime(&U256::from(3u8).to_odd().unwrap()),
125            JacobiSymbol::MinusOne
126        );
127        assert_eq!(
128            I64::MINUS_ONE.jacobi_symbol_vartime(&U256::from(3u8).to_odd().unwrap()),
129            JacobiSymbol::MinusOne
130        );
131    }
132
133    #[test]
134    fn jacobi_int() {
135        // Two semiprimes with no common factors, and
136        // f is quadratic residue modulo g
137        let f = I256::from(59i32 * 67);
138        let g = U256::from(61u32 * 71).to_odd().unwrap();
139        let res = f.jacobi_symbol(&g);
140        let res_vartime = f.jacobi_symbol_vartime(&g);
141        assert_eq!(res, JacobiSymbol::One);
142        assert_eq!(res, res_vartime);
143
144        let res = f.checked_neg().unwrap().jacobi_symbol(&g);
145        let res_vartime = f.checked_neg().unwrap().jacobi_symbol_vartime(&g);
146        assert_eq!(res, JacobiSymbol::MinusOne);
147        assert_eq!(res, res_vartime);
148    }
149}
crypto_bigint/int/mod_symbol.rs

crypto_bigint/int/
mod_symbol.rs
