snarkvm_fields/
fp_256.rs

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

snarkvm_fields/
fp_256.rs
