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(if sign.to_bool() && rhs.as_ref().limbs[0].0 & 3 == 3 {
37            -(jacobi as i8)
38        } else {
39            jacobi as i8
40        })
41    }
42}
43
44#[cfg(test)]
45mod tests {
46    use crate::{I64, I256, JacobiSymbol, U64, U256};
47
48    #[test]
49    fn jacobi_quad_residue() {
50        // Two semiprimes with no common factors, and
51        // f is quadratic residue modulo g
52        let f = I256::from(59i32 * 67);
53        let g = U256::from(61u32 * 71).to_odd().unwrap();
54        let res = f.jacobi_symbol(&g);
55        let res_vartime = f.jacobi_symbol_vartime(&g);
56        assert_eq!(res, JacobiSymbol::One);
57        assert_eq!(res, res_vartime);
58    }
59
60    #[test]
61    fn jacobi_non_quad_residue() {
62        // f and g have no common factors, but
63        // f is not quadratic residue modulo g
64        let f = I256::from(59i32 * 67 + 2);
65        let g = U256::from(61u32 * 71).to_odd().unwrap();
66        let res = f.jacobi_symbol(&g);
67        let res_vartime = f.jacobi_symbol_vartime(&g);
68        assert_eq!(res, JacobiSymbol::MinusOne);
69        assert_eq!(res, res_vartime);
70    }
71
72    #[test]
73    fn jacobi_non_coprime() {
74        let f = I256::from(4391633i32);
75        let g = U256::from(2022161u32).to_odd().unwrap();
76        let res = f.jacobi_symbol(&g);
77        let res_vartime = f.jacobi_symbol_vartime(&g);
78        assert_eq!(res, JacobiSymbol::Zero);
79        assert_eq!(res, res_vartime);
80    }
81
82    #[test]
83    fn jacobi_zero() {
84        assert_eq!(
85            I256::ZERO.jacobi_symbol(&U256::ONE.to_odd().unwrap()),
86            JacobiSymbol::One
87        );
88        assert_eq!(
89            I256::ZERO.jacobi_symbol_vartime(&U256::ONE.to_odd().unwrap()),
90            JacobiSymbol::One
91        );
92        assert_eq!(
93            I64::ZERO.jacobi_symbol_vartime(&U256::ONE.to_odd().unwrap()),
94            JacobiSymbol::One
95        );
96        assert_eq!(
97            I256::ZERO.jacobi_symbol_vartime(&U64::ONE.to_odd().unwrap()),
98            JacobiSymbol::One
99        );
100    }
101
102    #[test]
103    fn jacobi_neg_one() {
104        let f = I256::MINUS_ONE;
105        assert_eq!(
106            f.jacobi_symbol(&U256::ONE.to_odd().unwrap()),
107            JacobiSymbol::One
108        );
109        assert_eq!(
110            f.jacobi_symbol_vartime(&U256::ONE.to_odd().unwrap()),
111            JacobiSymbol::One
112        );
113        assert_eq!(
114            I64::MINUS_ONE.jacobi_symbol_vartime(&U256::ONE.to_odd().unwrap()),
115            JacobiSymbol::One
116        );
117        assert_eq!(
118            f.jacobi_symbol(&U256::from(3u8).to_odd().unwrap()),
119            JacobiSymbol::MinusOne
120        );
121        assert_eq!(
122            f.jacobi_symbol_vartime(&U256::from(3u8).to_odd().unwrap()),
123            JacobiSymbol::MinusOne
124        );
125        assert_eq!(
126            I64::MINUS_ONE.jacobi_symbol_vartime(&U256::from(3u8).to_odd().unwrap()),
127            JacobiSymbol::MinusOne
128        );
129    }
130
131    #[test]
132    fn jacobi_int() {
133        // Two semiprimes with no common factors, and
134        // f is quadratic residue modulo g
135        let f = I256::from(59i32 * 67);
136        let g = U256::from(61u32 * 71).to_odd().unwrap();
137        let res = f.jacobi_symbol(&g);
138        let res_vartime = f.jacobi_symbol_vartime(&g);
139        assert_eq!(res, JacobiSymbol::One);
140        assert_eq!(res, res_vartime);
141
142        let res = f.checked_neg().unwrap().jacobi_symbol(&g);
143        let res_vartime = f.checked_neg().unwrap().jacobi_symbol_vartime(&g);
144        assert_eq!(res, JacobiSymbol::MinusOne);
145        assert_eq!(res, res_vartime);
146    }
147}
crypto_bigint/int/mod_symbol.rs

crypto_bigint/int/
mod_symbol.rs
