snarkvm_fields/
fp_256.rs

1// Copyright (c) 2019-2026 Provable Inc.
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use crate::{
17    FftField,
18    Field,
19    FieldError,
20    FieldParameters,
21    LegendreSymbol,
22    One,
23    PoseidonDefaultField,
24    PoseidonDefaultParameters,
25    PrimeField,
26    SquareRootField,
27    Zero,
28};
29use snarkvm_utilities::{
30    FromBytes,
31    ToBits,
32    ToBytes,
33    biginteger::{BigInteger as _BigInteger, BigInteger256 as BigInteger, arithmetic as fa},
34    serialize::CanonicalDeserialize,
35};
36
37use std::{
38    cmp::{Ord, Ordering, PartialOrd},
39    fmt::{Debug, Display, Formatter, Result as FmtResult},
40    io::{Read, Result as IoResult, Write},
41    marker::PhantomData,
42    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
43    str::FromStr,
44};
45use zeroize::Zeroize;
46
47pub trait Fp256Parameters: FieldParameters<BigInteger = BigInteger> {}
48
49#[derive(Copy, Clone, Default, PartialEq, Eq, Hash, Zeroize)]
50pub struct Fp256<P: Fp256Parameters>(pub BigInteger, #[doc(hidden)] pub PhantomData<P>);
51
52impl<P: Fp256Parameters> Fp256<P> {
53    #[inline]
54    fn is_valid(&self) -> bool {
55        self.0 < P::MODULUS
56    }
57
58    #[inline]
59    fn reduce(&mut self) {
60        if !self.is_valid() {
61            self.0.sub_noborrow(&P::MODULUS);
62        }
63    }
64
65    #[inline(always)]
66    #[allow(clippy::too_many_arguments)]
67    fn mont_reduce(
68        &mut self,
69        r0: u64,
70        mut r1: u64,
71        mut r2: u64,
72        mut r3: u64,
73        mut r4: u64,
74        mut r5: u64,
75        mut r6: u64,
76        mut r7: u64,
77    ) {
78        // The Montgomery reduction here is based on Algorithm 14.32 in
79        // Handbook of Applied Cryptography
80        // <http://cacr.uwaterloo.ca/hac/about/chap14.pdf>.
81
82        let k = r0.wrapping_mul(P::INV);
83        let mut carry = 0;
84        fa::mac_with_carry(r0, k, P::MODULUS.0[0], &mut carry);
85        r1 = fa::mac_with_carry(r1, k, P::MODULUS.0[1], &mut carry);
86        r2 = fa::mac_with_carry(r2, k, P::MODULUS.0[2], &mut carry);
87        r3 = fa::mac_with_carry(r3, k, P::MODULUS.0[3], &mut carry);
88        carry = fa::adc(&mut r4, 0, carry);
89        let carry2 = carry;
90        let k = r1.wrapping_mul(P::INV);
91        let mut carry = 0;
92        fa::mac_with_carry(r1, k, P::MODULUS.0[0], &mut carry);
93        r2 = fa::mac_with_carry(r2, k, P::MODULUS.0[1], &mut carry);
94        r3 = fa::mac_with_carry(r3, k, P::MODULUS.0[2], &mut carry);
95        r4 = fa::mac_with_carry(r4, k, P::MODULUS.0[3], &mut carry);
96        carry = fa::adc(&mut r5, carry2, carry);
97        let carry2 = carry;
98        let k = r2.wrapping_mul(P::INV);
99        let mut carry = 0;
100        fa::mac_with_carry(r2, k, P::MODULUS.0[0], &mut carry);
101        r3 = fa::mac_with_carry(r3, k, P::MODULUS.0[1], &mut carry);
102        r4 = fa::mac_with_carry(r4, k, P::MODULUS.0[2], &mut carry);
103        r5 = fa::mac_with_carry(r5, k, P::MODULUS.0[3], &mut carry);
104        carry = fa::adc(&mut r6, carry2, carry);
105        let carry2 = carry;
106        let k = r3.wrapping_mul(P::INV);
107        let mut carry = 0;
108        fa::mac_with_carry(r3, k, P::MODULUS.0[0], &mut carry);
109        r4 = fa::mac_with_carry(r4, k, P::MODULUS.0[1], &mut carry);
110        r5 = fa::mac_with_carry(r5, k, P::MODULUS.0[2], &mut carry);
111        r6 = fa::mac_with_carry(r6, k, P::MODULUS.0[3], &mut carry);
112        fa::adc(&mut r7, carry2, carry);
113        (self.0).0[0] = r4;
114        (self.0).0[1] = r5;
115        (self.0).0[2] = r6;
116        (self.0).0[3] = r7;
117        self.reduce();
118    }
119}
120
121impl<P: Fp256Parameters> Zero for Fp256<P> {
122    #[inline]
123    fn zero() -> Self {
124        Self(BigInteger::from(0), PhantomData)
125    }
126
127    #[inline]
128    fn is_zero(&self) -> bool {
129        self.0.is_zero()
130    }
131}
132
133impl<P: Fp256Parameters> One for Fp256<P> {
134    #[inline]
135    fn one() -> Self {
136        Self(P::R, PhantomData)
137    }
138
139    #[inline]
140    fn is_one(&self) -> bool {
141        self.0 == P::R
142    }
143}
144
145impl<P: Fp256Parameters> Field for Fp256<P> {
146    type BasePrimeField = Self;
147
148    // 256/64 = 4 limbs.
149    impl_field_from_random_bytes_with_flags!(4);
150
151    fn from_base_prime_field(other: Self::BasePrimeField) -> Self {
152        other
153    }
154
155    /// Returns the constant 2^{-1}.
156    fn half() -> Self {
157        // Compute 1/2 `(p+1)/2` as `1/2`.
158        // This is cheaper than `Self::one().double().inverse()`
159        let mut two_inv = P::MODULUS;
160        two_inv.add_nocarry(&1u64.into());
161        two_inv.div2();
162        Self::from_bigint(two_inv).unwrap() // Guaranteed to be valid.
163    }
164
165    fn sum_of_products<'a>(a: &'a [Self], b: &'a [Self]) -> Self {
166        // For a single `a x b` multiplication, operand scanning (schoolbook) takes each
167        // limb of `a` in turn, and multiplies it by all of the limbs of `b` to compute
168        // the result as a double-width intermediate representation, which is then fully
169        // reduced at the end. Here however we have pairs of multiplications (a_i, b_i),
170        // the results of which are summed.
171        //
172        // The intuition for this algorithm is two-fold:
173        // - We can interleave the operand scanning for each pair, by processing the jth
174        //   limb of each `a_i` together. As these have the same offset within the overall
175        //   operand scanning flow, their results can be summed directly.
176        // - We can interleave the multiplication and reduction steps, resulting in a
177        //   single bitshift by the limb size after each iteration. This means we only
178        //   need to store a single extra limb overall, instead of keeping around all the
179        //   intermediate results and eventually having twice as many limbs.
180
181        // Algorithm 2, line 2
182        let (u0, u1, u2, u3) = (0..4).fold((0, 0, 0, 0), |(u0, u1, u2, u3), j| {
183            // Algorithm 2, line 3
184            // For each pair in the overall sum of products:
185            let (t0, t1, t2, t3, mut t4) =
186                a.iter().zip(b).fold((u0, u1, u2, u3, 0), |(t0, t1, t2, t3, mut t4), (a, b)| {
187                    // Compute digit_j x row and accumulate into `u`.
188                    let mut carry = 0;
189                    let t0 = fa::mac_with_carry(t0, a.0.0[j], b.0.0[0], &mut carry);
190                    let t1 = fa::mac_with_carry(t1, a.0.0[j], b.0.0[1], &mut carry);
191                    let t2 = fa::mac_with_carry(t2, a.0.0[j], b.0.0[2], &mut carry);
192                    let t3 = fa::mac_with_carry(t3, a.0.0[j], b.0.0[3], &mut carry);
193                    let _ = fa::adc(&mut t4, 0, carry);
194
195                    (t0, t1, t2, t3, t4)
196                });
197
198            // Algorithm 2, lines 4-5
199            // This is a single step of the usual Montgomery reduction process.
200            let k = t0.wrapping_mul(P::INV);
201            let mut carry = 0;
202            let _ = fa::mac_with_carry(t0, k, P::MODULUS.0[0], &mut carry);
203            let r1 = fa::mac_with_carry(t1, k, P::MODULUS.0[1], &mut carry);
204            let r2 = fa::mac_with_carry(t2, k, P::MODULUS.0[2], &mut carry);
205            let r3 = fa::mac_with_carry(t3, k, P::MODULUS.0[3], &mut carry);
206            let _ = fa::adc(&mut t4, 0, carry);
207            let r4 = t4;
208
209            (r1, r2, r3, r4)
210        });
211
212        // Because we represent F_p elements in non-redundant form, we need a final
213        // conditional subtraction to ensure the output is in range.
214        let mut result = Self(BigInteger([u0, u1, u2, u3]), PhantomData);
215        result.reduce();
216        result
217    }
218
219    #[inline]
220    fn double(&self) -> Self {
221        let mut temp = *self;
222        temp.double_in_place();
223        temp
224    }
225
226    #[inline]
227    fn double_in_place(&mut self) {
228        // This cannot exceed the backing capacity.
229        self.0.mul2();
230        // However, it may need to be reduced.
231        self.reduce();
232    }
233
234    #[inline]
235    fn characteristic<'a>() -> &'a [u64] {
236        P::MODULUS.as_ref()
237    }
238
239    #[inline]
240    fn square(&self) -> Self {
241        let mut temp = *self;
242        temp.square_in_place();
243        temp
244    }
245
246    #[inline]
247    fn square_in_place(&mut self) -> &mut Self {
248        // i = 0
249        let mut carry = 0;
250        let r1 = fa::mac_with_carry(0, (self.0).0[0], (self.0).0[1], &mut carry);
251        let r2 = fa::mac_with_carry(0, (self.0).0[0], (self.0).0[2], &mut carry);
252        let r3 = fa::mac_with_carry(0, (self.0).0[0], (self.0).0[3], &mut carry);
253        let r4 = carry;
254        let mut carry = 0;
255        let r3 = fa::mac_with_carry(r3, (self.0).0[1], (self.0).0[2], &mut carry);
256        let r4 = fa::mac_with_carry(r4, (self.0).0[1], (self.0).0[3], &mut carry);
257        let r5 = carry;
258        let mut carry = 0;
259        let r5 = fa::mac_with_carry(r5, (self.0).0[2], (self.0).0[3], &mut carry);
260        let r6 = carry;
261
262        let mut r7 = r6 >> 63;
263        let r6 = (r6 << 1) | (r5 >> 63);
264        let mut r5 = (r5 << 1) | (r4 >> 63);
265        let r4 = (r4 << 1) | (r3 >> 63);
266        let mut r3 = (r3 << 1) | (r2 >> 63);
267        let r2 = (r2 << 1) | (r1 >> 63);
268        let mut r1 = r1 << 1;
269
270        let mut carry = 0;
271        let r0 = fa::mac_with_carry(0, (self.0).0[0], (self.0).0[0], &mut carry);
272        carry = fa::adc(&mut r1, 0, carry);
273        let r2 = fa::mac_with_carry(r2, (self.0).0[1], (self.0).0[1], &mut carry);
274        carry = fa::adc(&mut r3, 0, carry);
275        let r4 = fa::mac_with_carry(r4, (self.0).0[2], (self.0).0[2], &mut carry);
276        carry = fa::adc(&mut r5, 0, carry);
277        let r6 = fa::mac_with_carry(r6, (self.0).0[3], (self.0).0[3], &mut carry);
278        fa::adc(&mut r7, 0, carry);
279
280        self.mont_reduce(r0, r1, r2, r3, r4, r5, r6, r7);
281        self
282    }
283
284    #[inline]
285    fn inverse(&self) -> Option<Self> {
286        if self.is_zero() {
287            None
288        } else {
289            // Guajardo Kumar Paar Pelzl
290            // Efficient Software-Implementation of Finite Fields with Applications to
291            // Cryptography
292            // Algorithm 16 (BEA for Inversion in Fp)
293
294            let one = BigInteger::from(1);
295
296            let mut u = self.0;
297            let mut v = P::MODULUS;
298            let mut b = Self(P::R2, PhantomData); // Avoids unnecessary reduction step.
299            let mut c = Self::zero();
300
301            while u != one && v != one {
302                while u.is_even() {
303                    u.div2();
304
305                    if b.0.is_even() {
306                        b.0.div2();
307                    } else {
308                        b.0.add_nocarry(&P::MODULUS);
309                        b.0.div2();
310                    }
311                }
312
313                while v.is_even() {
314                    v.div2();
315
316                    if c.0.is_even() {
317                        c.0.div2();
318                    } else {
319                        c.0.add_nocarry(&P::MODULUS);
320                        c.0.div2();
321                    }
322                }
323
324                if v < u {
325                    u.sub_noborrow(&v);
326                    b.sub_assign(&c);
327                } else {
328                    v.sub_noborrow(&u);
329                    c.sub_assign(&b);
330                }
331            }
332
333            if u == one { Some(b) } else { Some(c) }
334        }
335    }
336
337    fn inverse_in_place(&mut self) -> Option<&mut Self> {
338        if let Some(inverse) = self.inverse() {
339            *self = inverse;
340            Some(self)
341        } else {
342            None
343        }
344    }
345
346    #[inline]
347    fn frobenius_map(&mut self, _: usize) {
348        // No-op: No effect in a prime field.
349    }
350}
351
352impl<P: Fp256Parameters> PrimeField for Fp256<P> {
353    type BigInteger = BigInteger;
354    type Parameters = P;
355
356    #[inline]
357    fn from_bigint(r: BigInteger) -> Option<Self> {
358        let mut r = Fp256(r, PhantomData);
359        if r.is_zero() {
360            Some(r)
361        } else if r.is_valid() {
362            r *= &Fp256(P::R2, PhantomData);
363            Some(r)
364        } else {
365            None
366        }
367    }
368
369    #[inline]
370    fn to_bigint(&self) -> BigInteger {
371        let mut tmp = self.0;
372        let mut r = tmp.0;
373        // Montgomery Reduction
374        let k = r[0].wrapping_mul(P::INV);
375        let mut carry = 0;
376        fa::mac_with_carry(r[0], k, P::MODULUS.0[0], &mut carry);
377        r[1] = fa::mac_with_carry(r[1], k, P::MODULUS.0[1], &mut carry);
378        r[2] = fa::mac_with_carry(r[2], k, P::MODULUS.0[2], &mut carry);
379        r[3] = fa::mac_with_carry(r[3], k, P::MODULUS.0[3], &mut carry);
380        r[0] = carry;
381
382        let k = r[1].wrapping_mul(P::INV);
383        let mut carry = 0;
384        fa::mac_with_carry(r[1], k, P::MODULUS.0[0], &mut carry);
385        r[2] = fa::mac_with_carry(r[2], k, P::MODULUS.0[1], &mut carry);
386        r[3] = fa::mac_with_carry(r[3], k, P::MODULUS.0[2], &mut carry);
387        r[0] = fa::mac_with_carry(r[0], k, P::MODULUS.0[3], &mut carry);
388        r[1] = carry;
389
390        let k = r[2].wrapping_mul(P::INV);
391        let mut carry = 0;
392        fa::mac_with_carry(r[2], k, P::MODULUS.0[0], &mut carry);
393        r[3] = fa::mac_with_carry(r[3], k, P::MODULUS.0[1], &mut carry);
394        r[0] = fa::mac_with_carry(r[0], k, P::MODULUS.0[2], &mut carry);
395        r[1] = fa::mac_with_carry(r[1], k, P::MODULUS.0[3], &mut carry);
396        r[2] = carry;
397
398        let k = r[3].wrapping_mul(P::INV);
399        let mut carry = 0;
400        fa::mac_with_carry(r[3], k, P::MODULUS.0[0], &mut carry);
401        r[0] = fa::mac_with_carry(r[0], k, P::MODULUS.0[1], &mut carry);
402        r[1] = fa::mac_with_carry(r[1], k, P::MODULUS.0[2], &mut carry);
403        r[2] = fa::mac_with_carry(r[2], k, P::MODULUS.0[3], &mut carry);
404        r[3] = carry;
405
406        tmp.0 = r;
407        tmp
408    }
409
410    #[inline]
411    fn decompose(
412        &self,
413        q1: &[u64; 4],
414        q2: &[u64; 4],
415        b1: Self,
416        b2: Self,
417        r128: Self,
418        half_r: &[u64; 8],
419    ) -> (Self, Self, bool, bool) {
420        let mul_short = |a: &[u64; 4], b: &[u64; 4]| -> [u64; 8] {
421            // Schoolbook multiplication
422            let mut carry = 0;
423            let r0 = fa::mac_with_carry(0, a[0], b[0], &mut carry);
424            let r1 = fa::mac_with_carry(0, a[0], b[1], &mut carry);
425            let r2 = fa::mac_with_carry(0, a[0], b[2], &mut carry);
426            let r3 = carry;
427
428            let mut carry = 0;
429            let r1 = fa::mac_with_carry(r1, a[1], b[0], &mut carry);
430            let r2 = fa::mac_with_carry(r2, a[1], b[1], &mut carry);
431            let r3 = fa::mac_with_carry(r3, a[1], b[2], &mut carry);
432            let r4 = carry;
433
434            let mut carry = 0;
435            let r2 = fa::mac_with_carry(r2, a[2], b[0], &mut carry);
436            let r3 = fa::mac_with_carry(r3, a[2], b[1], &mut carry);
437            let r4 = fa::mac_with_carry(r4, a[2], b[2], &mut carry);
438            let r5 = carry;
439
440            let mut carry = 0;
441            let r3 = fa::mac_with_carry(r3, a[3], b[0], &mut carry);
442            let r4 = fa::mac_with_carry(r4, a[3], b[1], &mut carry);
443            let r5 = fa::mac_with_carry(r5, a[3], b[2], &mut carry);
444            let r6 = carry;
445
446            [r0, r1, r2, r3, r4, r5, r6, 0]
447        };
448
449        let round = |a: &mut [u64; 8]| -> Self {
450            let mut carry = 0;
451            // NOTE: can the first 4 be omitted?
452            carry = fa::adc(&mut a[0], half_r[0], carry);
453            carry = fa::adc(&mut a[1], half_r[1], carry);
454            carry = fa::adc(&mut a[2], half_r[2], carry);
455            carry = fa::adc(&mut a[3], half_r[3], carry);
456            carry = fa::adc(&mut a[4], half_r[4], carry);
457            carry = fa::adc(&mut a[5], half_r[5], carry);
458            carry = fa::adc(&mut a[6], half_r[6], carry);
459            _ = fa::adc(&mut a[7], half_r[7], carry);
460            Self::from_bigint(BigInteger([a[4], a[5], a[6], a[7]])).unwrap()
461        };
462
463        let alpha = |x: &Self, q: &[u64; 4]| -> Self {
464            let mut a = mul_short(&x.to_bigint().0, q);
465            round(&mut a)
466        };
467
468        let alpha1 = alpha(self, q1);
469        let alpha2 = alpha(self, q2);
470        let z1 = alpha1 * b1;
471        let z2 = alpha2 * b2;
472
473        let mut k1 = *self - z1 - alpha2;
474        let mut k2 = z2 - alpha1;
475        let mut k1_neg = false;
476        let mut k2_neg = false;
477
478        if k1 > r128 {
479            k1 = -k1;
480            k1_neg = true;
481        }
482
483        if k2 > r128 {
484            k2 = -k2;
485            k2_neg = true;
486        }
487
488        (k1, k2, k1_neg, k2_neg)
489    }
490}
491
492impl<P: Fp256Parameters> FftField for Fp256<P> {
493    type FftParameters = P;
494
495    #[inline]
496    fn two_adic_root_of_unity() -> Self {
497        Self(P::TWO_ADIC_ROOT_OF_UNITY, PhantomData)
498    }
499
500    #[inline]
501    fn large_subgroup_root_of_unity() -> Option<Self> {
502        Some(Self(P::LARGE_SUBGROUP_ROOT_OF_UNITY?, PhantomData))
503    }
504
505    #[inline]
506    fn multiplicative_generator() -> Self {
507        Self(P::GENERATOR, PhantomData)
508    }
509}
510
511impl<P: Fp256Parameters> SquareRootField for Fp256<P> {
512    #[inline]
513    fn legendre(&self) -> LegendreSymbol {
514        use crate::LegendreSymbol::*;
515
516        // s = self^((MODULUS - 1) // 2)
517        let mut s = self.pow(P::MODULUS_MINUS_ONE_DIV_TWO);
518        s.reduce();
519
520        if s.is_zero() {
521            Zero
522        } else if s.is_one() {
523            QuadraticResidue
524        } else {
525            QuadraticNonResidue
526        }
527    }
528
529    #[inline]
530    fn sqrt(&self) -> Option<Self> {
531        sqrt_impl!(Self, P, self)
532    }
533
534    fn sqrt_in_place(&mut self) -> Option<&mut Self> {
535        (*self).sqrt().map(|sqrt| {
536            *self = sqrt;
537            self
538        })
539    }
540}
541
542/// `Fp` elements are ordered lexicographically.
543impl<P: Fp256Parameters> Ord for Fp256<P> {
544    #[inline(always)]
545    fn cmp(&self, other: &Self) -> Ordering {
546        self.to_bigint().cmp(&other.to_bigint())
547    }
548}
549
550impl<P: Fp256Parameters> PartialOrd for Fp256<P> {
551    #[inline(always)]
552    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
553        Some(self.cmp(other))
554    }
555}
556
557impl<P: Fp256Parameters + PoseidonDefaultParameters> PoseidonDefaultField for Fp256<P> {}
558
559impl_primefield_from_int!(Fp256, u128, Fp256Parameters);
560impl_primefield_from_int!(Fp256, u64, Fp256Parameters);
561impl_primefield_from_int!(Fp256, u32, Fp256Parameters);
562impl_primefield_from_int!(Fp256, u16, Fp256Parameters);
563impl_primefield_from_int!(Fp256, u8, Fp256Parameters);
564
565impl_primefield_standard_sample!(Fp256, Fp256Parameters);
566
567impl_add_sub_from_field_ref!(Fp256, Fp256Parameters);
568impl_mul_div_from_field_ref!(Fp256, Fp256Parameters);
569
570impl<P: Fp256Parameters> ToBits for Fp256<P> {
571    fn write_bits_le(&self, vec: &mut Vec<bool>) {
572        let initial_len = vec.len();
573        self.to_bigint().write_bits_le(vec);
574        vec.truncate(initial_len + P::MODULUS_BITS as usize);
575    }
576
577    fn write_bits_be(&self, vec: &mut Vec<bool>) {
578        let initial_len = vec.len();
579        self.write_bits_le(vec);
580        vec[initial_len..].reverse();
581    }
582
583    fn num_bits() -> Option<usize> {
584        Some(256)
585    }
586}
587
588impl<P: Fp256Parameters> ToBytes for Fp256<P> {
589    #[inline]
590    fn write_le<W: Write>(&self, writer: W) -> IoResult<()> {
591        self.to_bigint().write_le(writer)
592    }
593}
594
595impl<P: Fp256Parameters> FromBytes for Fp256<P> {
596    #[inline]
597    fn read_le<R: Read>(reader: R) -> IoResult<Self> {
598        BigInteger::read_le(reader).and_then(|b| match Self::from_bigint(b) {
599            Some(f) => Ok(f),
600            None => Err(FieldError::InvalidFieldElement.into()),
601        })
602    }
603}
604
605impl<P: Fp256Parameters> FromStr for Fp256<P> {
606    type Err = FieldError;
607
608    /// Interpret a string of numbers as a (congruent) prime field element.
609    /// Does not accept unnecessary leading zeroes or a blank string.
610    fn from_str(s: &str) -> Result<Self, Self::Err> {
611        if s.is_empty() {
612            return Err(FieldError::ParsingEmptyString);
613        }
614
615        if s == "0" {
616            return Ok(Self::zero());
617        }
618
619        let mut res = Self::zero();
620
621        let ten =
622            Self::from_bigint(<Self as PrimeField>::BigInteger::from(10)).ok_or(FieldError::InvalidFieldElement)?;
623
624        let mut first_digit = true;
625
626        for c in s.chars() {
627            match c.to_digit(10) {
628                Some(c) => {
629                    if first_digit {
630                        if c == 0 {
631                            return Err(FieldError::InvalidString);
632                        }
633
634                        first_digit = false;
635                    }
636
637                    res.mul_assign(&ten);
638                    res.add_assign(
639                        &Self::from_bigint(<Self as PrimeField>::BigInteger::from(u64::from(c)))
640                            .ok_or(FieldError::InvalidFieldElement)?,
641                    );
642                }
643                None => return Err(FieldError::ParsingNonDigitCharacter),
644            }
645        }
646
647        if !res.is_valid() { Err(FieldError::InvalidFieldElement) } else { Ok(res) }
648    }
649}
650
651impl<P: Fp256Parameters> Debug for Fp256<P> {
652    #[inline]
653    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
654        write!(f, "{}", self.to_bigint())
655    }
656}
657
658impl<P: Fp256Parameters> Display for Fp256<P> {
659    #[inline]
660    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
661        write!(f, "{}", self.to_bigint())
662    }
663}
664
665impl<P: Fp256Parameters> Neg for Fp256<P> {
666    type Output = Self;
667
668    #[inline]
669    fn neg(self) -> Self {
670        if !self.is_zero() {
671            let mut tmp = P::MODULUS;
672            tmp.sub_noborrow(&self.0);
673            Self(tmp, PhantomData)
674        } else {
675            self
676        }
677    }
678}
679
680impl<P: Fp256Parameters> Add<&'_ Fp256<P>> for Fp256<P> {
681    type Output = Self;
682
683    #[inline]
684    fn add(self, other: &Self) -> Self {
685        let mut result = self;
686        result.add_assign(other);
687        result
688    }
689}
690
691impl<P: Fp256Parameters> Sub<&'_ Fp256<P>> for Fp256<P> {
692    type Output = Self;
693
694    #[inline]
695    fn sub(self, other: &Self) -> Self {
696        let mut result = self;
697        result.sub_assign(other);
698        result
699    }
700}
701
702impl<P: Fp256Parameters> Mul<&'_ Fp256<P>> for Fp256<P> {
703    type Output = Self;
704
705    #[inline]
706    fn mul(self, other: &Self) -> Self {
707        let mut result = self;
708        result.mul_assign(other);
709        result
710    }
711}
712
713impl<P: Fp256Parameters> Div<&'_ Fp256<P>> for Fp256<P> {
714    type Output = Self;
715
716    #[inline]
717    fn div(self, other: &Self) -> Self {
718        let mut result = self;
719        result.mul_assign(&other.inverse().unwrap());
720        result
721    }
722}
723
724impl<P: Fp256Parameters> AddAssign<&'_ Self> for Fp256<P> {
725    #[inline]
726    fn add_assign(&mut self, other: &Self) {
727        // This cannot exceed the backing capacity.
728        self.0.add_nocarry(&other.0);
729        // However, it may need to be reduced.
730        self.reduce();
731    }
732}
733
734impl<P: Fp256Parameters> SubAssign<&'_ Self> for Fp256<P> {
735    #[inline]
736    fn sub_assign(&mut self, other: &Self) {
737        // If `other` is larger than `self`, add the modulus to self first.
738        if other.0 > self.0 {
739            self.0.add_nocarry(&P::MODULUS);
740        }
741
742        self.0.sub_noborrow(&other.0);
743    }
744}
745
746impl<P: Fp256Parameters> MulAssign<&'_ Self> for Fp256<P> {
747    #[inline]
748    fn mul_assign(&mut self, other: &Self) {
749        let mut r = [0u64; 4];
750        let mut carry1 = 0u64;
751        let mut carry2 = 0u64;
752
753        // Iteration 0.
754        r[0] = fa::mac(r[0], (self.0).0[0], (other.0).0[0], &mut carry1);
755        let k = r[0].wrapping_mul(P::INV);
756        fa::mac_discard(r[0], k, P::MODULUS.0[0], &mut carry2);
757        r[1] = fa::mac_with_carry(r[1], (self.0).0[1], (other.0).0[0], &mut carry1);
758        r[0] = fa::mac_with_carry(r[1], k, P::MODULUS.0[1], &mut carry2);
759
760        r[2] = fa::mac_with_carry(r[2], (self.0).0[2], (other.0).0[0], &mut carry1);
761        r[1] = fa::mac_with_carry(r[2], k, P::MODULUS.0[2], &mut carry2);
762
763        r[3] = fa::mac_with_carry(r[3], (self.0).0[3], (other.0).0[0], &mut carry1);
764        r[2] = fa::mac_with_carry(r[3], k, P::MODULUS.0[3], &mut carry2);
765        r[3] = carry1 + carry2;
766
767        // Iteration 1.
768        r[0] = fa::mac(r[0], (self.0).0[0], (other.0).0[1], &mut carry1);
769        let k = r[0].wrapping_mul(P::INV);
770        fa::mac_discard(r[0], k, P::MODULUS.0[0], &mut carry2);
771        r[1] = fa::mac_with_carry(r[1], (self.0).0[1], (other.0).0[1], &mut carry1);
772        r[0] = fa::mac_with_carry(r[1], k, P::MODULUS.0[1], &mut carry2);
773
774        r[2] = fa::mac_with_carry(r[2], (self.0).0[2], (other.0).0[1], &mut carry1);
775        r[1] = fa::mac_with_carry(r[2], k, P::MODULUS.0[2], &mut carry2);
776
777        r[3] = fa::mac_with_carry(r[3], (self.0).0[3], (other.0).0[1], &mut carry1);
778        r[2] = fa::mac_with_carry(r[3], k, P::MODULUS.0[3], &mut carry2);
779        r[3] = carry1 + carry2;
780
781        // Iteration 2.
782        r[0] = fa::mac(r[0], (self.0).0[0], (other.0).0[2], &mut carry1);
783        let k = r[0].wrapping_mul(P::INV);
784        fa::mac_discard(r[0], k, P::MODULUS.0[0], &mut carry2);
785        r[1] = fa::mac_with_carry(r[1], (self.0).0[1], (other.0).0[2], &mut carry1);
786        r[0] = fa::mac_with_carry(r[1], k, P::MODULUS.0[1], &mut carry2);
787
788        r[2] = fa::mac_with_carry(r[2], (self.0).0[2], (other.0).0[2], &mut carry1);
789        r[1] = fa::mac_with_carry(r[2], k, P::MODULUS.0[2], &mut carry2);
790
791        r[3] = fa::mac_with_carry(r[3], (self.0).0[3], (other.0).0[2], &mut carry1);
792        r[2] = fa::mac_with_carry(r[3], k, P::MODULUS.0[3], &mut carry2);
793        r[3] = carry1 + carry2;
794
795        // Iteration 3.
796        r[0] = fa::mac(r[0], (self.0).0[0], (other.0).0[3], &mut carry1);
797        let k = r[0].wrapping_mul(P::INV);
798        fa::mac_discard(r[0], k, P::MODULUS.0[0], &mut carry2);
799        r[1] = fa::mac_with_carry(r[1], (self.0).0[1], (other.0).0[3], &mut carry1);
800        r[0] = fa::mac_with_carry(r[1], k, P::MODULUS.0[1], &mut carry2);
801
802        r[2] = fa::mac_with_carry(r[2], (self.0).0[2], (other.0).0[3], &mut carry1);
803        r[1] = fa::mac_with_carry(r[2], k, P::MODULUS.0[2], &mut carry2);
804
805        r[3] = fa::mac_with_carry(r[3], (self.0).0[3], (other.0).0[3], &mut carry1);
806        r[2] = fa::mac_with_carry(r[3], k, P::MODULUS.0[3], &mut carry2);
807        r[3] = carry1 + carry2;
808
809        (self.0).0 = r;
810        self.reduce();
811    }
812}
813
814impl<P: Fp256Parameters> DivAssign<&'_ Self> for Fp256<P> {
815    #[inline]
816    fn div_assign(&mut self, other: &Self) {
817        self.mul_assign(&other.inverse().unwrap());
818    }
819}
snarkvm_fields/fp_256.rs

snarkvm_fields/
fp_256.rs
