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

snarkvm_fields/
fp_384.rs
