crypto_bigint/
jacobi.rs

1use crate::{Choice, CtEq};
2use core::ops::Neg;
3
4/// Possible return values for Jacobi symbol calculations.
5#[derive(Debug, Copy, Clone)]
6#[repr(i8)]
7pub enum JacobiSymbol {
8    /// The two arguments are not coprime, they have a common divisor apart from 1.
9    Zero = 0,
10
11    /// The two arguments are coprime. If the lower argument is prime, then the upper argument
12    /// is quadratic residue modulo the lower argument. Otherwise, the upper argument is known to
13    /// be quadratic nonresidue for an even number of prime factors of the lower argument.
14    One = 1,
15
16    /// The two terms are coprime, and the upper argument is a quadratic nonresidue modulo the
17    /// lower argument.
18    MinusOne = -1,
19}
20
21impl JacobiSymbol {
22    /// Determine if the symbol is zero.
23    #[must_use]
24    pub const fn is_zero(&self) -> Choice {
25        Choice::from_i64_eq(*self as i8 as i64, 0)
26    }
27
28    /// Determine if the symbol is one.
29    #[must_use]
30    pub const fn is_one(&self) -> Choice {
31        Choice::from_i64_eq(*self as i8 as i64, 1)
32    }
33
34    /// Determine if the symbol is minus one.
35    #[must_use]
36    pub const fn is_minus_one(&self) -> Choice {
37        Choice::from_i64_eq(*self as i8 as i64, -1)
38    }
39
40    /// Negate the symbol.
41    #[must_use]
42    pub const fn neg(self) -> Self {
43        match self {
44            Self::Zero => Self::Zero,
45            Self::One => Self::MinusOne,
46            Self::MinusOne => Self::One,
47        }
48    }
49
50    pub(crate) const fn from_i8(value: i8) -> Self {
51        match value {
52            0 => Self::Zero,
53            1 => Self::One,
54            -1 => Self::MinusOne,
55            _ => panic!("invalid value for Jacobi symbol"),
56        }
57    }
58}
59
60impl CtEq for JacobiSymbol {
61    fn ct_eq(&self, other: &Self) -> Choice {
62        (*self as i8).ct_eq(&(*other as i8))
63    }
64}
65
66impl Eq for JacobiSymbol {}
67
68impl PartialEq for JacobiSymbol {
69    fn eq(&self, other: &Self) -> bool {
70        self.ct_eq(other).to_bool()
71    }
72}
73
74impl From<JacobiSymbol> for i8 {
75    fn from(symbol: JacobiSymbol) -> i8 {
76        symbol as i8
77    }
78}
79
80impl Neg for JacobiSymbol {
81    type Output = Self;
82
83    fn neg(self) -> Self {
84        Self::neg(self)
85    }
86}
87
88#[cfg(feature = "subtle")]
89impl subtle::ConstantTimeEq for JacobiSymbol {
90    fn ct_eq(&self, other: &Self) -> subtle::Choice {
91        CtEq::ct_eq(self, other).into()
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use super::JacobiSymbol;
98
99    #[test]
100    fn jacobi_eq() {
101        assert_eq!(JacobiSymbol::Zero, JacobiSymbol::Zero);
102        assert_ne!(JacobiSymbol::Zero, JacobiSymbol::One);
103        assert_ne!(JacobiSymbol::Zero, JacobiSymbol::MinusOne);
104        assert!(JacobiSymbol::Zero.is_zero().to_bool());
105        assert!(!JacobiSymbol::One.is_zero().to_bool());
106        assert!(JacobiSymbol::One.is_one().to_bool());
107        assert!(!JacobiSymbol::MinusOne.is_one().to_bool());
108        assert!(JacobiSymbol::MinusOne.is_minus_one().to_bool());
109        #[cfg(feature = "subtle")]
110        assert!(bool::from(subtle::ConstantTimeEq::ct_eq(
111            &JacobiSymbol::Zero,
112            &JacobiSymbol::Zero
113        )));
114        #[cfg(feature = "subtle")]
115        assert!(!bool::from(subtle::ConstantTimeEq::ct_eq(
116            &JacobiSymbol::Zero,
117            &JacobiSymbol::One
118        )));
119    }
120
121    #[test]
122    fn jacobi_from() {
123        assert_eq!(i8::from(JacobiSymbol::Zero), 0i8);
124        assert_eq!(i8::from(JacobiSymbol::One), 1i8);
125        assert_eq!(i8::from(JacobiSymbol::MinusOne), -1i8);
126        assert_eq!(JacobiSymbol::from_i8(0i8), JacobiSymbol::Zero);
127        assert_eq!(JacobiSymbol::from_i8(1i8), JacobiSymbol::One);
128        assert_eq!(JacobiSymbol::from_i8(-1i8), JacobiSymbol::MinusOne);
129    }
130
131    #[test]
132    fn jacobi_neg() {
133        assert_eq!(JacobiSymbol::Zero.neg(), JacobiSymbol::Zero);
134        assert_eq!(-JacobiSymbol::One, JacobiSymbol::MinusOne);
135        assert_eq!(-JacobiSymbol::MinusOne, JacobiSymbol::One);
136    }
137}
crypto_bigint/jacobi.rs

crypto_bigint/
jacobi.rs
