crypto_bigint/modular/const_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::{ConstMontyForm, ConstMontyParams};
6
7impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ConstMontyForm<MOD, 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(MOD::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().jacobi_symbol_vartime(MOD::PARAMS.modulus())
26    }
27}
28
29#[cfg(test)]
30mod tests {
31    use crate::{
32        JacobiSymbol, U256, const_monty_form, const_monty_params,
33        modular::const_monty_form::ConstMontyParams,
34    };
35
36    const_monty_params!(
37        Modulus,
38        U256,
39        "2523648240000001BA344D80000000086121000000000013A700000000000013"
40    );
41    const_monty_form!(Fe, Modulus);
42
43    #[test]
44    fn jacobi_quad_residue() {
45        let x =
46            U256::from_be_hex("14BFAE46F4026E97C7A3FCD889B379A5F025719911C994A594FC6C5092AC58B1");
47        let x_mod = Fe::new(&x);
48
49        let jac = x_mod.jacobi_symbol();
50        let jac_vartime = x_mod.jacobi_symbol_vartime();
51        assert_eq!(jac, JacobiSymbol::One);
52        assert_eq!(jac, jac_vartime);
53    }
54
55    #[test]
56    fn jacobi_quad_nonresidue() {
57        let x =
58            U256::from_be_hex("1D2EFB21D283A2DDE77004B9DE9A9624F7B15CEEF055CD02E9EF1A9F1B76F253");
59        let x_mod = Fe::new(&x);
60
61        let jac = x_mod.jacobi_symbol();
62        let jac_vartime = x_mod.jacobi_symbol_vartime();
63        assert_eq!(jac, JacobiSymbol::MinusOne);
64        assert_eq!(jac, jac_vartime);
65    }
66}
crypto_bigint/modular/const_monty_form/mod_symbol.rs

crypto_bigint/modular/const_monty_form/
mod_symbol.rs
