1use ff::Field;
2use subtle::{Choice, CtOption};
3
4use super::{
5 cubic::{CubicExtField, CubicSparseMul},
6 ExtField,
7};
8
9pub trait QuadSparseMul {
10 type Base: ExtField;
11
12 fn mul_by_014(
13 lhs: &mut QuadExtField<CubicExtField<Self::Base>>,
14 c0: &Self::Base,
15 c1: &Self::Base,
16 c4: &Self::Base,
17 ) where
18 CubicExtField<Self::Base>: CubicSparseMul<Base = Self::Base> + ExtField,
19 {
20 let aa = CubicExtField::mul_by_01(&lhs.c0, c0, c1);
21 let bb = CubicExtField::mul_by_1(&lhs.c1, c4);
22 let t0 = &(lhs.c1 + lhs.c0);
23 let t1 = *c1 + c4;
24 lhs.c1 = CubicExtField::mul_by_01(t0, c0, &t1) - (aa + bb);
25 lhs.c0 = bb.mul_by_nonresidue() + aa;
26 }
27
28 fn mul_by_034(
29 lhs: &mut QuadExtField<CubicExtField<Self::Base>>,
30 c0: &Self::Base,
31 c3: &Self::Base,
32 c4: &Self::Base,
33 ) where
34 CubicExtField<Self::Base>: CubicSparseMul<Base = Self::Base> + ExtField,
35 {
36 let t0 = CubicExtField {
37 c0: lhs.c0.c0 * c0,
38 c1: lhs.c0.c1 * c0,
39 c2: lhs.c0.c2 * c0,
40 };
41 let t1 = CubicExtField::mul_by_01(&lhs.c1, c3, c4);
42 let t2 = lhs.c0 + lhs.c1;
43 let t3 = *c0 + c3;
44 lhs.c1 = CubicExtField::mul_by_01(&t2, &t3, c4) - t0 - t1;
45 lhs.c0 = t0 + t1.mul_by_nonresidue();
46 }
47}
48
49pub fn sqrt_algo9<F: ExtField, S: AsRef<[u64]>>(
51 e: &QuadExtField<F>,
52 q_minus_3_over_4: S,
53 q_minus_1_over_2: S,
54) -> subtle::CtOption<QuadExtField<F>>
55where
56 QuadExtField<F>: QuadExtFieldArith<Base = F> + ExtField,
57{
58 if e.is_zero().into() {
59 subtle::CtOption::new(QuadExtField::ZERO, subtle::Choice::from(1))
60 } else {
61 let mut a1 = e.pow(q_minus_3_over_4);
62
63 let alpha = a1.square();
64 let alpha = alpha * e;
65
66 let mut a0 = alpha;
67 a0.frobenius_map(1);
68 let a0 = a0 * alpha;
69
70 let neg1 = QuadExtField::<F> {
71 c0: F::ZERO - F::ONE,
72 c1: F::ZERO,
73 };
74
75 if a0 == neg1 {
76 subtle::CtOption::new(a0, subtle::Choice::from(0))
77 } else {
78 a1.mul_assign(e);
79
80 if alpha == neg1 {
81 a1.mul_assign(&QuadExtField::<F> {
82 c0: F::ZERO,
83 c1: F::ONE,
84 });
85 } else {
86 let alpha = alpha + QuadExtField::<F>::ONE;
87 let alpha = alpha.pow(q_minus_1_over_2);
88 a1.mul_assign(&alpha);
89 }
90 subtle::CtOption::new(a1, subtle::Choice::from(1))
91 }
92 }
93}
94
95pub fn sqrt_algo10<F: ExtField, S: AsRef<[u64]>>(
97 el: &QuadExtField<F>,
98 precompute_e: &QuadExtField<F>,
99 precompute_f: &QuadExtField<F>,
100 q_minus_1_over_4: S,
101) -> subtle::CtOption<QuadExtField<F>>
102where
103 QuadExtField<F>: QuadExtFieldArith<Base = F> + ExtField,
104{
105 let b = el.pow_vartime(q_minus_1_over_4);
106
107 let b_2 = b.square();
108 let mut b_2_q = b_2;
109 b_2_q.frobenius_map(1);
110
111 let a0 = b_2_q * b_2;
112 let neg1 = QuadExtField::<F> {
113 c0: F::ZERO - F::ONE,
114 c1: F::ZERO,
115 };
116
117 if a0 == neg1 {
118 CtOption::new(a0, Choice::from(0))
119 } else {
120 let mut x = b;
121 x.frobenius_map(1);
122 if x * b == QuadExtField::ONE {
123 let x0 = (b_2 * el).c0.sqrt().unwrap();
124 x.c0.mul_assign(x0);
125 x.c1.mul_assign(x0);
126 CtOption::new(x, Choice::from(1))
127 } else {
128 let x0 = (b_2 * precompute_f * el).sqrt().unwrap();
129 x *= x0 * precompute_e;
130 CtOption::new(x, Choice::from(1))
131 }
132 }
133}
134
135pub enum SQRT<F: Field> {
136 Algorithm9 {
137 q_minus_3_over_4: &'static [u64],
138 q_minus_1_over_2: &'static [u64],
139 },
140 Algorithm10 {
141 precompute_e: QuadExtField<F>,
142 precompute_f: QuadExtField<F>,
143 q_minus_1_over_4: &'static [u64],
144 },
145 Unimplemented,
146}
147
148pub trait QuadExtFieldArith {
149 type Base: ExtField;
150 const SQRT: SQRT<Self::Base> = SQRT::Unimplemented;
151
152 fn mul_assign(lhs: &mut QuadExtField<Self::Base>, rhs: &QuadExtField<Self::Base>) {
153 let v0 = lhs.c0 * rhs.c0;
154 let v1 = lhs.c1 * rhs.c1;
155 lhs.c1 = (lhs.c0 + lhs.c1) * (rhs.c0 + rhs.c1) - (v0 + v1);
156 lhs.c0 = v0 + v1.mul_by_nonresidue();
157 }
158
159 fn square_assign(el: &mut QuadExtField<Self::Base>) {
160 let ab = el.c0 * el.c1;
161 let c0c1 = el.c0 + el.c1;
162 let c0 = (el.c1.mul_by_nonresidue() + el.c0) * c0c1 - ab;
163 el.c1 = ab.double();
164 el.c0 = c0 - ab.mul_by_nonresidue();
165 }
166}
167
168#[cfg(feature = "derive_serde")]
169use serde::{Deserialize, Serialize};
170
171#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
172#[cfg_attr(feature = "derive_serde", derive(Serialize, Deserialize))]
173pub struct QuadExtField<F: ff::Field> {
174 pub(crate) c0: F,
175 pub(crate) c1: F,
176}
177
178impl<F: ff::Field> QuadExtField<F> {
179 #[inline]
180 pub const fn new(c0: F, c1: F) -> Self {
181 Self { c0, c1 }
182 }
183
184 #[inline]
185 pub const fn zero() -> Self {
186 Self {
187 c0: F::ZERO,
188 c1: F::ZERO,
189 }
190 }
191
192 #[inline]
193 pub const fn one() -> Self {
194 Self {
195 c0: F::ONE,
196 c1: F::ZERO,
197 }
198 }
199
200 #[inline]
201 pub fn c0(&self) -> &F {
202 &self.c0
203 }
204
205 #[inline]
206 pub fn c1(&self) -> &F {
207 &self.c1
208 }
209
210 #[inline]
211 pub fn double(&self) -> Self {
212 Self {
213 c0: self.c0.double(),
214 c1: self.c1.double(),
215 }
216 }
217
218 #[inline]
219 pub fn add(&self, other: &Self) -> Self {
220 Self {
221 c0: self.c0 + other.c0,
222 c1: self.c1 + other.c1,
223 }
224 }
225
226 #[inline]
227 pub fn sub(&self, other: &Self) -> Self {
228 Self {
229 c0: self.c0 - other.c0,
230 c1: self.c1 - other.c1,
231 }
232 }
233
234 #[inline]
235 pub fn neg(&self) -> Self {
236 Self {
237 c0: -self.c0,
238 c1: -self.c1,
239 }
240 }
241
242 #[inline]
243 pub fn conjugate(&mut self) {
244 self.c1 = -self.c1;
245 }
246}
247
248impl<F: ExtField> QuadExtField<F>
249where
250 Self: QuadExtFieldArith<Base = F>,
251{
252 pub fn mul(&self, rhs: &Self) -> Self {
253 let mut lhs = *self;
254 Self::mul_assign(&mut lhs, rhs);
255 lhs
256 }
257
258 pub fn mul_assign(&mut self, rhs: &Self) {
259 <Self as QuadExtFieldArith>::mul_assign(self, rhs);
260 }
261
262 pub fn square(el: &Self) -> Self {
263 let mut el = *el;
264 Self::square_assign(&mut el);
265 el
266 }
267
268 pub fn square_assign(&mut self) {
269 <Self as QuadExtFieldArith>::square_assign(self);
270 }
271
272 pub fn norm(&self) -> F {
273 self.c0.square() - self.c1.square().mul_by_nonresidue()
274 }
275}
276
277impl<F: ExtField> Field for QuadExtField<F>
278where
279 QuadExtField<F>: QuadExtFieldArith<Base = F> + ExtField,
280{
281 const ZERO: Self = Self::zero();
282 const ONE: Self = Self::one();
283
284 fn random(mut rng: impl rand_core::RngCore) -> Self {
285 Self::new(F::random(&mut rng), F::random(&mut rng))
286 }
287
288 fn is_zero(&self) -> subtle::Choice {
289 self.c0.is_zero() & self.c1.is_zero()
290 }
291
292 fn square(&self) -> Self {
293 QuadExtField::square(self)
294 }
295
296 fn double(&self) -> Self {
297 self.double()
298 }
299
300 fn sqrt(&self) -> subtle::CtOption<Self> {
301 match Self::SQRT {
302 SQRT::Algorithm9 {
303 q_minus_3_over_4,
304 q_minus_1_over_2,
305 } => sqrt_algo9(self, q_minus_3_over_4, q_minus_1_over_2),
306 SQRT::Algorithm10 {
307 precompute_e,
308 precompute_f,
309 q_minus_1_over_4,
310 } => sqrt_algo10(self, &precompute_e, &precompute_f, q_minus_1_over_4),
311 SQRT::Unimplemented => unimplemented!(),
312 }
313 }
314
315 fn sqrt_ratio(_: &Self, _: &Self) -> (subtle::Choice, Self) {
316 unimplemented!()
317 }
318
319 fn invert(&self) -> subtle::CtOption<Self> {
320 self.norm().invert().map(|t| Self {
321 c0: self.c0 * t,
322 c1: self.c1 * -t,
323 })
324 }
325}
326
327impl<F: ff::Field> subtle::ConditionallySelectable for QuadExtField<F> {
328 fn conditional_select(a: &Self, b: &Self, choice: subtle::Choice) -> Self {
329 QuadExtField {
330 c0: F::conditional_select(&a.c0, &b.c0, choice),
331 c1: F::conditional_select(&a.c1, &b.c1, choice),
332 }
333 }
334}
335
336impl<F: ff::Field> subtle::ConstantTimeEq for QuadExtField<F> {
337 fn ct_eq(&self, other: &Self) -> subtle::Choice {
338 self.c0.ct_eq(&other.c0) & self.c1.ct_eq(&other.c1)
339 }
340}