halo2curves/ff_ext/
cubic.rs
1use super::ExtField;
2
3#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
4pub struct CubicExtField<F: ff::Field> {
5 pub(crate) c0: F,
6 pub(crate) c1: F,
7 pub(crate) c2: F,
8}
9
10pub trait CubicSparseMul {
11 type Base: ExtField;
12
13 #[must_use]
14 fn mul_by_1(lhs: &CubicExtField<Self::Base>, c1: &Self::Base) -> CubicExtField<Self::Base> {
15 let b_b = lhs.c1 * c1;
16
17 let t1 = (lhs.c1 + lhs.c2) * c1 - b_b;
18 let t1 = t1.mul_by_nonresidue();
19 let t2 = (lhs.c0 + lhs.c1) * c1 - b_b;
20
21 CubicExtField {
22 c0: t1,
23 c1: t2,
24 c2: b_b,
25 }
26 }
27
28 #[must_use]
29 fn mul_by_01(
30 lhs: &CubicExtField<Self::Base>,
31 c0: &Self::Base,
32 c1: &Self::Base,
33 ) -> CubicExtField<Self::Base> {
34 let a_a = lhs.c0 * c0;
35 let b_b = lhs.c1 * c1;
36
37 let t1 = *c1 * (lhs.c1 + lhs.c2) - b_b;
38 let t1 = a_a + t1.mul_by_nonresidue();
39 let t3 = *c0 * (lhs.c0 + lhs.c2) - a_a + b_b;
40 let t2 = (*c0 + c1) * (lhs.c0 + lhs.c1) - a_a - b_b;
41
42 CubicExtField {
43 c0: t1,
44 c1: t2,
45 c2: t3,
46 }
47 }
48}
49
50pub trait CubicExtFieldArith {
51 type Base: ExtField;
52
53 fn mul_assign(lhs: &mut CubicExtField<Self::Base>, rhs: &CubicExtField<Self::Base>) {
54 let a_a = lhs.c0 * rhs.c0;
55 let b_b = lhs.c1 * rhs.c1;
56 let c_c = lhs.c2 * rhs.c2;
57
58 let t1 = (rhs.c1 + rhs.c2) * (lhs.c1 + lhs.c2) - (c_c + b_b);
59
60 let t1 = a_a + t1.mul_by_nonresidue();
61
62 let t3 = (rhs.c0 + rhs.c2) * (lhs.c0 + lhs.c2) - (a_a - b_b + c_c);
63
64 let t2 = (rhs.c0 + rhs.c1) * (lhs.c0 + lhs.c1) - (a_a + b_b);
65 let t2 = t2 + c_c.mul_by_nonresidue();
66
67 lhs.c0 = t1;
68 lhs.c1 = t2;
69 lhs.c2 = t3;
70 }
71
72 fn square_assign(el: &mut CubicExtField<Self::Base>) {
73 use ff::Field;
74
75 let s0 = el.c0.square();
76 let s1 = (el.c0 * el.c1).double();
77 let s2 = (el.c0 - el.c1 + el.c2).square();
78 let s3 = (el.c1 * el.c2).double();
79 let s4 = el.c2.square();
80
81 el.c0 = s3.mul_by_nonresidue() + s0;
82 el.c1 = s4.mul_by_nonresidue() + s1;
83 el.c2 = s1 + s2 + s3 - s0 - s4;
84 }
85}
86
87impl<F: ff::Field> CubicExtField<F> {
88 #[inline]
89 pub const fn new(c0: F, c1: F, c2: F) -> Self {
90 Self { c0, c1, c2 }
91 }
92
93 #[inline]
94 pub const fn zero() -> Self {
95 Self {
96 c0: F::ZERO,
97 c1: F::ZERO,
98 c2: F::ZERO,
99 }
100 }
101
102 #[inline]
103 pub const fn one() -> Self {
104 Self {
105 c0: F::ONE,
106 c1: F::ZERO,
107 c2: F::ZERO,
108 }
109 }
110
111 #[inline]
112 pub fn c0(&self) -> &F {
113 &self.c0
114 }
115
116 #[inline]
117 pub fn c1(&self) -> &F {
118 &self.c1
119 }
120
121 #[inline]
122 pub fn c2(&self) -> &F {
123 &self.c2
124 }
125
126 #[inline]
127 pub fn double(&self) -> Self {
128 Self {
129 c0: self.c0.double(),
130 c1: self.c1.double(),
131 c2: self.c2.double(),
132 }
133 }
134
135 #[inline]
136 pub fn add(&self, other: &Self) -> Self {
137 Self {
138 c0: self.c0 + other.c0,
139 c1: self.c1 + other.c1,
140 c2: self.c2 + other.c2,
141 }
142 }
143
144 #[inline]
145 pub fn sub(&self, other: &Self) -> Self {
146 Self {
147 c0: self.c0 - other.c0,
148 c1: self.c1 - other.c1,
149 c2: self.c2 - other.c2,
150 }
151 }
152
153 #[inline]
154 pub fn neg(&self) -> Self {
155 Self {
156 c0: -self.c0,
157 c1: -self.c1,
158 c2: -self.c2,
159 }
160 }
161}
162
163impl<F: ff::Field> CubicExtField<F>
164where
165 Self: CubicExtFieldArith<Base = F>,
166{
167 pub fn mul(&self, rhs: &Self) -> Self {
168 let mut lhs = *self;
169 Self::mul_assign(&mut lhs, rhs);
170 lhs
171 }
172
173 pub fn mul_assign(&mut self, rhs: &Self) {
174 <Self as CubicExtFieldArith>::mul_assign(self, rhs);
175 }
176
177 pub fn square(el: &Self) -> Self {
178 let mut el = *el;
179 Self::square_assign(&mut el);
180 el
181 }
182
183 pub fn square_assign(&mut self) {
184 <Self as CubicExtFieldArith>::square_assign(self);
185 }
186}
187
188impl<F: ExtField> ff::Field for CubicExtField<F>
189where
190 CubicExtField<F>: CubicExtFieldArith<Base = F> + ExtField, {
194 const ZERO: Self = Self::zero();
195 const ONE: Self = Self::one();
196
197 fn random(mut rng: impl rand_core::RngCore) -> Self {
198 Self::new(
199 F::random(&mut rng),
200 F::random(&mut rng),
201 F::random(&mut rng),
202 )
203 }
204
205 fn is_zero(&self) -> subtle::Choice {
206 self.c0.is_zero() & self.c1.is_zero()
207 }
208
209 fn square(&self) -> Self {
210 CubicExtField::square(self)
211 }
212
213 fn double(&self) -> Self {
214 self.double()
215 }
216
217 fn sqrt(&self) -> subtle::CtOption<Self> {
218 unimplemented!()
219 }
220
221 fn sqrt_ratio(_: &Self, _: &Self) -> (subtle::Choice, Self) {
222 unimplemented!()
223 }
224
225 fn invert(&self) -> subtle::CtOption<Self> {
226 let c0 = self.c2.mul_by_nonresidue() * self.c1.neg() + self.c0.square();
227 let c1 = self.c2.square().mul_by_nonresidue() - (self.c0 * self.c1);
228 let c2 = self.c1.square() - (self.c0 * self.c2);
229
230 let t = (self.c2 * c1) + (self.c1 * c2);
231 let t = t.mul_by_nonresidue() + (self.c0 * c0);
232
233 t.invert().map(|t| Self {
234 c0: t * c0,
235 c1: t * c1,
236 c2: t * c2,
237 })
238 }
239}
240
241impl<F: ff::Field> subtle::ConditionallySelectable for CubicExtField<F> {
242 fn conditional_select(a: &Self, b: &Self, choice: subtle::Choice) -> Self {
243 CubicExtField {
244 c0: F::conditional_select(&a.c0, &b.c0, choice),
245 c1: F::conditional_select(&a.c1, &b.c1, choice),
246 c2: F::conditional_select(&a.c2, &b.c2, choice),
247 }
248 }
249}
250
251impl<F: ff::Field> subtle::ConstantTimeEq for CubicExtField<F> {
252 fn ct_eq(&self, other: &Self) -> subtle::Choice {
253 self.c0.ct_eq(&other.c0) & self.c1.ct_eq(&other.c1) & self.c2.ct_eq(&other.c2)
254 }
255}