halo2curves_axiom/pluto_eris/fields/
mod.rs

Help
1pub mod fp;
2pub mod fp12;
3pub mod fp2;
4pub mod fp6;
5pub mod fq;
6
7#[macro_export]
8macro_rules! impl_from_u64_7_limbs {
9    ($field:ident, $r2:ident) => {
10        impl From<u64> for $field {
11            fn from(val: u64) -> $field {
12                $field([val, 0, 0, 0, 0, 0, 0]) * $r2
13            }
14        }
15    };
16}
17
18#[macro_export]
19macro_rules! field_common_7_limbs {
20    (
21        $field:ident,
22        $field_repr:ident,
23        $modulus:ident,
24        $inv:ident,
25        $modulus_str:ident,
26        $two_inv:ident,
27        $root_of_unity_inv:ident,
28        $delta:ident,
29        $zeta:ident,
30        $r:ident,
31        $r2:ident,
32        $r3:ident
33    ) => {
34        impl $field {
35            /// Returns zero, the additive identity.
36            #[inline]
37            pub const fn zero() -> $field {
38                $field([0, 0, 0, 0, 0, 0, 0])
39            }
40
41            /// Returns one, the multiplicative identity.
42            #[inline]
43            pub const fn one() -> $field {
44                $r
45            }
46
47            // Returns the Jacobi symbol, where the numerator and denominator
48            // are the element and the characteristic of the field, respectively.
49            // The Jacobi symbol is applicable to odd moduli
50            // while the Legendre symbol is applicable to prime moduli.
51            // They are equivalent for prime moduli.
52            #[inline(always)]
53            pub fn jacobi(&self) -> i64 {
54                $crate::ff_ext::jacobi::jacobi::<8>(&self.0, &$modulus.0)
55            }
56
57            fn from_u512(limbs: [u64; 8]) -> $field {
58                // We reduce an arbitrary 512-bit number by decomposing it into two 256-bit digits
59                // with the higher bits multiplied by 2^256. Thus, we perform two reductions
60                //
61                // 1. the lower bits are multiplied by R^2, as normal
62                // 2. the upper bits are multiplied by R^2 * 2^256 = R^3
63                //
64                // and computing their sum in the field. It remains to see that arbitrary 256-bit
65                // numbers can be placed into Montgomery form safely using the reduction. The
66                // reduction works so long as the product is less than R=2^256 multiplied by
67                // the modulus. This holds because for any `c` smaller than the modulus, we have
68                // that (2^256 - 1)*c is an acceptable product for the reduction. Therefore, the
69                // reduction always works so long as `c` is in the field; in this case it is either the
70                // constant `R2` or `R3`.
71                let d0 = $field([
72                    limbs[0], limbs[1], limbs[2], limbs[3], limbs[4], limbs[5], limbs[6],
73                ]);
74                let d1 = $field([limbs[7], 0u64, 0u64, 0u64, 0u64, 0u64, 0u64]);
75                // Convert to Montgomery form
76                d0 * $r2 + d1 * $r3
77            }
78
79            /// Converts from an integer represented in little endian
80            /// into its (congruent) `$field` representation.
81            pub const fn from_raw(val: [u64; 7]) -> Self {
82                #[cfg(feature = "asm")]
83                {
84                    let (r0, carry) = mac(0, val[0], $r2.0[0], 0);
85                    let (r1, carry) = mac(0, val[0], $r2.0[1], carry);
86                    let (r2, carry) = mac(0, val[0], $r2.0[2], carry);
87                    let (r3, carry) = mac(0, val[0], $r2.0[3], carry);
88                    let (r4, carry) = mac(0, val[0], $r2.0[4], carry);
89                    let (r5, carry) = mac(0, val[0], $r2.0[5], carry);
90                    let (r6, r7) = mac(0, val[0], $r2.0[6], carry);
91
92                    let (r1, carry) = mac(r1, val[1], $r2.0[0], 0);
93                    let (r2, carry) = mac(r2, val[1], $r2.0[1], carry);
94                    let (r3, carry) = mac(r3, val[1], $r2.0[2], carry);
95                    let (r4, carry) = mac(r4, val[1], $r2.0[3], carry);
96                    let (r5, carry) = mac(r5, val[1], $r2.0[4], carry);
97                    let (r6, carry) = mac(r6, val[1], $r2.0[5], carry);
98                    let (r7, r8) = mac(r7, val[1], $r2.0[6], carry);
99
100                    let (r2, carry) = mac(r2, val[2], $r2.0[0], 0);
101                    let (r3, carry) = mac(r3, val[2], $r2.0[1], carry);
102                    let (r4, carry) = mac(r4, val[2], $r2.0[2], carry);
103                    let (r5, carry) = mac(r5, val[2], $r2.0[3], carry);
104                    let (r6, carry) = mac(r6, val[2], $r2.0[4], carry);
105                    let (r7, carry) = mac(r7, val[2], $r2.0[5], carry);
106                    let (r8, r9) = mac(r8, val[2], $r2.0[6], carry);
107
108                    let (r3, carry) = mac(r3, val[3], $r2.0[0], 0);
109                    let (r4, carry) = mac(r4, val[3], $r2.0[1], carry);
110                    let (r5, carry) = mac(r5, val[3], $r2.0[2], carry);
111                    let (r6, carry) = mac(r6, val[3], $r2.0[3], carry);
112                    let (r7, carry) = mac(r7, val[3], $r2.0[4], carry);
113                    let (r8, carry) = mac(r8, val[3], $r2.0[5], carry);
114                    let (r9, r10) = mac(r9, val[3], $r2.0[6], carry);
115
116                    let (r4, carry) = mac(r4, val[4], $r2.0[0], 0);
117                    let (r5, carry) = mac(r5, val[4], $r2.0[1], carry);
118                    let (r6, carry) = mac(r6, val[4], $r2.0[2], carry);
119                    let (r7, carry) = mac(r7, val[4], $r2.0[3], carry);
120                    let (r8, carry) = mac(r8, val[4], $r2.0[4], carry);
121                    let (r9, carry) = mac(r9, val[4], $r2.0[5], carry);
122                    let (r10, r11) = mac(r10, val[4], $r2.0[6], carry);
123
124                    let (r5, carry) = mac(r5, val[5], $r2.0[0], 0);
125                    let (r6, carry) = mac(r6, val[5], $r2.0[1], carry);
126                    let (r7, carry) = mac(r7, val[5], $r2.0[2], carry);
127                    let (r8, carry) = mac(r8, val[5], $r2.0[3], carry);
128                    let (r9, carry) = mac(r9, val[5], $r2.0[4], carry);
129                    let (r10, carry) = mac(r10, val[5], $r2.0[5], carry);
130                    let (r11, r12) = mac(r11, val[5], $r2.0[6], carry);
131
132                    let (r6, carry) = mac(r6, val[6], $r2.0[0], 0);
133                    let (r7, carry) = mac(r7, val[6], $r2.0[1], carry);
134                    let (r8, carry) = mac(r8, val[6], $r2.0[2], carry);
135                    let (r9, carry) = mac(r9, val[6], $r2.0[3], carry);
136                    let (r10, carry) = mac(r10, val[6], $r2.0[4], carry);
137                    let (r11, carry) = mac(r11, val[6], $r2.0[5], carry);
138                    let (r12, r13) = mac(r12, val[6], $r2.0[6], carry);
139
140                    // Montgomery reduction
141                    let k = r0.wrapping_mul($inv);
142                    let (_, carry) = mac(r0, k, $modulus.0[0], 0);
143                    let (r1, carry) = mac(r1, k, $modulus.0[1], carry);
144                    let (r2, carry) = mac(r2, k, $modulus.0[2], carry);
145                    let (r3, carry) = mac(r3, k, $modulus.0[3], carry);
146                    let (r4, carry) = mac(r4, k, $modulus.0[4], carry);
147                    let (r5, carry) = mac(r5, k, $modulus.0[5], carry);
148                    let (r6, carry) = mac(r6, k, $modulus.0[6], carry);
149                    let (r7, carry2) = adc(r7, 0, carry);
150
151                    let k = r1.wrapping_mul($inv);
152                    let (_, carry) = mac(r1, k, $modulus.0[0], 0);
153                    let (r2, carry) = mac(r2, k, $modulus.0[1], carry);
154                    let (r3, carry) = mac(r3, k, $modulus.0[2], carry);
155                    let (r4, carry) = mac(r4, k, $modulus.0[3], carry);
156                    let (r5, carry) = mac(r5, k, $modulus.0[4], carry);
157                    let (r6, carry) = mac(r6, k, $modulus.0[5], carry);
158                    let (r7, carry) = mac(r7, k, $modulus.0[6], carry);
159                    let (r8, carry2) = adc(r8, carry2, carry);
160
161                    let k = r2.wrapping_mul($inv);
162                    let (_, carry) = mac(r2, k, $modulus.0[0], 0);
163                    let (r3, carry) = mac(r3, k, $modulus.0[1], carry);
164                    let (r4, carry) = mac(r4, k, $modulus.0[2], carry);
165                    let (r5, carry) = mac(r5, k, $modulus.0[3], carry);
166                    let (r6, carry) = mac(r6, k, $modulus.0[4], carry);
167                    let (r7, carry) = mac(r7, k, $modulus.0[5], carry);
168                    let (r8, carry) = mac(r8, k, $modulus.0[6], carry);
169                    let (r9, carry2) = adc(r9, carry2, carry);
170
171                    let k = r3.wrapping_mul($inv);
172                    let (_, carry) = mac(r3, k, $modulus.0[0], 0);
173                    let (r4, carry) = mac(r4, k, $modulus.0[1], carry);
174                    let (r5, carry) = mac(r5, k, $modulus.0[2], carry);
175                    let (r6, carry) = mac(r6, k, $modulus.0[3], carry);
176                    let (r7, carry) = mac(r7, k, $modulus.0[4], carry);
177                    let (r8, carry) = mac(r8, k, $modulus.0[5], carry);
178                    let (r9, carry) = mac(r9, k, $modulus.0[6], carry);
179                    let (r10, carry2) = adc(r10, carry2, carry);
180
181                    let k = r4.wrapping_mul($inv);
182                    let (_, carry) = mac(r4, k, $modulus.0[0], 0);
183                    let (r5, carry) = mac(r5, k, $modulus.0[1], carry);
184                    let (r6, carry) = mac(r6, k, $modulus.0[2], carry);
185                    let (r7, carry) = mac(r7, k, $modulus.0[3], carry);
186                    let (r8, carry) = mac(r8, k, $modulus.0[4], carry);
187                    let (r9, carry) = mac(r9, k, $modulus.0[5], carry);
188                    let (r10, carry) = mac(r10, k, $modulus.0[6], carry);
189                    let (r11, carry2) = adc(r11, carry2, carry);
190
191                    let k = r5.wrapping_mul($inv);
192                    let (_, carry) = mac(r5, k, $modulus.0[0], 0);
193                    let (r6, carry) = mac(r6, k, $modulus.0[1], carry);
194                    let (r7, carry) = mac(r7, k, $modulus.0[2], carry);
195                    let (r8, carry) = mac(r8, k, $modulus.0[3], carry);
196                    let (r9, carry) = mac(r9, k, $modulus.0[4], carry);
197                    let (r10, carry) = mac(r10, k, $modulus.0[5], carry);
198                    let (r11, carry) = mac(r11, k, $modulus.0[6], carry);
199                    let (r12, carry2) = adc(r12, carry2, carry);
200
201                    let k = r6.wrapping_mul($inv);
202                    let (_, carry) = mac(r6, k, $modulus.0[0], 0);
203                    let (r7, carry) = mac(r7, k, $modulus.0[1], carry);
204                    let (r8, carry) = mac(r8, k, $modulus.0[2], carry);
205                    let (r9, carry) = mac(r9, k, $modulus.0[3], carry);
206                    let (r10, carry) = mac(r10, k, $modulus.0[4], carry);
207                    let (r11, carry) = mac(r11, k, $modulus.0[5], carry);
208                    let (r12, carry) = mac(r12, k, $modulus.0[6], carry);
209                    let (r13, carry2) = adc(r13, carry2, carry);
210
211                    // Result may be within MODULUS of the correct value
212                    let (d0, borrow) = sbb(r7, $modulus.0[0], 0);
213                    let (d1, borrow) = sbb(r8, $modulus.0[1], borrow);
214                    let (d2, borrow) = sbb(r9, $modulus.0[2], borrow);
215                    let (d3, borrow) = sbb(r10, $modulus.0[3], borrow);
216                    let (d4, borrow) = sbb(r11, $modulus.0[4], borrow);
217                    let (d5, borrow) = sbb(r12, $modulus.0[5], borrow);
218                    let (d6, borrow) = sbb(r13, $modulus.0[6], borrow);
219                    let (_, borrow) = sbb(carry2, 0, borrow);
220                    let (d0, carry) = adc(d0, $modulus.0[0] & borrow, 0);
221                    let (d1, carry) = adc(d1, $modulus.0[1] & borrow, carry);
222                    let (d2, carry) = adc(d2, $modulus.0[2] & borrow, carry);
223                    let (d3, carry) = adc(d3, $modulus.0[3] & borrow, carry);
224                    let (d4, carry) = adc(d4, $modulus.0[4] & borrow, carry);
225                    let (d5, carry) = adc(d5, $modulus.0[5] & borrow, carry);
226                    let (d6, _) = adc(d6, $modulus.0[6] & borrow, carry);
227
228                    $field([d0, d1, d2, d3, d4, d5, d6])
229                }
230                #[cfg(not(feature = "asm"))]
231                {
232                    (&$field(val)).mul(&$r2)
233                }
234            }
235
236            /// Attempts to convert a little-endian byte representation of
237            /// a scalar into a `Fr`, failing if the input is not canonical.
238            pub fn from_bytes(bytes: &[u8; 56]) -> CtOption<$field> {
239                <Self as ff::PrimeField>::from_repr($field_repr { repr: *bytes })
240            }
241
242            /// Converts an element of `Fr` into a byte representation in
243            /// little-endian byte order.
244            pub fn to_bytes(&self) -> [u8; 56] {
245                <Self as ff::PrimeField>::to_repr(self).repr
246            }
247
248            /// Lexicographic comparison of Montgomery forms.
249            #[inline(always)]
250            const fn is_less_than(x: &[u64; 7], y: &[u64; 7]) -> bool {
251                let (_, borrow) = sbb(x[0], y[0], 0);
252                let (_, borrow) = sbb(x[1], y[1], borrow);
253                let (_, borrow) = sbb(x[2], y[2], borrow);
254                let (_, borrow) = sbb(x[3], y[3], borrow);
255                let (_, borrow) = sbb(x[4], y[4], borrow);
256                let (_, borrow) = sbb(x[5], y[5], borrow);
257                let (_, borrow) = sbb(x[6], y[6], borrow);
258                borrow >> 63 == 1
259            }
260        }
261
262        impl fmt::Debug for $field {
263            fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
264                let tmp = self.to_repr();
265                write!(f, "0x")?;
266                for &b in tmp.iter().rev() {
267                    write!(f, "{:02x}", b)?;
268                }
269                Ok(())
270            }
271        }
272
273        impl Default for $field {
274            #[inline]
275            fn default() -> Self {
276                Self::zero()
277            }
278        }
279
280        impl From<bool> for $field {
281            fn from(bit: bool) -> $field {
282                if bit {
283                    $field::one()
284                } else {
285                    $field::zero()
286                }
287            }
288        }
289
290        impl ConstantTimeEq for $field {
291            fn ct_eq(&self, other: &Self) -> Choice {
292                self.0[0].ct_eq(&other.0[0])
293                    & self.0[1].ct_eq(&other.0[1])
294                    & self.0[2].ct_eq(&other.0[2])
295                    & self.0[3].ct_eq(&other.0[3])
296                    & self.0[4].ct_eq(&other.0[4])
297                    & self.0[5].ct_eq(&other.0[5])
298                    & self.0[6].ct_eq(&other.0[6])
299            }
300        }
301
302        impl core::cmp::Ord for $field {
303            fn cmp(&self, other: &Self) -> core::cmp::Ordering {
304                let left = self.to_repr();
305                let right = other.to_repr();
306                left.iter()
307                    .zip(right.iter())
308                    .rev()
309                    .find_map(|(left_byte, right_byte)| match left_byte.cmp(right_byte) {
310                        core::cmp::Ordering::Equal => None,
311                        res => Some(res),
312                    })
313                    .unwrap_or(core::cmp::Ordering::Equal)
314            }
315        }
316
317        impl core::cmp::PartialOrd for $field {
318            fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
319                Some(self.cmp(other))
320            }
321        }
322
323        impl ConditionallySelectable for $field {
324            fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
325                $field([
326                    u64::conditional_select(&a.0[0], &b.0[0], choice),
327                    u64::conditional_select(&a.0[1], &b.0[1], choice),
328                    u64::conditional_select(&a.0[2], &b.0[2], choice),
329                    u64::conditional_select(&a.0[3], &b.0[3], choice),
330                    u64::conditional_select(&a.0[4], &b.0[4], choice),
331                    u64::conditional_select(&a.0[5], &b.0[5], choice),
332                    u64::conditional_select(&a.0[6], &b.0[6], choice),
333                ])
334            }
335        }
336
337        impl<'a> Neg for &'a $field {
338            type Output = $field;
339
340            #[inline]
341            fn neg(self) -> $field {
342                self.neg()
343            }
344        }
345
346        impl Neg for $field {
347            type Output = $field;
348
349            #[inline]
350            fn neg(self) -> $field {
351                -&self
352            }
353        }
354
355        impl<'a, 'b> Sub<&'b $field> for &'a $field {
356            type Output = $field;
357
358            #[inline]
359            fn sub(self, rhs: &'b $field) -> $field {
360                self.sub(rhs)
361            }
362        }
363
364        impl<'a, 'b> Add<&'b $field> for &'a $field {
365            type Output = $field;
366
367            #[inline]
368            fn add(self, rhs: &'b $field) -> $field {
369                self.add(rhs)
370            }
371        }
372
373        impl<'a, 'b> Mul<&'b $field> for &'a $field {
374            type Output = $field;
375
376            #[inline]
377            fn mul(self, rhs: &'b $field) -> $field {
378                self.mul(rhs)
379            }
380        }
381
382        impl From<$field> for [u8; 56] {
383            fn from(value: $field) -> [u8; 56] {
384                value.to_repr().repr
385            }
386        }
387
388        impl<'a> From<&'a $field> for [u8; 56] {
389            fn from(value: &'a $field) -> [u8; 56] {
390                value.to_repr().repr
391            }
392        }
393
394        impl $crate::serde::SerdeObject for $field {
395            fn from_raw_bytes_unchecked(bytes: &[u8]) -> Self {
396                debug_assert_eq!(bytes.len(), 56);
397                let inner = [0, 8, 16, 24, 32, 40, 48]
398                    .map(|i| u64::from_le_bytes(bytes[i..i + 8].try_into().unwrap()));
399                Self(inner)
400            }
401            fn from_raw_bytes(bytes: &[u8]) -> Option<Self> {
402                if bytes.len() != 56 {
403                    return None;
404                }
405                let elt = Self::from_raw_bytes_unchecked(bytes);
406                Self::is_less_than(&elt.0, &$modulus.0).then(|| elt)
407            }
408            fn to_raw_bytes(&self) -> Vec<u8> {
409                let mut res = Vec::with_capacity(56);
410                for limb in self.0.iter() {
411                    res.extend_from_slice(&limb.to_le_bytes());
412                }
413                res
414            }
415            fn read_raw_unchecked<R: std::io::Read>(reader: &mut R) -> Self {
416                let inner = [(); 7].map(|_| {
417                    let mut buf = [0; 8];
418                    reader.read_exact(&mut buf).unwrap();
419                    u64::from_le_bytes(buf)
420                });
421                Self(inner)
422            }
423            fn read_raw<R: std::io::Read>(reader: &mut R) -> std::io::Result<Self> {
424                let mut inner = [0u64; 7];
425                for limb in inner.iter_mut() {
426                    let mut buf = [0; 8];
427                    reader.read_exact(&mut buf)?;
428                    *limb = u64::from_le_bytes(buf);
429                }
430                let elt = Self(inner);
431                Self::is_less_than(&elt.0, &$modulus.0)
432                    .then(|| elt)
433                    .ok_or_else(|| {
434                        std::io::Error::new(
435                            std::io::ErrorKind::InvalidData,
436                            "input number is not less than field modulus",
437                        )
438                    })
439            }
440            fn write_raw<W: std::io::Write>(&self, writer: &mut W) -> std::io::Result<()> {
441                for limb in self.0.iter() {
442                    writer.write_all(&limb.to_le_bytes())?;
443                }
444                Ok(())
445            }
446        }
447    };
448}
449
450#[macro_export]
451macro_rules! field_arithmetic_7_limbs {
452    ($field:ident, $modulus:ident, $inv:ident, $field_type:ident) => {
453        $crate::field_specific_7_limbs!($field, $modulus, $inv, $field_type);
454        impl $field {
455            /// Doubles this field element.
456            #[inline]
457            pub const fn double(&self) -> $field {
458                self.add(self)
459            }
460
461            /// Squares this element.
462            #[inline]
463            pub const fn square(&self) -> $field {
464                let (r1, carry) = mac(0, self.0[0], self.0[1], 0);
465                let (r2, carry) = mac(0, self.0[0], self.0[2], carry);
466                let (r3, carry) = mac(0, self.0[0], self.0[3], carry);
467                let (r4, carry) = mac(0, self.0[0], self.0[4], carry);
468                let (r5, carry) = mac(0, self.0[0], self.0[5], carry);
469                let (r6, r7) = mac(0, self.0[0], self.0[6], carry);
470
471                let (r3, carry) = mac(r3, self.0[1], self.0[2], 0);
472                let (r4, carry) = mac(r4, self.0[1], self.0[3], carry);
473                let (r5, carry) = mac(r5, self.0[1], self.0[4], carry);
474                let (r6, carry) = mac(r6, self.0[1], self.0[5], carry);
475                let (r7, r8) = mac(r7, self.0[1], self.0[6], carry);
476
477                let (r5, carry) = mac(r5, self.0[2], self.0[3], 0);
478                let (r6, carry) = mac(r6, self.0[2], self.0[4], carry);
479                let (r7, carry) = mac(r7, self.0[2], self.0[5], carry);
480                let (r8, r9) = mac(r8, self.0[2], self.0[6], carry);
481
482                let (r7, carry) = mac(r7, self.0[3], self.0[4], 0);
483                let (r8, carry) = mac(r8, self.0[3], self.0[5], carry);
484                let (r9, r10) = mac(r9, self.0[3], self.0[6], carry);
485
486                let (r9, carry) = mac(r9, self.0[4], self.0[5], 0);
487                let (r10, r11) = mac(r10, self.0[4], self.0[6], carry);
488
489                let (r11, r12) = mac(r11, self.0[5], self.0[6], 0);
490
491                let r13 = r12 >> 63;
492                let r12 = (r12 << 1) | (r11 >> 63);
493                let r11 = (r11 << 1) | (r10 >> 63);
494                let r10 = (r10 << 1) | (r9 >> 63);
495                let r9 = (r9 << 1) | (r8 >> 63);
496                let r8 = (r8 << 1) | (r7 >> 63);
497                let r7 = (r7 << 1) | (r6 >> 63);
498                let r6 = (r6 << 1) | (r5 >> 63);
499                let r5 = (r5 << 1) | (r4 >> 63);
500                let r4 = (r4 << 1) | (r3 >> 63);
501                let r3 = (r3 << 1) | (r2 >> 63);
502                let r2 = (r2 << 1) | (r1 >> 63);
503                let r1 = r1 << 1;
504
505                let (r0, carry) = mac(0, self.0[0], self.0[0], 0);
506                let (r1, carry) = adc(0, r1, carry);
507                let (r2, carry) = mac(r2, self.0[1], self.0[1], carry);
508                let (r3, carry) = adc(0, r3, carry);
509                let (r4, carry) = mac(r4, self.0[2], self.0[2], carry);
510                let (r5, carry) = adc(0, r5, carry);
511                let (r6, carry) = mac(r6, self.0[3], self.0[3], carry);
512                let (r7, carry) = adc(0, r7, carry);
513                let (r8, carry) = mac(r8, self.0[4], self.0[4], carry);
514                let (r9, carry) = adc(0, r9, carry);
515                let (r10, carry) = mac(r10, self.0[5], self.0[5], carry);
516                let (r11, carry) = adc(0, r11, carry);
517                let (r12, carry) = mac(r12, self.0[6], self.0[6], carry);
518                let (r13, _) = adc(0, r13, carry);
519
520                $field::montgomery_reduce(&[
521                    r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13,
522                ])
523            }
524
525            /// Multiplies `rhs` by `self`, returning the result.
526            #[inline]
527            pub const fn mul(&self, rhs: &Self) -> $field {
528                // Schoolbook multiplication
529                let (r0, carry) = mac(0, self.0[0], rhs.0[0], 0);
530                let (r1, carry) = mac(0, self.0[0], rhs.0[1], carry);
531                let (r2, carry) = mac(0, self.0[0], rhs.0[2], carry);
532                let (r3, carry) = mac(0, self.0[0], rhs.0[3], carry);
533                let (r4, carry) = mac(0, self.0[0], rhs.0[4], carry);
534                let (r5, carry) = mac(0, self.0[0], rhs.0[5], carry);
535                let (r6, r7) = mac(0, self.0[0], rhs.0[6], carry);
536
537                let (r1, carry) = mac(r1, self.0[1], rhs.0[0], 0);
538                let (r2, carry) = mac(r2, self.0[1], rhs.0[1], carry);
539                let (r3, carry) = mac(r3, self.0[1], rhs.0[2], carry);
540                let (r4, carry) = mac(r4, self.0[1], rhs.0[3], carry);
541                let (r5, carry) = mac(r5, self.0[1], rhs.0[4], carry);
542                let (r6, carry) = mac(r6, self.0[1], rhs.0[5], carry);
543                let (r7, r8) = mac(r7, self.0[1], rhs.0[6], carry);
544
545                let (r2, carry) = mac(r2, self.0[2], rhs.0[0], 0);
546                let (r3, carry) = mac(r3, self.0[2], rhs.0[1], carry);
547                let (r4, carry) = mac(r4, self.0[2], rhs.0[2], carry);
548                let (r5, carry) = mac(r5, self.0[2], rhs.0[3], carry);
549                let (r6, carry) = mac(r6, self.0[2], rhs.0[4], carry);
550                let (r7, carry) = mac(r7, self.0[2], rhs.0[5], carry);
551                let (r8, r9) = mac(r8, self.0[2], rhs.0[6], carry);
552
553                let (r3, carry) = mac(r3, self.0[3], rhs.0[0], 0);
554                let (r4, carry) = mac(r4, self.0[3], rhs.0[1], carry);
555                let (r5, carry) = mac(r5, self.0[3], rhs.0[2], carry);
556                let (r6, carry) = mac(r6, self.0[3], rhs.0[3], carry);
557                let (r7, carry) = mac(r7, self.0[3], rhs.0[4], carry);
558                let (r8, carry) = mac(r8, self.0[3], rhs.0[5], carry);
559                let (r9, r10) = mac(r9, self.0[3], rhs.0[6], carry);
560
561                let (r4, carry) = mac(r4, self.0[4], rhs.0[0], 0);
562                let (r5, carry) = mac(r5, self.0[4], rhs.0[1], carry);
563                let (r6, carry) = mac(r6, self.0[4], rhs.0[2], carry);
564                let (r7, carry) = mac(r7, self.0[4], rhs.0[3], carry);
565                let (r8, carry) = mac(r8, self.0[4], rhs.0[4], carry);
566                let (r9, carry) = mac(r9, self.0[4], rhs.0[5], carry);
567                let (r10, r11) = mac(r10, self.0[4], rhs.0[6], carry);
568
569                let (r5, carry) = mac(r5, self.0[5], rhs.0[0], 0);
570                let (r6, carry) = mac(r6, self.0[5], rhs.0[1], carry);
571                let (r7, carry) = mac(r7, self.0[5], rhs.0[2], carry);
572                let (r8, carry) = mac(r8, self.0[5], rhs.0[3], carry);
573                let (r9, carry) = mac(r9, self.0[5], rhs.0[4], carry);
574                let (r10, carry) = mac(r10, self.0[5], rhs.0[5], carry);
575                let (r11, r12) = mac(r11, self.0[5], rhs.0[6], carry);
576
577                let (r6, carry) = mac(r6, self.0[6], rhs.0[0], 0);
578                let (r7, carry) = mac(r7, self.0[6], rhs.0[1], carry);
579                let (r8, carry) = mac(r8, self.0[6], rhs.0[2], carry);
580                let (r9, carry) = mac(r9, self.0[6], rhs.0[3], carry);
581                let (r10, carry) = mac(r10, self.0[6], rhs.0[4], carry);
582                let (r11, carry) = mac(r11, self.0[6], rhs.0[5], carry);
583                let (r12, r13) = mac(r12, self.0[6], rhs.0[6], carry);
584
585                $field::montgomery_reduce(&[
586                    r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13,
587                ])
588            }
589
590            /// Subtracts `rhs` from `self`, returning the result.
591            #[inline]
592            pub const fn sub(&self, rhs: &Self) -> Self {
593                let (d0, borrow) = sbb(self.0[0], rhs.0[0], 0);
594                let (d1, borrow) = sbb(self.0[1], rhs.0[1], borrow);
595                let (d2, borrow) = sbb(self.0[2], rhs.0[2], borrow);
596                let (d3, borrow) = sbb(self.0[3], rhs.0[3], borrow);
597                let (d4, borrow) = sbb(self.0[4], rhs.0[4], borrow);
598                let (d5, borrow) = sbb(self.0[5], rhs.0[5], borrow);
599                let (d6, borrow) = sbb(self.0[6], rhs.0[6], borrow);
600
601                // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
602                // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
603                let (d0, carry) = adc(d0, $modulus.0[0] & borrow, 0);
604                let (d1, carry) = adc(d1, $modulus.0[1] & borrow, carry);
605                let (d2, carry) = adc(d2, $modulus.0[2] & borrow, carry);
606                let (d3, carry) = adc(d3, $modulus.0[3] & borrow, carry);
607                let (d4, carry) = adc(d4, $modulus.0[4] & borrow, carry);
608                let (d5, carry) = adc(d5, $modulus.0[5] & borrow, carry);
609                let (d6, _) = adc(d6, $modulus.0[6] & borrow, carry);
610
611                $field([d0, d1, d2, d3, d4, d5, d6])
612            }
613
614            /// Negates `self`.
615            #[inline]
616            pub const fn neg(&self) -> Self {
617                // Subtract `self` from `MODULUS` to negate. Ignore the final
618                // borrow because it cannot underflow; self is guaranteed to
619                // be in the field.
620                let (d0, borrow) = sbb($modulus.0[0], self.0[0], 0);
621                let (d1, borrow) = sbb($modulus.0[1], self.0[1], borrow);
622                let (d2, borrow) = sbb($modulus.0[2], self.0[2], borrow);
623                let (d3, borrow) = sbb($modulus.0[3], self.0[3], borrow);
624                let (d4, borrow) = sbb($modulus.0[4], self.0[4], borrow);
625                let (d5, borrow) = sbb($modulus.0[5], self.0[5], borrow);
626                let (d6, _) = sbb($modulus.0[6], self.0[6], borrow);
627
628                // `tmp` could be `MODULUS` if `self` was zero. Create a mask that is
629                // zero if `self` was zero, and `u64::max_value()` if self was nonzero.
630                let mask = (((self.0[0]
631                    | self.0[1]
632                    | self.0[2]
633                    | self.0[3]
634                    | self.0[4]
635                    | self.0[5]
636                    | self.0[6])
637                    == 0) as u64)
638                    .wrapping_sub(1);
639
640                $field([
641                    d0 & mask,
642                    d1 & mask,
643                    d2 & mask,
644                    d3 & mask,
645                    d4 & mask,
646                    d5 & mask,
647                    d6 & mask,
648                ])
649            }
650        }
651    };
652}
653
654#[macro_export]
655macro_rules! field_specific_7_limbs {
656    ($field:ident, $modulus:ident, $inv:ident, sparse) => {
657        impl $field {
658            /// Adds `rhs` to `self`, returning the result.
659            #[inline]
660            pub const fn add(&self, rhs: &Self) -> Self {
661                let (d0, carry) = adc(self.0[0], rhs.0[0], 0);
662                let (d1, carry) = adc(self.0[1], rhs.0[1], carry);
663                let (d2, carry) = adc(self.0[2], rhs.0[2], carry);
664                let (d3, carry) = adc(self.0[3], rhs.0[3], carry);
665                let (d4, carry) = adc(self.0[4], rhs.0[4], carry);
666                let (d5, carry) = adc(self.0[5], rhs.0[5], carry);
667                let (d6, _) = adc(self.0[6], rhs.0[6], carry);
668
669                // Attempt to subtract the modulus, to ensure the value
670                // is smaller than the modulus.
671                (&$field([d0, d1, d2, d3, d4, d5, d6])).sub(&$modulus)
672            }
673
674            #[inline(always)]
675            pub(crate) const fn montgomery_reduce(r: &[u64; 14]) -> $field {
676                // The Montgomery reduction here is based on Algorithm 14.32 in
677                // Handbook of Applied Cryptography
678                // <http://cacr.uwaterloo.ca/hac/about/chap14.pdf>.
679
680                let k = r[0].wrapping_mul($inv);
681                let (_, carry) = mac(r[0], k, $modulus.0[0], 0);
682                let (r1, carry) = mac(r[1], k, $modulus.0[1], carry);
683                let (r2, carry) = mac(r[2], k, $modulus.0[2], carry);
684                let (r3, carry) = mac(r[3], k, $modulus.0[3], carry);
685                let (r4, carry) = mac(r[4], k, $modulus.0[4], carry);
686                let (r5, carry) = mac(r[5], k, $modulus.0[5], carry);
687                let (r6, carry) = mac(r[6], k, $modulus.0[6], carry);
688                let (r7, carry2) = adc(r[7], 0, carry);
689
690                let k = r1.wrapping_mul($inv);
691                let (_, carry) = mac(r1, k, $modulus.0[0], 0);
692                let (r2, carry) = mac(r2, k, $modulus.0[1], carry);
693                let (r3, carry) = mac(r3, k, $modulus.0[2], carry);
694                let (r4, carry) = mac(r4, k, $modulus.0[3], carry);
695                let (r5, carry) = mac(r5, k, $modulus.0[4], carry);
696                let (r6, carry) = mac(r6, k, $modulus.0[5], carry);
697                let (r7, carry) = mac(r7, k, $modulus.0[6], carry);
698                let (r8, carry2) = adc(r[8], carry2, carry);
699
700                let k = r2.wrapping_mul($inv);
701                let (_, carry) = mac(r2, k, $modulus.0[0], 0);
702                let (r3, carry) = mac(r3, k, $modulus.0[1], carry);
703                let (r4, carry) = mac(r4, k, $modulus.0[2], carry);
704                let (r5, carry) = mac(r5, k, $modulus.0[3], carry);
705                let (r6, carry) = mac(r6, k, $modulus.0[4], carry);
706                let (r7, carry) = mac(r7, k, $modulus.0[5], carry);
707                let (r8, carry) = mac(r8, k, $modulus.0[6], carry);
708                let (r9, carry2) = adc(r[9], carry2, carry);
709
710                let k = r3.wrapping_mul($inv);
711                let (_, carry) = mac(r3, k, $modulus.0[0], 0);
712                let (r4, carry) = mac(r4, k, $modulus.0[1], carry);
713                let (r5, carry) = mac(r5, k, $modulus.0[2], carry);
714                let (r6, carry) = mac(r6, k, $modulus.0[3], carry);
715                let (r7, carry) = mac(r7, k, $modulus.0[4], carry);
716                let (r8, carry) = mac(r8, k, $modulus.0[5], carry);
717                let (r9, carry) = mac(r9, k, $modulus.0[6], carry);
718                let (r10, carry2) = adc(r[10], carry2, carry);
719
720                let k = r4.wrapping_mul($inv);
721                let (_, carry) = mac(r4, k, $modulus.0[0], 0);
722                let (r5, carry) = mac(r5, k, $modulus.0[1], carry);
723                let (r6, carry) = mac(r6, k, $modulus.0[2], carry);
724                let (r7, carry) = mac(r7, k, $modulus.0[3], carry);
725                let (r8, carry) = mac(r8, k, $modulus.0[4], carry);
726                let (r9, carry) = mac(r9, k, $modulus.0[5], carry);
727                let (r10, carry) = mac(r10, k, $modulus.0[6], carry);
728                let (r11, carry2) = adc(r[11], carry2, carry);
729
730                let k = r5.wrapping_mul($inv);
731                let (_, carry) = mac(r5, k, $modulus.0[0], 0);
732                let (r6, carry) = mac(r6, k, $modulus.0[1], carry);
733                let (r7, carry) = mac(r7, k, $modulus.0[2], carry);
734                let (r8, carry) = mac(r8, k, $modulus.0[3], carry);
735                let (r9, carry) = mac(r9, k, $modulus.0[4], carry);
736                let (r10, carry) = mac(r10, k, $modulus.0[5], carry);
737                let (r11, carry) = mac(r11, k, $modulus.0[6], carry);
738                let (r12, carry2) = adc(r[12], carry2, carry);
739
740                let k = r6.wrapping_mul($inv);
741                let (_, carry) = mac(r6, k, $modulus.0[0], 0);
742                let (r7, carry) = mac(r7, k, $modulus.0[1], carry);
743                let (r8, carry) = mac(r8, k, $modulus.0[2], carry);
744                let (r9, carry) = mac(r9, k, $modulus.0[3], carry);
745                let (r10, carry) = mac(r10, k, $modulus.0[4], carry);
746                let (r11, carry) = mac(r11, k, $modulus.0[5], carry);
747                let (r12, carry) = mac(r12, k, $modulus.0[6], carry);
748                let (r13, _) = adc(r[13], carry2, carry);
749                // Result may be within MODULUS of the correct value
750                (&$field([r7, r8, r9, r10, r11, r12, r13])).sub(&$modulus)
751            }
752        }
753    };
754    ($field:ident, $modulus:ident, $inv:ident, dense) => {
755        impl $field {
756            /// Adds `rhs` to `self`, returning the result.
757            #[inline]
758            pub const fn add(&self, rhs: &Self) -> Self {
759                let (d0, carry) = adc(self.0[0], rhs.0[0], 0);
760                let (d1, carry) = adc(self.0[1], rhs.0[1], carry);
761                let (d2, carry) = adc(self.0[2], rhs.0[2], carry);
762                let (d3, carry) = adc(self.0[3], rhs.0[3], carry);
763                let (d4, carry) = adc(self.0[4], rhs.0[4], carry);
764                let (d5, carry) = adc(self.0[5], rhs.0[5], carry);
765                let (d6, carry) = adc(self.0[6], rhs.0[6], carry);
766
767                // Attempt to subtract the modulus, to ensure the value
768                // is smaller than the modulus.
769                let (d0, borrow) = sbb(d0, $modulus.0[0], 0);
770                let (d1, borrow) = sbb(d1, $modulus.0[1], borrow);
771                let (d2, borrow) = sbb(d2, $modulus.0[2], borrow);
772                let (d3, borrow) = sbb(d3, $modulus.0[3], borrow);
773                let (d4, borrow) = sbb(d4, $modulus.0[4], borrow);
774                let (d5, borrow) = sbb(d5, $modulus.0[5], borrow);
775                let (_, borrow) = sbb(carry, 0, borrow);
776
777                let (d0, carry) = adc(d0, $modulus.0[0] & borrow, 0);
778                let (d1, carry) = adc(d1, $modulus.0[1] & borrow, carry);
779                let (d2, carry) = adc(d2, $modulus.0[2] & borrow, carry);
780                let (d3, carry) = adc(d3, $modulus.0[3] & borrow, carry);
781                let (d4, carry) = adc(d4, $modulus.0[4] & borrow, carry);
782                let (d5, carry) = adc(d5, $modulus.0[5] & borrow, carry);
783                let (d6, _) = adc(d6, $modulus.0[6] & borrow, carry);
784
785                $field([d0, d1, d2, d3, d4, d5, d6])
786            }
787        }
788    };
789}
790
791#[macro_export]
792macro_rules! field_bits_7_limbs {
793    // For #[cfg(target_pointer_width = "64")]
794    ($field:ident, $modulus:ident) => {
795        #[cfg(feature = "bits")]
796        #[cfg_attr(docsrs, doc(cfg(feature = "bits")))]
797        impl ::ff::PrimeFieldBits for $field {
798            type ReprBits = [u64; 7];
799
800            fn to_le_bits(&self) -> ::ff::FieldBits<Self::ReprBits> {
801                let bytes = self.to_repr().repr;
802
803                let limbs = [
804                    u64::from_le_bytes(bytes[0..8].try_into().unwrap()),
805                    u64::from_le_bytes(bytes[8..16].try_into().unwrap()),
806                    u64::from_le_bytes(bytes[16..24].try_into().unwrap()),
807                    u64::from_le_bytes(bytes[24..32].try_into().unwrap()),
808                    u64::from_le_bytes(bytes[32..40].try_into().unwrap()),
809                    u64::from_le_bytes(bytes[40..48].try_into().unwrap()),
810                    u64::from_le_bytes(bytes[48..56].try_into().unwrap()),
811                ];
812
813                ::ff::FieldBits::new(limbs)
814            }
815
816            fn char_le_bits() -> ::ff::FieldBits<Self::ReprBits> {
817                ::ff::FieldBits::new($modulus.0)
818            }
819        }
820    };
821    // For #[cfg(not(target_pointer_width = "64"))]
822    ($field:ident, $modulus:ident, $modulus_limbs_32:ident) => {
823        #[cfg(feature = "bits")]
824        #[cfg_attr(docsrs, doc(cfg(feature = "bits")))]
825        impl ::ff::PrimeFieldBits for $field {
826            type ReprBits = [u32; 14];
827
828            fn to_le_bits(&self) -> ::ff::FieldBits<Self::ReprBits> {
829                let bytes = self.to_repr().repr;
830
831                let limbs = [
832                    u32::from_le_bytes(bytes[0..4].try_into().unwrap()),
833                    u32::from_le_bytes(bytes[4..8].try_into().unwrap()),
834                    u32::from_le_bytes(bytes[8..12].try_into().unwrap()),
835                    u32::from_le_bytes(bytes[12..16].try_into().unwrap()),
836                    u32::from_le_bytes(bytes[16..20].try_into().unwrap()),
837                    u32::from_le_bytes(bytes[20..24].try_into().unwrap()),
838                    u32::from_le_bytes(bytes[24..28].try_into().unwrap()),
839                    u32::from_le_bytes(bytes[28..32].try_into().unwrap()),
840                    u32::from_le_bytes(bytes[32..36].try_into().unwrap()),
841                    u32::from_le_bytes(bytes[36..40].try_into().unwrap()),
842                    u32::from_le_bytes(bytes[40..44].try_into().unwrap()),
843                    u32::from_le_bytes(bytes[44..48].try_into().unwrap()),
844                    u32::from_le_bytes(bytes[48..52].try_into().unwrap()),
845                    u32::from_le_bytes(bytes[52..56].try_into().unwrap()),
846                ];
847
848                ::ff::FieldBits::new(limbs)
849            }
850
851            fn char_le_bits() -> ::ff::FieldBits<Self::ReprBits> {
852                ::ff::FieldBits::new($modulus_limbs_32)
853            }
854        }
855    };
856}
halo2curves_axiom/pluto_eris/fields/mod.rs

halo2curves_axiom/pluto_eris/fields/
mod.rs
