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

snarkvm_fields/
fp_384.rs
