crypto_bigint/uint/
mod_symbol.rs

1//! Support for computing modular symbols.
2
3use crate::{JacobiSymbol, Odd, U64, U128, Uint};
4
5impl<const LIMBS: usize> Uint<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        if LIMBS > RHS_LIMBS {
17            // Ensure `a` is reduced modulo `b` and operate on the smallest limb size
18            let a = self.rem(rhs.as_nz_ref());
19            return a.jacobi_symbol(rhs);
20        }
21
22        let (gcd, jacobi_neg) = if LIMBS < 4 {
23            rhs.classic_bingcd_(&self.resize())
24        } else {
25            rhs.optimized_bingcd_::<{ U64::BITS }, { U64::LIMBS }, { U128::LIMBS }>(
26                &self.resize(),
27                U64::BITS - 2,
28            )
29        };
30        // The sign of the Jacobi symbol is represented by jacobi_neg. We select 0 as the
31        // symbol when the GCD is not one, otherwise 1 or -1.
32        let jacobi = (jacobi_neg as i8 * -2 + 1) as i64;
33        JacobiSymbol::from_i8(Uint::eq(gcd.as_ref(), &Uint::ONE).select_i64(0, jacobi) as i8)
34    }
35
36    /// Compute the Jacobi symbol `(self|rhs)`.
37    ///
38    /// For prime `rhs`, this corresponds to the Legendre symbol and
39    /// indicates whether `self` is quadratic residue modulo `rhs`.
40    ///
41    /// This method executes in variable-time for both inputs.
42    #[must_use]
43    #[allow(clippy::cast_possible_truncation)]
44    pub const fn jacobi_symbol_vartime<const RHS_LIMBS: usize>(
45        &self,
46        rhs: &Odd<Uint<RHS_LIMBS>>,
47    ) -> JacobiSymbol {
48        if LIMBS > RHS_LIMBS {
49            // Ensure `a` is reduced modulo `b` and operate on the smallest limb size
50            let a = self.rem_vartime(rhs.as_nz_ref());
51            return a.jacobi_symbol_vartime(rhs);
52        } else if RHS_LIMBS > LIMBS {
53            if self.is_zero_vartime() {
54                return if rhs.as_ref().cmp_vartime(&Uint::ONE).is_eq() {
55                    JacobiSymbol::One
56                } else {
57                    JacobiSymbol::Zero
58                };
59            } else {
60                // Perform an initial swap and reduction and operate on the smallest limb size
61                let mut jacobi_neg = 0;
62
63                let tail = self.trailing_zeros_vartime();
64                if tail & 1 == 1 {
65                    // (2a|b) = -(a|b) iff b = ±3 mod 8
66                    // b is always odd, so we ignore the lower bit and check that bits 2 and 3 are '01' or '10'
67                    let b_lo = rhs.as_ref().limbs[0].0;
68                    jacobi_neg ^= ((b_lo >> 1) ^ (b_lo >> 2)) & 1;
69                }
70
71                // (b|a) = -(a|b) iff a = b = 3 mod 4 (quadratic reciprocity)
72                let b = self
73                    .shr_vartime(tail)
74                    .to_odd()
75                    .expect_copied("ensured non-zero");
76                let a_b_mod_4 = b.as_ref().limbs[0].0 & rhs.as_ref().limbs[0].0 & 3;
77                jacobi_neg ^= a_b_mod_4 & (a_b_mod_4 >> 1) & 1;
78
79                // (a, b) = (b % a, a)
80                let a = rhs.as_ref().rem_vartime(b.as_nz_ref());
81                let jacobi_symbol = a.jacobi_symbol_vartime(&b);
82                return if jacobi_neg == 1 {
83                    jacobi_symbol.neg()
84                } else {
85                    jacobi_symbol
86                };
87            }
88        }
89
90        let (gcd, jacobi_neg) = if LIMBS < 4 {
91            rhs.classic_bingcd_vartime_(&self.resize())
92        } else {
93            rhs.optimized_bingcd_vartime_::<{ U64::BITS }, { U64::LIMBS }, { U128::LIMBS }>(
94                &self.resize(),
95                U64::BITS - 2,
96            )
97        };
98        JacobiSymbol::from_i8(if gcd.as_ref().cmp_vartime(&Uint::ONE).is_eq() {
99            jacobi_neg as i8 * -2 + 1
100        } else {
101            0
102        })
103    }
104}
105
106#[cfg(test)]
107mod tests {
108    use crate::{JacobiSymbol, U256};
109
110    #[test]
111    fn jacobi_quad_residue() {
112        // Two semiprimes with no common factors, and
113        // f is quadratic residue modulo g
114        let f = U256::from(59u32 * 67);
115        let g = U256::from(61u32 * 71).to_odd().unwrap();
116        let res = f.jacobi_symbol(&g);
117        let res_small = f.resize::<1>().jacobi_symbol(&g);
118        let res_large = f.jacobi_symbol(&g.resize::<1>());
119        let res_vartime = f.jacobi_symbol_vartime(&g);
120        let res_vartime_small = f.resize::<1>().jacobi_symbol_vartime(&g);
121        let res_vartime_large = f.jacobi_symbol_vartime(&g.resize::<1>());
122        assert_eq!(res, JacobiSymbol::One);
123        assert_eq!(res, res_small);
124        assert_eq!(res, res_large);
125        assert_eq!(res, res_vartime);
126        assert_eq!(res, res_vartime_small);
127        assert_eq!(res, res_vartime_large);
128    }
129
130    #[test]
131    fn jacobi_non_quad_residue() {
132        // f and g have no common factors, but
133        // f is not quadratic residue modulo g
134        let f = U256::from(59u32 * 67 + 2);
135        let g = U256::from(61u32 * 71).to_odd().unwrap();
136        let res = f.jacobi_symbol(&g);
137        let res_small = f.resize::<1>().jacobi_symbol(&g);
138        let res_large = f.jacobi_symbol(&g.resize::<1>());
139        let res_vartime = f.jacobi_symbol_vartime(&g);
140        let res_vartime_small = f.resize::<1>().jacobi_symbol_vartime(&g);
141        let res_vartime_large = f.jacobi_symbol_vartime(&g.resize::<1>());
142        assert_eq!(res, JacobiSymbol::MinusOne);
143        assert_eq!(res, res_small);
144        assert_eq!(res, res_large);
145        assert_eq!(res, res_vartime);
146        assert_eq!(res, res_vartime_small);
147        assert_eq!(res, res_vartime_large);
148    }
149
150    #[test]
151    fn jacobi_non_coprime() {
152        let f = U256::from(4391633u32);
153        let g = U256::from(2022161u32).to_odd().unwrap();
154        let res = f.jacobi_symbol(&g);
155        let res_small = f.resize::<1>().jacobi_symbol(&g);
156        let res_large = f.jacobi_symbol(&g.resize::<1>());
157        let res_vartime = f.jacobi_symbol_vartime(&g);
158        let res_vartime_small = f.resize::<1>().jacobi_symbol_vartime(&g);
159        let res_vartime_large = f.jacobi_symbol_vartime(&g.resize::<1>());
160        assert_eq!(res, JacobiSymbol::Zero);
161        assert_eq!(res, res_small);
162        assert_eq!(res, res_large);
163        assert_eq!(res, res_vartime);
164        assert_eq!(res, res_vartime_small);
165        assert_eq!(res, res_vartime_large);
166    }
167
168    #[test]
169    fn jacobi_zero() {
170        let f = U256::ZERO;
171        let g = U256::ONE.to_odd().unwrap();
172        let res = f.jacobi_symbol(&g);
173        let res_small = f.resize::<1>().jacobi_symbol(&g);
174        let res_large = f.jacobi_symbol(&g.resize::<1>());
175        let res_vartime = f.jacobi_symbol_vartime(&g);
176        let res_vartime_small = f.resize::<1>().jacobi_symbol_vartime(&g);
177        let res_vartime_large = f.jacobi_symbol_vartime(&g.resize::<1>());
178        assert_eq!(res, JacobiSymbol::One);
179        assert_eq!(res, res_small);
180        assert_eq!(res, res_large);
181        assert_eq!(res, res_vartime);
182        assert_eq!(res, res_vartime_small);
183        assert_eq!(res, res_vartime_large);
184    }
185
186    #[test]
187    fn jacobi_one() {
188        let f = U256::ONE;
189        let g = U256::ONE.to_odd().unwrap();
190        let res = f.jacobi_symbol(&g);
191        let res_small = f.resize::<1>().jacobi_symbol(&g);
192        let res_large = f.jacobi_symbol(&g.resize::<1>());
193        let res_vartime = f.jacobi_symbol_vartime(&g);
194        let res_vartime_small = f.resize::<1>().jacobi_symbol_vartime(&g);
195        let res_vartime_large = f.jacobi_symbol_vartime(&g.resize::<1>());
196        assert_eq!(res, JacobiSymbol::One);
197        assert_eq!(res, res_small);
198        assert_eq!(res, res_large);
199        assert_eq!(res, res_vartime);
200        assert_eq!(res, res_vartime_small);
201        assert_eq!(res, res_vartime_large);
202    }
203}
crypto_bigint/uint/mod_symbol.rs

crypto_bigint/uint/
mod_symbol.rs
