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 /// To be used when the modulus is 5 mod 8.
79 Case5Mod8 {
80 modulus_plus_three_div_eight: &'static [u64],
81 modulus_minus_one_div_four: &'static [u64],
82 },
83}
84
85impl<F: crate::Field> SqrtPrecomputation<F> {
86 pub fn sqrt(&self, elem: &F) -> Option<F> {
87 match self {
88 Self::TonelliShanks {
89 two_adicity,
90 quadratic_nonresidue_to_trace,
91 trace_of_modulus_minus_one_div_two,
92 } => {
93 // https://eprint.iacr.org/2012/685.pdf (page 12, algorithm 5)
94 // Actually this is just normal Tonelli-Shanks; since `P::Generator`
95 // is a quadratic non-residue, `P::ROOT_OF_UNITY = P::GENERATOR ^ t`
96 // is also a quadratic non-residue (since `t` is odd).
97 if elem.is_zero() {
98 return Some(F::zero());
99 }
100 // Try computing the square root (x at the end of the algorithm)
101 // Check at the end of the algorithm if x was a square root
102 // Begin Tonelli-Shanks
103 let mut z = *quadratic_nonresidue_to_trace;
104 let mut w = elem.pow(trace_of_modulus_minus_one_div_two);
105 let mut x = w * elem;
106 let mut b = x * &w;
107
108 let mut v = *two_adicity as usize;
109
110 while !b.is_one() {
111 let mut k = 0usize;
112
113 let mut b2k = b;
114 while !b2k.is_one() {
115 // invariant: b2k = b^(2^k) after entering this loop
116 b2k.square_in_place();
117 k += 1;
118 }
119
120 if k == (*two_adicity as usize) {
121 // We are in the case where self^(T * 2^k) = x^(P::MODULUS - 1) = 1,
122 // which means that no square root exists.
123 return None;
124 }
125 let j = v - k;
126 w = z;
127 for _ in 1..j {
128 w.square_in_place();
129 }
130
131 z = w.square();
132 b *= &z;
133 x *= &w;
134 v = k;
135 }
136 // Is x the square root? If so, return it.
137 if x.square() == *elem {
138 Some(x)
139 } else {
140 // Consistency check that if no square root is found,
141 // it is because none exists.
142 debug_assert!(!matches!(elem.legendre(), LegendreSymbol::QuadraticResidue));
143 None
144 }
145 },
146 // Let `x ^ 2 = a mod p` is our quadratic equation where we need
147 // to find `x` if one exists. Note that solutions modullo p
148 // exists if `a` is quadratic residue modullo `p`. Recall that `a` in
149 // `F_p` is quadratic residue if `a ^ ((p - 1) / 2) = 1 (mod p)`
150 // by Euler criterion (https://en.wikipedia.org/wiki/Euler%27s_criterion)
151 // or equivalently Legendre symbol `(a/p) = 1` so that solutions
152 // to the equation `x ^ 2 = a (mod p)` exist.
153 Self::Case3Mod4 {
154 modulus_plus_one_div_four,
155 } => {
156 // if `p = 4k + 3` then `a ^ (2k + 1) = 1 (mod p)`. After multiplying by
157 // `a` both sides of conjugation we obtain `a ^ (2k + 2) = a (mod p)` so
158 // that `a ^ (2k + 2) = x ^ 2 (mod p)`. Now we can easily take square root
159 // of both sides as every exponent is even: `x = +- a ^ (k + 1) (mod p)`.
160 let result = elem.pow(modulus_plus_one_div_four.as_ref());
161 (result.square() == *elem).then_some(result)
162 },
163 Self::Case5Mod8 {
164 modulus_plus_three_div_eight,
165 modulus_minus_one_div_four,
166 } => {
167 // When `p = 8k + 5`, we have `a ^ (4k + 2) = 1 (mod p)`.
168 // Multiplying each side by `a` will not help since the exponent
169 // will be odd. But instead, since `a ^ (4k + 2) = 1 ^ 2 = 1 (mod p)`
170 // taking square root of `1` gives us either `a ^ (2k + 1) = 1 (mod p)`
171 // or `a ^ (2k + 1) = -1 (mod p)`.
172
173 if elem.is_zero() {
174 return Some(F::zero());
175 }
176
177 let result;
178
179 // We have different solutions, if `a ^ (2k + 1)` is `1` or `-1`.
180 let check_value = elem.pow(modulus_minus_one_div_four.as_ref());
181 if check_value.is_one() {
182 // In this case, we can use the same technique as in `p = 4k + 3` case.
183 // After multiplying both sides by `a` we get
184 // `a ^ (2k + 2) = a = x ^ 2 (mod p)`
185 // so that `x = +- a ^ (k + 1) (mod p)`.
186 result = elem.pow(modulus_plus_three_div_eight.as_ref());
187 } else if check_value.neg().is_one() {
188 // In this case we can not use the same technique, but recalling
189 // Tonneli-Shanks trick of multiplying each side by some non-residue
190 // we could obtain the square root. Firstly, `2` in `F_p` is always
191 // quadratic non-residue modullo `p` as by Legendre symbol properties
192 // (https://en.wikipedia.org/wiki/Legendre_symbol):
193 // `(2/p) = (-1) ^ ((p ^ 2 - 1) / 8 )
194 // = (-1) ^ (8k ^ 2 + 10 k + 3)
195 // = -1`.
196 // By Euler criterion:
197 // `2 ^ ((p - 1) / 2) = 2 ^ (4k + 2)
198 // = -1 (mod p)`.
199 // After multiplying both sides of `a ^ (2k + 1) = -1 (mod p)` by
200 // `2 ^ (4k + 2)` we get the following conjugation:
201 // `a ^ (2k + 1) 2 ^ (4k + 2) = 1 (mod p)`.
202 // Multiplying both sides by `a` we get
203 // `a ^ (2k + 2) 2 ^ (4k + 2) = a = x ^ 2 (mod p)`
204 // so that `x = +- a ^ (k+1) 2 ^ (2k + 1) (mod p)`.
205 let two: F = 2.into();
206 result = elem
207 .pow(modulus_plus_three_div_eight.as_ref())
208 .mul(two.pow(modulus_minus_one_div_four.as_ref()))
209 } else {
210 return None;
211 }
212
213 (result.square() == *elem).then_some(result)
214 },
215 }
216 }
217}