crypto_bigint/modular/fixed_monty_form/
mod_symbol.rs

1//! Modular symbol calculation for integers in Montgomery form with a constant modulus.
2
3use crate::JacobiSymbol;
4
5use super::FixedMontyForm;
6
7impl<const LIMBS: usize> FixedMontyForm<LIMBS> {
8    /// Compute the Jacobi symbol `(self|modulus)`.
9    ///
10    /// For a prime modulus, this corresponds to the Legendre symbol and indicates
11    /// whether `self` is quadratic residue.
12    #[must_use]
13    pub const fn jacobi_symbol(&self) -> JacobiSymbol {
14        self.retrieve().jacobi_symbol(self.params().modulus())
15    }
16
17    /// Compute the Jacobi symbol `(self|modulus)`.
18    ///
19    /// For a prime modulus, this corresponds to the Legendre symbol and indicates
20    /// whether `self` is quadratic residue.
21    ///
22    /// This method is variable-time with respect to the value of `self`.
23    #[must_use]
24    pub const fn jacobi_symbol_vartime(&self) -> JacobiSymbol {
25        self.retrieve()
26            .jacobi_symbol_vartime(self.params().modulus())
27    }
28}
29
30#[cfg(test)]
31mod tests {
32    use crate::{
33        JacobiSymbol, Odd, U256,
34        modular::{FixedMontyForm, FixedMontyParams},
35    };
36
37    const PARAMS: FixedMontyParams<{ U256::LIMBS }> =
38        FixedMontyParams::new_vartime(Odd::<U256>::from_be_hex(
39            "2523648240000001BA344D80000000086121000000000013A700000000000013",
40        ));
41
42    #[test]
43    fn jacobi_quad_residue() {
44        let x =
45            U256::from_be_hex("14BFAE46F4026E97C7A3FCD889B379A5F025719911C994A594FC6C5092AC58B1");
46        let x_mod = FixedMontyForm::new(&x, &PARAMS);
47
48        let jac = x_mod.jacobi_symbol();
49        let jac_vartime = x_mod.jacobi_symbol_vartime();
50        assert_eq!(jac, JacobiSymbol::One);
51        assert_eq!(jac, jac_vartime);
52    }
53
54    #[test]
55    fn jacobi_quad_nonresidue() {
56        let x =
57            U256::from_be_hex("1D2EFB21D283A2DDE77004B9DE9A9624F7B15CEEF055CD02E9EF1A9F1B76F253");
58        let x_mod = FixedMontyForm::new(&x, &PARAMS);
59
60        let jac = x_mod.jacobi_symbol();
61        let jac_vartime = x_mod.jacobi_symbol_vartime();
62        assert_eq!(jac, JacobiSymbol::MinusOne);
63        assert_eq!(jac, jac_vartime);
64    }
65}
crypto_bigint/modular/fixed_monty_form/mod_symbol.rs

crypto_bigint/modular/fixed_monty_form/
mod_symbol.rs
