sp1_hypercube/
septic_extension.rs

1//! A septic extension with an irreducible polynomial `z^7 - 3z - 5`.
2use num_bigint::BigUint;
3use num_traits::One;
4use serde::{Deserialize, Serialize};
5use slop_algebra::{
6    AbstractExtensionField, AbstractField, ExtensionField, Field, Packable, PrimeField32,
7};
8use std::{
9    array,
10    fmt::Display,
11    iter::{Product, Sum},
12    ops::{Add, AddAssign, Div, Index, IndexMut, Mul, MulAssign, Neg, Sub, SubAssign},
13};
14
15use crate::air::{SP1AirBuilder, SepticExtensionAirBuilder};
16
17/// A septic extension with an irreducible polynomial `z^7 - 3z - 5`.
18///
19/// The field can be constructed as `F_{p^7} = F_p[z]/(z^7 - 3z - 5)`.
20#[derive(
21    Debug, Clone, Copy, Default, Serialize, Deserialize, PartialEq, Eq, Hash, deepsize2::DeepSizeOf,
22)]
23#[repr(C)]
24pub struct SepticExtension<F>(pub [F; 7]);
25
26impl<F: AbstractField> AbstractField for SepticExtension<F> {
27    type F = SepticExtension<F::F>;
28
29    fn zero() -> Self {
30        SepticExtension([
31            F::zero(),
32            F::zero(),
33            F::zero(),
34            F::zero(),
35            F::zero(),
36            F::zero(),
37            F::zero(),
38        ])
39    }
40
41    fn one() -> Self {
42        SepticExtension([
43            F::one(),
44            F::zero(),
45            F::zero(),
46            F::zero(),
47            F::zero(),
48            F::zero(),
49            F::zero(),
50        ])
51    }
52
53    fn two() -> Self {
54        SepticExtension([
55            F::two(),
56            F::zero(),
57            F::zero(),
58            F::zero(),
59            F::zero(),
60            F::zero(),
61            F::zero(),
62        ])
63    }
64
65    fn neg_one() -> Self {
66        SepticExtension([
67            F::neg_one(),
68            F::zero(),
69            F::zero(),
70            F::zero(),
71            F::zero(),
72            F::zero(),
73            F::zero(),
74        ])
75    }
76
77    fn from_f(f: Self::F) -> Self {
78        SepticExtension([
79            F::from_f(f.0[0]),
80            F::from_f(f.0[1]),
81            F::from_f(f.0[2]),
82            F::from_f(f.0[3]),
83            F::from_f(f.0[4]),
84            F::from_f(f.0[5]),
85            F::from_f(f.0[6]),
86        ])
87    }
88
89    fn from_bool(b: bool) -> Self {
90        SepticExtension([
91            F::from_bool(b),
92            F::zero(),
93            F::zero(),
94            F::zero(),
95            F::zero(),
96            F::zero(),
97            F::zero(),
98        ])
99    }
100
101    fn from_canonical_u8(n: u8) -> Self {
102        SepticExtension([
103            F::from_canonical_u8(n),
104            F::zero(),
105            F::zero(),
106            F::zero(),
107            F::zero(),
108            F::zero(),
109            F::zero(),
110        ])
111    }
112
113    fn from_canonical_u16(n: u16) -> Self {
114        SepticExtension([
115            F::from_canonical_u16(n),
116            F::zero(),
117            F::zero(),
118            F::zero(),
119            F::zero(),
120            F::zero(),
121            F::zero(),
122        ])
123    }
124
125    fn from_canonical_u32(n: u32) -> Self {
126        SepticExtension([
127            F::from_canonical_u32(n),
128            F::zero(),
129            F::zero(),
130            F::zero(),
131            F::zero(),
132            F::zero(),
133            F::zero(),
134        ])
135    }
136
137    fn from_canonical_u64(n: u64) -> Self {
138        SepticExtension([
139            F::from_canonical_u64(n),
140            F::zero(),
141            F::zero(),
142            F::zero(),
143            F::zero(),
144            F::zero(),
145            F::zero(),
146        ])
147    }
148
149    fn from_canonical_usize(n: usize) -> Self {
150        SepticExtension([
151            F::from_canonical_usize(n),
152            F::zero(),
153            F::zero(),
154            F::zero(),
155            F::zero(),
156            F::zero(),
157            F::zero(),
158        ])
159    }
160
161    fn from_wrapped_u32(n: u32) -> Self {
162        SepticExtension([
163            F::from_wrapped_u32(n),
164            F::zero(),
165            F::zero(),
166            F::zero(),
167            F::zero(),
168            F::zero(),
169            F::zero(),
170        ])
171    }
172
173    fn from_wrapped_u64(n: u64) -> Self {
174        SepticExtension([
175            F::from_wrapped_u64(n),
176            F::zero(),
177            F::zero(),
178            F::zero(),
179            F::zero(),
180            F::zero(),
181            F::zero(),
182        ])
183    }
184
185    fn generator() -> Self {
186        SepticExtension([
187            F::zero(),
188            F::one(),
189            F::zero(),
190            F::zero(),
191            F::zero(),
192            F::zero(),
193            F::zero(),
194        ])
195    }
196}
197
198impl<F: Field> Field for SepticExtension<F> {
199    type Packing = Self;
200
201    fn try_inverse(&self) -> Option<Self> {
202        if self.is_zero() {
203            return None;
204        }
205        Some(self.inv())
206    }
207
208    fn order() -> BigUint {
209        F::order().pow(7)
210    }
211}
212
213impl<F: AbstractField> AbstractExtensionField<F> for SepticExtension<F> {
214    const D: usize = 7;
215
216    fn from_base(b: F) -> Self {
217        SepticExtension([b, F::zero(), F::zero(), F::zero(), F::zero(), F::zero(), F::zero()])
218    }
219
220    fn from_base_slice(bs: &[F]) -> Self {
221        SepticExtension([
222            bs[0].clone(),
223            bs[1].clone(),
224            bs[2].clone(),
225            bs[3].clone(),
226            bs[4].clone(),
227            bs[5].clone(),
228            bs[6].clone(),
229        ])
230    }
231
232    fn from_base_fn<G: FnMut(usize) -> F>(f: G) -> Self {
233        Self(array::from_fn(f))
234    }
235
236    fn as_base_slice(&self) -> &[F] {
237        self.0.as_slice()
238    }
239}
240
241impl<F: Field> ExtensionField<F> for SepticExtension<F> {
242    type ExtensionPacking = SepticExtension<F::Packing>;
243}
244
245impl<F: Field> Packable for SepticExtension<F> {}
246
247impl<F: AbstractField> Add for SepticExtension<F> {
248    type Output = Self;
249
250    fn add(self, rhs: Self) -> Self::Output {
251        let mut res = self.0;
252        for (r, rhs_val) in res.iter_mut().zip(rhs.0) {
253            *r = (*r).clone() + rhs_val;
254        }
255        Self(res)
256    }
257}
258
259impl<F: AbstractField> AddAssign for SepticExtension<F> {
260    fn add_assign(&mut self, rhs: Self) {
261        self.0[0] += rhs.0[0].clone();
262        self.0[1] += rhs.0[1].clone();
263        self.0[2] += rhs.0[2].clone();
264        self.0[3] += rhs.0[3].clone();
265        self.0[4] += rhs.0[4].clone();
266        self.0[5] += rhs.0[5].clone();
267        self.0[6] += rhs.0[6].clone();
268    }
269}
270
271impl<F: AbstractField> Sub for SepticExtension<F> {
272    type Output = Self;
273
274    fn sub(self, rhs: Self) -> Self::Output {
275        let mut res = self.0;
276        for (r, rhs_val) in res.iter_mut().zip(rhs.0) {
277            *r = (*r).clone() - rhs_val;
278        }
279        Self(res)
280    }
281}
282
283impl<F: AbstractField> SubAssign for SepticExtension<F> {
284    fn sub_assign(&mut self, rhs: Self) {
285        self.0[0] -= rhs.0[0].clone();
286        self.0[1] -= rhs.0[1].clone();
287        self.0[2] -= rhs.0[2].clone();
288        self.0[3] -= rhs.0[3].clone();
289        self.0[4] -= rhs.0[4].clone();
290        self.0[5] -= rhs.0[5].clone();
291        self.0[6] -= rhs.0[6].clone();
292    }
293}
294
295impl<F: AbstractField> Neg for SepticExtension<F> {
296    type Output = Self;
297
298    fn neg(self) -> Self::Output {
299        let mut res = self.0;
300        for r in res.iter_mut() {
301            *r = -r.clone();
302        }
303        Self(res)
304    }
305}
306
307impl<F: AbstractField> Mul for SepticExtension<F> {
308    type Output = Self;
309
310    /// The multiplication rule for `F_{p^7} = F_p[z]/(z^7 - 3z - 5)`.
311    fn mul(self, rhs: Self) -> Self::Output {
312        let mut res: [F; 13] = core::array::from_fn(|_| F::zero());
313        for i in 0..7 {
314            for j in 0..7 {
315                res[i + j] = res[i + j].clone() + self.0[i].clone() * rhs.0[j].clone();
316            }
317        }
318        let mut ret: [F; 7] = core::array::from_fn(|i| res[i].clone());
319        for i in 7..13 {
320            ret[i - 7] = ret[i - 7].clone() + res[i].clone() * F::from_canonical_u32(5);
321            ret[i - 6] = ret[i - 6].clone() + res[i].clone() * F::from_canonical_u32(3);
322        }
323        Self(ret)
324    }
325}
326
327impl<F: AbstractField> MulAssign for SepticExtension<F> {
328    fn mul_assign(&mut self, rhs: Self) {
329        let res = self.clone() * rhs;
330        *self = res;
331    }
332}
333
334impl<F: AbstractField> Product for SepticExtension<F> {
335    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
336        let one = Self::one();
337        iter.fold(one, |acc, x| acc * x)
338    }
339}
340
341impl<F: AbstractField> Sum for SepticExtension<F> {
342    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
343        let zero = Self::zero();
344        iter.fold(zero, |acc, x| acc + x)
345    }
346}
347
348impl<F: AbstractField> From<F> for SepticExtension<F> {
349    fn from(f: F) -> Self {
350        SepticExtension([f, F::zero(), F::zero(), F::zero(), F::zero(), F::zero(), F::zero()])
351    }
352}
353
354impl<F: AbstractField> Add<F> for SepticExtension<F> {
355    type Output = Self;
356
357    fn add(self, rhs: F) -> Self::Output {
358        SepticExtension([
359            self.0[0].clone() + rhs,
360            self.0[1].clone(),
361            self.0[2].clone(),
362            self.0[3].clone(),
363            self.0[4].clone(),
364            self.0[5].clone(),
365            self.0[6].clone(),
366        ])
367    }
368}
369
370impl<F: AbstractField> AddAssign<F> for SepticExtension<F> {
371    fn add_assign(&mut self, rhs: F) {
372        self.0[0] += rhs;
373    }
374}
375
376impl<F: AbstractField> Sub<F> for SepticExtension<F> {
377    type Output = Self;
378
379    fn sub(self, rhs: F) -> Self::Output {
380        self + (-rhs)
381    }
382}
383
384impl<F: AbstractField> SubAssign<F> for SepticExtension<F> {
385    fn sub_assign(&mut self, rhs: F) {
386        self.0[0] -= rhs;
387    }
388}
389
390impl<F: AbstractField> Mul<F> for SepticExtension<F> {
391    type Output = Self;
392
393    fn mul(self, rhs: F) -> Self::Output {
394        SepticExtension([
395            self.0[0].clone() * rhs.clone(),
396            self.0[1].clone() * rhs.clone(),
397            self.0[2].clone() * rhs.clone(),
398            self.0[3].clone() * rhs.clone(),
399            self.0[4].clone() * rhs.clone(),
400            self.0[5].clone() * rhs.clone(),
401            self.0[6].clone() * rhs.clone(),
402        ])
403    }
404}
405
406impl<F: AbstractField> MulAssign<F> for SepticExtension<F> {
407    fn mul_assign(&mut self, rhs: F) {
408        for i in 0..7 {
409            self.0[i] *= rhs.clone();
410        }
411    }
412}
413
414impl<F: Field> Div for SepticExtension<F> {
415    type Output = Self;
416
417    #[allow(clippy::suspicious_arithmetic_impl)]
418    fn div(self, rhs: Self) -> Self::Output {
419        self * rhs.inverse()
420    }
421}
422
423impl<F: AbstractField> Display for SepticExtension<F> {
424    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
425        write!(f, "{:?}", self.0)
426    }
427}
428
429impl<F: Field> SepticExtension<F> {
430    /// Returns the value of z^{index * p} in the [`SepticExtension`] field.
431    fn z_pow_p(index: u32) -> Self {
432        // The constants written below are specifically for the KoalaBear field.
433        debug_assert_eq!(F::order(), BigUint::from(2130706433u32));
434        if index == 0 {
435            return Self::one();
436        }
437        if index == 1 {
438            return SepticExtension([
439                F::from_canonical_u32(1272123317),
440                F::from_canonical_u32(1950759909),
441                F::from_canonical_u32(1879852731),
442                F::from_canonical_u32(746569225),
443                F::from_canonical_u32(180350946),
444                F::from_canonical_u32(1600835585),
445                F::from_canonical_u32(333893434),
446            ]);
447        }
448        if index == 2 {
449            return SepticExtension([
450                F::from_canonical_u32(129050189),
451                F::from_canonical_u32(1749509219),
452                F::from_canonical_u32(983995729),
453                F::from_canonical_u32(711096547),
454                F::from_canonical_u32(1505254548),
455                F::from_canonical_u32(639452798),
456                F::from_canonical_u32(68186395),
457            ]);
458        }
459        if index == 3 {
460            return SepticExtension([
461                F::from_canonical_u32(1911662442),
462                F::from_canonical_u32(1095215454),
463                F::from_canonical_u32(1794102427),
464                F::from_canonical_u32(1173566779),
465                F::from_canonical_u32(140526665),
466                F::from_canonical_u32(110899104),
467                F::from_canonical_u32(1387282150),
468            ]);
469        }
470        if index == 4 {
471            return SepticExtension([
472                F::from_canonical_u32(1366416596),
473                F::from_canonical_u32(1212861),
474                F::from_canonical_u32(2104391040),
475                F::from_canonical_u32(1447859676),
476                F::from_canonical_u32(308944373),
477                F::from_canonical_u32(106444152),
478                F::from_canonical_u32(1362577042),
479            ]);
480        }
481        if index == 5 {
482            return SepticExtension([
483                F::from_canonical_u32(1411781189),
484                F::from_canonical_u32(1580508159),
485                F::from_canonical_u32(1332301780),
486                F::from_canonical_u32(1528790701),
487                F::from_canonical_u32(380217034),
488                F::from_canonical_u32(1752756730),
489                F::from_canonical_u32(989817517),
490            ]);
491        }
492        if index == 6 {
493            return SepticExtension([
494                F::from_canonical_u32(37669840),
495                F::from_canonical_u32(439102875),
496                F::from_canonical_u32(410223214),
497                F::from_canonical_u32(964813232),
498                F::from_canonical_u32(1250258104),
499                F::from_canonical_u32(877333757),
500                F::from_canonical_u32(222095778),
501            ]);
502        }
503        unreachable!();
504    }
505
506    /// Returns the value of z^{index * p^2} in the [`SepticExtension`] field.
507    fn z_pow_p2(index: u32) -> Self {
508        // The constants written below are specifically for the KoalaBear field.
509        debug_assert_eq!(F::order(), BigUint::from(2130706433u32));
510        if index == 0 {
511            return Self::one();
512        }
513        if index == 1 {
514            return SepticExtension([
515                F::from_canonical_u32(1330073564),
516                F::from_canonical_u32(1724372201),
517                F::from_canonical_u32(942213154),
518                F::from_canonical_u32(258987814),
519                F::from_canonical_u32(1836986639),
520                F::from_canonical_u32(566030553),
521                F::from_canonical_u32(2086945921),
522            ]);
523        }
524        if index == 2 {
525            return SepticExtension([
526                F::from_canonical_u32(473977877),
527                F::from_canonical_u32(99096011),
528                F::from_canonical_u32(1919717963),
529                F::from_canonical_u32(733784355),
530                F::from_canonical_u32(1167998744),
531                F::from_canonical_u32(19619652),
532                F::from_canonical_u32(1354518805),
533            ]);
534        }
535        if index == 3 {
536            return SepticExtension([
537                F::from_canonical_u32(1040563478),
538                F::from_canonical_u32(1866766699),
539                F::from_canonical_u32(1875293643),
540                F::from_canonical_u32(846885082),
541                F::from_canonical_u32(1921678452),
542                F::from_canonical_u32(2127718474),
543                F::from_canonical_u32(1489297699),
544            ]);
545        }
546        if index == 4 {
547            return SepticExtension([
548                F::from_canonical_u32(1350284585),
549                F::from_canonical_u32(1583164394),
550                F::from_canonical_u32(512913106),
551                F::from_canonical_u32(1818487640),
552                F::from_canonical_u32(2116891899),
553                F::from_canonical_u32(318922921),
554                F::from_canonical_u32(1013732863),
555            ]);
556        }
557        if index == 5 {
558            return SepticExtension([
559                F::from_canonical_u32(887772098),
560                F::from_canonical_u32(1971095075),
561                F::from_canonical_u32(843183752),
562                F::from_canonical_u32(711838602),
563                F::from_canonical_u32(1717807390),
564                F::from_canonical_u32(521017530),
565                F::from_canonical_u32(1548716569),
566            ]);
567        }
568        if index == 6 {
569            return SepticExtension([
570                F::from_canonical_u32(372606377),
571                F::from_canonical_u32(357514301),
572                F::from_canonical_u32(335089633),
573                F::from_canonical_u32(330400379),
574                F::from_canonical_u32(1545190367),
575                F::from_canonical_u32(1813349020),
576                F::from_canonical_u32(1393941056),
577            ]);
578        }
579        unreachable!();
580    }
581
582    #[must_use]
583    fn frobenius(&self) -> Self {
584        let mut result = Self::zero();
585        result += self.0[0];
586        result += Self::z_pow_p(1) * self.0[1];
587        result += Self::z_pow_p(2) * self.0[2];
588        result += Self::z_pow_p(3) * self.0[3];
589        result += Self::z_pow_p(4) * self.0[4];
590        result += Self::z_pow_p(5) * self.0[5];
591        result += Self::z_pow_p(6) * self.0[6];
592        result
593    }
594
595    #[must_use]
596    fn double_frobenius(&self) -> Self {
597        let mut result = Self::zero();
598        result += self.0[0];
599        result += Self::z_pow_p2(1) * self.0[1];
600        result += Self::z_pow_p2(2) * self.0[2];
601        result += Self::z_pow_p2(3) * self.0[3];
602        result += Self::z_pow_p2(4) * self.0[4];
603        result += Self::z_pow_p2(5) * self.0[5];
604        result += Self::z_pow_p2(6) * self.0[6];
605        result
606    }
607
608    #[must_use]
609    fn pow_r_1(&self) -> Self {
610        let base = self.frobenius() * self.double_frobenius();
611        let base_p2 = base.double_frobenius();
612        let base_p4 = base_p2.double_frobenius();
613        base * base_p2 * base_p4
614    }
615
616    #[must_use]
617    fn inv(&self) -> Self {
618        let pow_r_1 = self.pow_r_1();
619        let pow_r = pow_r_1 * *self;
620        pow_r_1 * pow_r.0[0].inverse()
621    }
622
623    fn is_square(&self) -> (F, bool) {
624        let pow_r_1 = self.pow_r_1();
625        let pow_r = pow_r_1 * *self;
626        let exp = (F::order() - BigUint::one()) / BigUint::from(2u8);
627        let exp = exp.to_u64_digits()[0];
628
629        (pow_r.0[0], pow_r.0[0].exp_u64(exp) == F::one())
630    }
631
632    /// Computes the square root of the septic field extension element.
633    /// Returns None if the element is not a square, and Some(result) if it is a square.
634    pub fn sqrt(&self) -> Option<Self> {
635        let n = *self;
636
637        if n == Self::zero() || n == Self::one() {
638            return Some(n);
639        }
640
641        let (numerator, is_square) = n.is_square();
642
643        if !is_square {
644            return None;
645        }
646
647        let mut n_iter = n;
648        let mut n_power = n;
649        for i in 1..30 {
650            n_iter *= n_iter;
651            if i >= 23 {
652                n_power *= n_iter;
653            }
654        }
655
656        let mut n_frobenius = n_power.frobenius();
657        let mut denominator = n_frobenius;
658
659        n_frobenius = n_frobenius.double_frobenius();
660        denominator *= n_frobenius;
661        n_frobenius = n_frobenius.double_frobenius();
662        denominator *= n_frobenius;
663        denominator *= n;
664
665        let base = numerator.inverse();
666        let g = F::generator();
667        let mut a = F::one();
668        let mut nonresidue = F::one() - base;
669        let legendre_exp = (F::order() - BigUint::one()) / BigUint::from(2u8);
670
671        while nonresidue.exp_u64(legendre_exp.to_u64_digits()[0]) == F::one() {
672            a *= g;
673            nonresidue = a.square() - base;
674        }
675
676        let order = F::order();
677        let cipolla_pow = (&order + BigUint::one()) / BigUint::from(2u8);
678        let mut x = CipollaExtension::new(a, F::one());
679        x = x.pow(&cipolla_pow, nonresidue);
680
681        Some(denominator * x.real)
682    }
683}
684
685impl<F: PrimeField32> SepticExtension<F> {
686    /// Returns whether the extension field element viewed as an y-coordinate of a digest represents
687    /// a receive interaction.
688    pub fn is_receive(&self) -> bool {
689        1 <= self.0[6].as_canonical_u32() && self.0[6].as_canonical_u32() <= 63 * (1 << 24)
690    }
691
692    /// Returns whether the extension field element viewed as an y-coordinate of a digest represents
693    /// a send interaction.
694    pub fn is_send(&self) -> bool {
695        F::ORDER_U32 - 63 * (1 << 24) <= self.0[6].as_canonical_u32()
696            && self.0[6].as_canonical_u32() <= (F::ORDER_U32 - 1)
697    }
698
699    /// Returns whether the extension field element viewed as an y-coordinate of a digest cannot
700    /// represent anything.
701    pub fn is_exception(&self) -> bool {
702        self.0[6].as_canonical_u32() == 0
703            || (63 * (1 << 24) < self.0[6].as_canonical_u32()
704                && self.0[6].as_canonical_u32() < F::ORDER_U32 - 63 * (1 << 24))
705    }
706}
707
708/// Extension field for Cipolla's algorithm, taken from <https://github.com/Plonky3/Plonky3/pull/439/files>.
709#[derive(Clone, Copy, Debug)]
710struct CipollaExtension<F: Field> {
711    real: F,
712    imag: F,
713}
714
715impl<F: Field> CipollaExtension<F> {
716    fn new(real: F, imag: F) -> Self {
717        Self { real, imag }
718    }
719
720    fn one() -> Self {
721        Self::new(F::one(), F::zero())
722    }
723
724    fn mul_ext(&self, other: Self, nonresidue: F) -> Self {
725        Self::new(
726            self.real * other.real + nonresidue * self.imag * other.imag,
727            self.real * other.imag + self.imag * other.real,
728        )
729    }
730
731    fn pow(&self, exp: &BigUint, nonresidue: F) -> Self {
732        let mut result = Self::one();
733        let mut base = *self;
734        let bits = exp.bits();
735
736        for i in 0..bits {
737            if exp.bit(i) {
738                result = result.mul_ext(base, nonresidue);
739            }
740            base = base.mul_ext(base, nonresidue);
741        }
742        result
743    }
744}
745
746/// A block of columns for septic extension.
747#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
748#[repr(C)]
749pub struct SepticBlock<T>(pub [T; 7]);
750
751impl<T> SepticBlock<T> {
752    /// Maps a `SepticBlock<T>` to `SepticBlock<U>` based on a map from `T` to `U`.
753    pub fn map<F, U>(self, f: F) -> SepticBlock<U>
754    where
755        F: FnMut(T) -> U,
756    {
757        SepticBlock(self.0.map(f))
758    }
759
760    /// A function similar to `core:array::from_fn`.
761    pub fn from_base_fn<G: FnMut(usize) -> T>(f: G) -> Self {
762        Self(array::from_fn(f))
763    }
764}
765
766impl<T: Clone> SepticBlock<T> {
767    /// Takes a `SepticBlock` into a `SepticExtension` of expressions.
768    pub fn as_extension<AB: SepticExtensionAirBuilder<Var = T>>(
769        &self,
770    ) -> SepticExtension<AB::Expr> {
771        let arr: [AB::Expr; 7] = self.0.clone().map(|x| AB::Expr::zero() + x);
772        SepticExtension(arr)
773    }
774
775    /// Takes a single expression into a `SepticExtension` of expressions.
776    pub fn as_extension_from_base<AB: SP1AirBuilder<Var = T>>(
777        &self,
778        base: AB::Expr,
779    ) -> SepticExtension<AB::Expr> {
780        let mut arr: [AB::Expr; 7] = self.0.clone().map(|_| AB::Expr::zero());
781        arr[0] = base;
782
783        SepticExtension(arr)
784    }
785}
786
787impl<T> From<[T; 7]> for SepticBlock<T> {
788    fn from(arr: [T; 7]) -> Self {
789        Self(arr)
790    }
791}
792
793impl<T: AbstractField> From<T> for SepticBlock<T> {
794    fn from(value: T) -> Self {
795        Self([value, T::zero(), T::zero(), T::zero(), T::zero(), T::zero(), T::zero()])
796    }
797}
798
799impl<T: Copy> From<&[T]> for SepticBlock<T> {
800    fn from(slice: &[T]) -> Self {
801        let arr: [T; 7] = slice.try_into().unwrap();
802        Self(arr)
803    }
804}
805
806impl<T, I> Index<I> for SepticBlock<T>
807where
808    [T]: Index<I>,
809{
810    type Output = <[T] as Index<I>>::Output;
811
812    #[inline]
813    fn index(&self, index: I) -> &Self::Output {
814        Index::index(&self.0, index)
815    }
816}
817
818impl<T, I> IndexMut<I> for SepticBlock<T>
819where
820    [T]: IndexMut<I>,
821{
822    #[inline]
823    fn index_mut(&mut self, index: I) -> &mut Self::Output {
824        IndexMut::index_mut(&mut self.0, index)
825    }
826}
827
828impl<T> IntoIterator for SepticBlock<T> {
829    type Item = T;
830    type IntoIter = std::array::IntoIter<T, 7>;
831
832    fn into_iter(self) -> Self::IntoIter {
833        self.0.into_iter()
834    }
835}
836
837#[cfg(test)]
838mod tests {
839    #![allow(clippy::print_stdout)]
840
841    use sp1_primitives::SP1Field;
842
843    use super::*;
844
845    #[test]
846    fn test_mul() {
847        let a: SepticExtension<SP1Field> = SepticExtension::from_canonical_u32(1);
848        let b: SepticExtension<SP1Field> = SepticExtension::from_canonical_u32(2);
849        let c = a * b;
850        println!("{c}");
851    }
852
853    #[test]
854    fn test_inv() {
855        for i in 0..256 {
856            let a: SepticExtension<SP1Field> = SepticExtension([
857                SP1Field::from_canonical_u32(i + 3),
858                SP1Field::from_canonical_u32(2 * i + 6),
859                SP1Field::from_canonical_u32(5 * i + 17),
860                SP1Field::from_canonical_u32(6 * i + 91),
861                SP1Field::from_canonical_u32(8 * i + 37),
862                SP1Field::from_canonical_u32(11 * i + 35),
863                SP1Field::from_canonical_u32(14 * i + 33),
864            ]);
865            let b = a.inv();
866            assert_eq!(a * b, SepticExtension::<SP1Field>::one());
867        }
868    }
869
870    #[test]
871    fn test_legendre() {
872        let a: SepticExtension<SP1Field> = SepticExtension::generator();
873        let mut b = SepticExtension::<SP1Field>::one();
874        for i in 1..256 {
875            b *= a;
876            let (_, c) = b.is_square();
877            assert!(c == (i % 2 == 0));
878        }
879    }
880
881    #[test]
882    fn test_sqrt() {
883        for i in 0..256 {
884            let a: SepticExtension<SP1Field> = SepticExtension([
885                SP1Field::from_canonical_u32(i + 3),
886                SP1Field::from_canonical_u32(2 * i + 6),
887                SP1Field::from_canonical_u32(5 * i + 17),
888                SP1Field::from_canonical_u32(6 * i + 91),
889                SP1Field::from_canonical_u32(8 * i + 37),
890                SP1Field::from_canonical_u32(11 * i + 35),
891                SP1Field::from_canonical_u32(14 * i + 33),
892            ]);
893            let b = a * a;
894            let recovered_a = b.sqrt().unwrap();
895            assert_eq!(recovered_a * recovered_a, b);
896        }
897        let mut b = SepticExtension::<SP1Field>::one();
898        for i in 1..256 {
899            let a: SepticExtension<SP1Field> = SepticExtension::generator();
900            b *= a;
901            let c = b.sqrt();
902            if i % 2 == 1 {
903                assert!(c.is_none());
904            } else {
905                let c = c.unwrap();
906                assert_eq!(c * c, b);
907            }
908        }
909    }
910}
sp1_hypercube/septic_extension.rs

sp1_hypercube/
septic_extension.rs
