ark_ff/fields/
sqrt.rs

1/// Indication of the field element's quadratic residuosity
2///
3/// # Examples
4/// ```
5/// # use ark_std::test_rng;
6/// # use ark_std::UniformRand;
7/// # use ark_test_curves::{LegendreSymbol, Field, bls12_381::Fq as Fp};
8/// let a: Fp = Fp::rand(&mut test_rng());
9/// let b = a.square();
10/// assert_eq!(b.legendre(), LegendreSymbol::QuadraticResidue);
11/// ```
12#[derive(Debug, PartialEq, Eq)]
13pub enum LegendreSymbol {
14    Zero = 0,
15    QuadraticResidue = 1,
16    QuadraticNonResidue = -1,
17}
18
19impl LegendreSymbol {
20    /// Returns true if `self.is_zero()`.
21    ///
22    /// # Examples
23    /// ```
24    /// # use ark_std::test_rng;
25    /// # use ark_std::UniformRand;
26    /// # use ark_test_curves::{LegendreSymbol, Field, bls12_381::Fq as Fp};
27    /// let a: Fp = Fp::rand(&mut test_rng());
28    /// let b: Fp = a.square();
29    /// assert!(!b.legendre().is_zero());
30    /// ```
31    pub fn is_zero(&self) -> bool {
32        *self == LegendreSymbol::Zero
33    }
34
35    /// Returns true if `self` is a quadratic non-residue.
36    ///
37    /// # Examples
38    /// ```
39    /// # use ark_test_curves::{Fp2Config, Field, LegendreSymbol, bls12_381::{Fq, Fq2Config}};
40    /// let a: Fq = Fq2Config::NONRESIDUE;
41    /// assert!(a.legendre().is_qnr());
42    /// ```
43    pub fn is_qnr(&self) -> bool {
44        *self == LegendreSymbol::QuadraticNonResidue
45    }
46
47    /// Returns true if `self` is a quadratic residue.
48    /// # Examples
49    /// ```
50    /// # use ark_std::test_rng;
51    /// # use ark_test_curves::bls12_381::Fq as Fp;
52    /// # use ark_std::UniformRand;
53    /// # use ark_ff::{LegendreSymbol, Field};
54    /// let a: Fp = Fp::rand(&mut test_rng());
55    /// let b: Fp = a.square();
56    /// assert!(b.legendre().is_qr());
57    /// ```
58    pub fn is_qr(&self) -> bool {
59        *self == LegendreSymbol::QuadraticResidue
60    }
61}
62
63/// Precomputation that makes computing square roots faster
64/// A particular variant should only be instantiated if the modulus satisfies
65/// the corresponding condition.
66#[non_exhaustive]
67pub enum SqrtPrecomputation<F: crate::Field> {
68    // Tonelli-Shanks algorithm works for all elements, no matter what the modulus is.
69    TonelliShanks {
70        two_adicity: u32,
71        quadratic_nonresidue_to_trace: F,
72        trace_of_modulus_minus_one_div_two: &'static [u64],
73    },
74    /// To be used when the modulus is 3 mod 4.
75    Case3Mod4 {
76        modulus_plus_one_div_four: &'static [u64],
77    },
78}
79
80impl<F: crate::Field> SqrtPrecomputation<F> {
81    pub fn sqrt(&self, elem: &F) -> Option<F> {
82        match self {
83            Self::TonelliShanks {
84                two_adicity,
85                quadratic_nonresidue_to_trace,
86                trace_of_modulus_minus_one_div_two,
87            } => {
88                // https://eprint.iacr.org/2012/685.pdf (page 12, algorithm 5)
89                // Actually this is just normal Tonelli-Shanks; since `P::Generator`
90                // is a quadratic non-residue, `P::ROOT_OF_UNITY = P::GENERATOR ^ t`
91                // is also a quadratic non-residue (since `t` is odd).
92                if elem.is_zero() {
93                    return Some(F::zero());
94                }
95                // Try computing the square root (x at the end of the algorithm)
96                // Check at the end of the algorithm if x was a square root
97                // Begin Tonelli-Shanks
98                let mut z = *quadratic_nonresidue_to_trace;
99                let mut w = elem.pow(trace_of_modulus_minus_one_div_two);
100                let mut x = w * elem;
101                let mut b = x * &w;
102
103                let mut v = *two_adicity as usize;
104
105                while !b.is_one() {
106                    let mut k = 0usize;
107
108                    let mut b2k = b;
109                    while !b2k.is_one() {
110                        // invariant: b2k = b^(2^k) after entering this loop
111                        b2k.square_in_place();
112                        k += 1;
113                    }
114
115                    if k == (*two_adicity as usize) {
116                        // We are in the case where self^(T * 2^k) = x^(P::MODULUS - 1) = 1,
117                        // which means that no square root exists.
118                        return None;
119                    }
120                    let j = v - k;
121                    w = z;
122                    for _ in 1..j {
123                        w.square_in_place();
124                    }
125
126                    z = w.square();
127                    b *= &z;
128                    x *= &w;
129                    v = k;
130                }
131                // Is x the square root? If so, return it.
132                if x.square() == *elem {
133                    Some(x)
134                } else {
135                    // Consistency check that if no square root is found,
136                    // it is because none exists.
137                    debug_assert!(!matches!(elem.legendre(), LegendreSymbol::QuadraticResidue));
138                    None
139                }
140            },
141            Self::Case3Mod4 {
142                modulus_plus_one_div_four,
143            } => {
144                let result = elem.pow(modulus_plus_one_div_four.as_ref());
145                (result.square() == *elem).then_some(result)
146            },
147        }
148    }
149}
ark_ff/fields/sqrt.rs

ark_ff/fields/
sqrt.rs
