airbender_crypto/secp256k1/field/
mod.rs1use crate::k256::FieldBytes;
2use cfg_if::cfg_if;
3use core::ops::{AddAssign, MulAssign, SubAssign};
4
5#[cfg(any(target_arch = "riscv32", test, feature = "proving"))]
6mod field_10x26;
7#[cfg(any(target_arch = "riscv32", test, feature = "proving"))]
8mod mod_inv32;
9
10#[cfg(any(target_pointer_width = "64", test, feature = "proving"))]
11mod field_5x52;
12#[cfg(any(target_pointer_width = "64", test, feature = "proving"))]
13mod mod_inv64;
14
15#[cfg(any(
16 all(target_arch = "riscv32", feature = "bigint_ops"),
17 test,
18 feature = "proving"
19))]
20mod field_8x32;
21
22#[cfg(all(debug_assertions, not(feature = "bigint_ops")))]
23mod field_impl;
24
25cfg_if! {
26 if #[cfg(all(debug_assertions, not(feature = "bigint_ops")))] {
27 use field_impl::{FieldElementImpl as FieldElementImplConst, FieldElementImpl, FieldStorageImpl};
28 } else if #[cfg(feature = "bigint_ops")] {
29 use field_10x26::{FieldElement10x26 as FieldElementImplConst, FieldStorage10x26 as FieldStorageImpl};
30 use field_8x32::FieldElement8x32 as FieldElementImpl;
31 } else if #[cfg(target_pointer_width = "64")] {
32 use field_5x52::{FieldElement5x52 as FieldElementImpl, FieldElement5x52 as FieldElementImplConst, FieldStorage5x52 as FieldStorageImpl};
33 } else if #[cfg(target_pointer_width = "32")] {
34 use field_10x26::{FieldElement10x26 as FieldElementImplConst, FieldElement10x26 as FieldElementImpl, FieldStorage10x26 as FieldStorageImpl};
35 } else {
36 panic!("unsupported arch");
37 }
38}
39
40#[derive(Debug, Clone, Copy)]
41pub struct FieldElementConst(pub(crate) FieldElementImplConst);
42
43impl FieldElementConst {
44 pub const ZERO: Self = Self(FieldElementImplConst::ZERO);
45 pub const ONE: Self = Self(FieldElementImplConst::ONE);
46
47 pub const fn from_bytes_unchecked(bytes: &[u8; 32]) -> Self {
48 Self(FieldElementImplConst::from_bytes_unchecked(bytes))
49 }
50
51 pub const fn mul(&self, rhs: &Self) -> Self {
52 Self(self.0.mul(&rhs.0))
53 }
54
55 pub const fn mul_int(&self, rhs: u32) -> Self {
56 Self(self.0.mul_int(rhs))
57 }
58
59 pub const fn square(&self) -> Self {
60 Self(self.0.square())
61 }
62
63 pub const fn add(&self, rhs: &Self) -> Self {
64 Self(self.0.add(&rhs.0))
65 }
66
67 pub const fn invert(&self) -> Self {
68 let x2 = self.pow2k(1).mul(self);
69 let x3 = x2.pow2k(1).mul(self);
70 let x6 = x3.pow2k(3).mul(&x3);
71 let x9 = x6.pow2k(3).mul(&x3);
72 let x11 = x9.pow2k(2).mul(&x2);
73 let x22 = x11.pow2k(11).mul(&x11);
74 let x44 = x22.pow2k(22).mul(&x22);
75 let x88 = x44.pow2k(44).mul(&x44);
76 let x176 = x88.pow2k(88).mul(&x88);
77 let x220 = x176.pow2k(44).mul(&x44);
78 let x223 = x220.pow2k(3).mul(&x3);
79
80 x223.pow2k(23)
81 .mul(&x22)
82 .pow2k(5)
83 .mul(self)
84 .pow2k(3)
85 .mul(&x2)
86 .pow2k(2)
87 .mul(self)
88 }
89
90 pub const fn negate(&self, magnitude: u32) -> Self {
91 Self(self.0.negate(magnitude))
92 }
93
94 pub const fn normalize(&self) -> Self {
95 Self(self.0.normalize())
96 }
97
98 pub(crate) const fn to_storage(self) -> FieldStorage {
99 FieldStorage(self.0.to_storage())
100 }
101
102 pub const fn normalizes_to_zero(&self) -> bool {
103 self.0.normalizes_to_zero()
104 }
105
106 #[inline(always)]
107 const fn pow2k(&self, k: usize) -> Self {
108 use const_for::const_for;
109 let mut x = *self;
110 const_for!(_ in 0..k => {
111 x = x.square();
112 });
113
114 x
115 }
116}
117
118#[derive(Debug, Clone, Copy)]
119pub struct FieldElement(pub(crate) FieldElementImpl);
120
121impl FieldElement {
122 pub const ZERO: Self = Self(FieldElementImpl::ZERO);
123 pub const ONE: Self = Self(FieldElementImpl::ONE);
124 pub const BETA: Self = Self(FieldElementImpl::BETA);
126
127 #[cfg(test)]
128 pub(crate) const fn from_bytes_unchecked(bytes: &[u8; 32]) -> Self {
129 Self(FieldElementImpl::from_bytes_unchecked(bytes))
130 }
131
132 pub fn from_bytes(bytes: &[u8; 32]) -> Option<Self> {
133 FieldElementImpl::from_bytes(bytes).map(Self)
134 }
135
136 pub fn mul_in_place(&mut self, rhs: &Self) {
137 self.0.mul_in_place(&rhs.0);
138 }
139
140 pub fn mul_int_in_place(&mut self, rhs: u32) {
141 self.0.mul_int_in_place(rhs);
142 }
143
144 pub fn square_in_place(&mut self) {
145 self.0.square_in_place();
146 }
147
148 pub fn add_in_place(&mut self, rhs: &Self) {
149 self.0.add_in_place(&rhs.0);
150 }
151
152 pub fn double_in_place(&mut self) {
153 self.0.double_in_place();
154 }
155
156 pub fn sub_in_place(&mut self, rhs: &Self) {
157 self.0.sub_in_place(&rhs.0);
158 }
159
160 pub fn add_int_in_place(&mut self, rhs: u32) {
161 self.0.add_int_in_place(rhs);
162 }
163
164 pub fn invert_in_place(&mut self) {
165 self.0.invert_in_place()
166 }
167
168 pub fn sqrt_in_place_unchecked(&mut self) {
169 let x1 = *self;
170
171 self.pow2k_in_place(1);
172 *self *= x1;
173 let x2 = *self;
174
175 self.pow2k_in_place(1);
176 *self *= x1;
177 let x3 = *self;
178
179 self.pow2k_in_place(3);
180 *self *= x3;
181
182 self.pow2k_in_place(3);
183 *self *= x3;
184
185 self.pow2k_in_place(2);
186 *self *= x2;
187 let x11 = *self;
188
189 self.pow2k_in_place(11);
190 *self *= x11;
191 let x22 = *self;
192
193 self.pow2k_in_place(22);
194 *self *= x22;
195 let x44 = *self;
196
197 self.pow2k_in_place(44);
198 *self *= x44;
199 let x88 = *self;
200
201 self.pow2k_in_place(88);
202 *self *= x88;
203
204 self.pow2k_in_place(44);
205 *self *= x44;
206
207 self.pow2k_in_place(3);
208 *self *= x3;
209
210 self.pow2k_in_place(23);
211 *self *= x22;
212 self.pow2k_in_place(6);
213 *self *= x2;
214 self.pow2k_in_place(2);
215 }
216
217 pub fn sqrt_in_place(&mut self) -> bool {
218 let original = *self;
219 self.sqrt_in_place_unchecked();
220
221 let mut is_root = *self;
222 is_root.square_in_place();
223 is_root.negate_in_place(1);
224 is_root.add_in_place(&original);
225
226 is_root.normalizes_to_zero()
227 }
228 pub fn negate_in_place(&mut self, magnitude: u32) {
229 self.0.negate_in_place(magnitude);
230 }
231
232 pub fn normalize_in_place(&mut self) {
233 self.0.normalize_in_place();
234 }
235
236 pub fn is_odd(&self) -> bool {
237 self.0.is_odd()
238 }
239
240 pub fn normalizes_to_zero(&self) -> bool {
241 self.0.normalizes_to_zero()
242 }
243
244 #[inline(always)]
245 fn pow2k_in_place(&mut self, k: usize) {
246 for _ in 0..k {
247 self.square_in_place();
248 }
249 }
250
251 pub fn to_bytes(mut self) -> FieldBytes {
252 self.normalize_in_place();
253 self.0.to_bytes()
254 }
255
256 #[cfg(test)]
257 pub(crate) const fn to_storage(self) -> FieldStorage {
258 FieldStorage(self.0.to_storage())
259 }
260}
261
262impl MulAssign for FieldElement {
263 fn mul_assign(&mut self, rhs: Self) {
264 self.mul_in_place(&rhs);
265 }
266}
267
268impl MulAssign<&FieldElement> for FieldElement {
269 fn mul_assign(&mut self, rhs: &Self) {
270 self.mul_in_place(rhs);
271 }
272}
273
274impl MulAssign<u32> for FieldElement {
275 fn mul_assign(&mut self, rhs: u32) {
276 self.mul_int_in_place(rhs);
277 }
278}
279
280impl AddAssign for FieldElement {
281 fn add_assign(&mut self, rhs: Self) {
282 self.add_in_place(&rhs);
283 }
284}
285
286impl AddAssign<u32> for FieldElement {
287 fn add_assign(&mut self, rhs: u32) {
288 self.add_int_in_place(rhs);
289 }
290}
291
292impl SubAssign for FieldElement {
293 fn sub_assign(&mut self, rhs: Self) {
294 self.sub_in_place(&rhs);
295 }
296}
297
298#[derive(Debug, Clone, Copy)]
299pub(crate) struct FieldStorage(FieldStorageImpl);
300
301impl FieldStorage {
302 pub(crate) const DEFAULT: Self = Self(FieldStorageImpl::DEFAULT);
303
304 pub(crate) fn to_field_elem(self) -> FieldElement {
305 FieldElement(self.0.to_field_elem())
306 }
307}
308
309#[cfg(test)]
310impl proptest::arbitrary::Arbitrary for FieldElementConst {
311 type Parameters = ();
312
313 fn arbitrary_with(_: Self::Parameters) -> Self::Strategy {
314 use proptest::prelude::{any, Strategy};
315
316 any::<FieldElementImplConst>().prop_map(Self)
317 }
318
319 type Strategy = proptest::arbitrary::Mapped<FieldElementImplConst, Self>;
320}
321
322#[cfg(test)]
323impl PartialEq for FieldElementConst {
324 fn eq(&self, other: &Self) -> bool {
325 self.0 == other.0
326 }
327}
328
329#[cfg(test)]
330impl proptest::arbitrary::Arbitrary for FieldElement {
331 type Parameters = ();
332
333 fn arbitrary_with(_: Self::Parameters) -> Self::Strategy {
334 use proptest::prelude::{any, Strategy};
335
336 any::<FieldElementImpl>().prop_map(Self)
337 }
338
339 type Strategy = proptest::arbitrary::Mapped<FieldElementImpl, Self>;
340}
341
342#[cfg(test)]
343impl PartialEq for FieldElement {
344 fn eq(&self, other: &Self) -> bool {
345 self.0 == other.0
346 }
347}
348
349#[cfg(test)]
350mod tests {
351 use super::{FieldElement, FieldElementConst};
352 use proptest::{prop_assert, prop_assert_eq, proptest};
353
354 #[test]
355 fn storage_round_trip() {
356 proptest!(|(x: FieldElement)| {
357 prop_assert_eq!(x.to_storage().to_field_elem(), x);
358 })
359 }
360
361 #[test]
362 fn to_bytes_round_trip() {
363 proptest!(|(x: FieldElement)| {
364 let bytes: [u8; 32] = x.to_bytes().into();
365 prop_assert_eq!(
366 FieldElement::from_bytes(&bytes),
367 Some(x)
368 )
369 });
370 }
371
372 #[test]
373 fn from_bytes_round_trip() {
374 proptest!(|(bytes: [u8; 32])| {
375 prop_assert_eq!(
376 &*FieldElement::from_bytes(&bytes).unwrap().to_bytes(),
377 bytes
378 )
379 })
380 }
381
382 #[test]
383 fn test_mul() {
384 proptest!(|(x: FieldElement, y: FieldElement, z: FieldElement)| {
385 let mut a = x;
386 let mut b = y;
387 a.mul_in_place(&y);
388 b.mul_in_place(&x);
389 prop_assert_eq!(a, b);
390
391 a = x;
392 b = y;
393 a.mul_in_place(&y);
394 a.mul_in_place(&z);
395 b.mul_in_place(&z);
396 b.mul_in_place(&x);
397 prop_assert_eq!(a, b);
398
399 a = x;
400 a.mul_in_place(&FieldElement::ONE);
401 prop_assert_eq!(a, x);
402
403 a.mul_in_place(&FieldElement::ZERO);
404 prop_assert_eq!(a, FieldElement::ZERO);
405
406 a = y;
407 a.add_in_place(&z);
408 a.mul_in_place(&x);
409
410 b = x;
411 let mut c = x;
412 b.mul_in_place(&y);
413 c.mul_in_place(&z);
414 b.add_in_place(&c);
415 prop_assert_eq!(a, b);
416 });
417 }
418
419 #[test]
420 fn test_mul_const() {
421 proptest!(|(x: FieldElementConst, y: FieldElementConst, z: FieldElementConst)| {
422 prop_assert_eq!(x.mul(&y), y.mul(&x));
423 prop_assert_eq!(x.mul(&y).mul(&z), x.mul(&y.mul(&z)));
424 prop_assert_eq!(x.mul(&FieldElementConst::ONE), x);
425 prop_assert_eq!(x.mul(&FieldElementConst::ZERO), FieldElementConst::ZERO);
426
427 prop_assert_eq!(x.mul(&y.add(&z)), x.mul(&y).add(&x.mul(&z)));
428 });
429 }
430
431 #[test]
432 fn test_invert() {
433 proptest!(|(x: FieldElement)| {
434 let mut a = x;
435 a.invert_in_place();
436 a.invert_in_place();
437 prop_assert_eq!(a, x);
438
439 a.invert_in_place();
440 a.mul_in_place(&x);
441 if x.normalizes_to_zero() {
442 prop_assert_eq!(a, FieldElement::ZERO);
443 } else {
444 prop_assert_eq!(a, FieldElement::ONE);
445 }
446 })
447 }
448
449 #[test]
450 fn test_invert_const() {
451 proptest!(|(x: FieldElementConst)| {
452 prop_assert_eq!(x.invert().invert(), x);
453
454 if x.normalizes_to_zero() {
455 prop_assert_eq!(x.invert().mul(&x), FieldElementConst::ZERO);
456 } else {
457 prop_assert_eq!(x.invert().mul(&x), FieldElementConst::ONE);
458 }
459 })
460 }
461
462 #[test]
463 fn test_add() {
464 proptest!(|(x: FieldElement, y: FieldElement, z: FieldElement)| {
465 let mut a = x;
466 let mut b = y;
467 a.add_in_place(&y);
468 b.add_in_place(&x);
469 prop_assert_eq!(a, b);
470
471 a = x;
472 a.add_in_place(&FieldElement::ZERO);
473 prop_assert_eq!(a, x);
474
475 b = y;
476 a.add_in_place(&y);
477 a.add_in_place(&z);
478 b.add_in_place(&z);
479 b.add_in_place(&x);
480 prop_assert_eq!(a, b);
481
482 a = x;
483 a.negate_in_place(1);
484 a.add_in_place(&x);
485 prop_assert_eq!(a, FieldElement::ZERO);
486
487 a = x;
488 a.sub_in_place(&x);
489 prop_assert_eq!(a, FieldElement::ZERO);
490 });
491 }
492
493 #[test]
494 fn test_add_const() {
495 proptest!(|(x: FieldElementConst, y: FieldElementConst, z: FieldElementConst)| {
496 prop_assert_eq!(x.add(&y), y.add(&x));
497 prop_assert_eq!(x.add(&FieldElementConst::ZERO), x);
498 prop_assert_eq!(x.add(&y).add(&z), x.add(&y.add(&z)));
499 prop_assert_eq!(x.add(&x.negate(1)), FieldElementConst::ZERO);
500 });
501 }
502
503 #[test]
504 fn test_square() {
505 proptest!(|(x: FieldElement)| {
506 let mut x_neg = x;
507 x_neg.negate_in_place(1);
508
509 let mut a = x;
510 let mut b = x;
511 a.square_in_place();
512 b.mul_in_place(&x);
513 prop_assert_eq!(a, b);
514
515 a = x;
516 a.square_in_place();
517 a.sqrt_in_place();
518
519 prop_assert!(a == x || a == x_neg);
520
521 a = x;
522 a.sqrt_in_place();
523 a.square_in_place();
524
525 prop_assert!(a == x || a == x_neg)
526 });
527 }
528
529 #[test]
530 fn test_square_const() {
531 proptest!(|(x: FieldElementConst)| {
532 prop_assert_eq!(x.square(), x.mul(&x));
533 })
534 }
535}