halo2curves_axiom/bls12_381/
fp.rs

Help
1//! This module provides an implementation of the BLS12-381 base field `GF(p)`
2//! where `p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab`
3//! Source: <https://github.com/privacy-scaling-explorations/bls12_381>
4
5#![allow(clippy::needless_borrow)]
6use core::cmp::Ordering;
7use core::fmt;
8use core::ops::{Add, Mul, Neg, Sub};
9use ff::{Field, PrimeField, WithSmallOrderMulGroup};
10use rand_core::RngCore;
11use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
12
13use crate::arithmetic::{adc, mac, sbb};
14use crate::{
15    impl_add_binop_specify_output, impl_binops_additive, impl_binops_additive_specify_output,
16    impl_binops_multiplicative, impl_binops_multiplicative_mixed, impl_sub_binop_specify_output,
17};
18/// Represents an element of the base field $\mathbb{F}_p$ of the BLS12-381 elliptic
19/// curve construction.
20/// The internal representation of this type is six 64-bit unsigned
21/// integers in little-endian order. `Fp` values are always in
22/// Montgomery form; i.e., Scalar(a) = aR mod p, with R = 2^384.
23#[derive(Copy, Clone, PartialEq, Eq, Hash)]
24pub struct Fp(pub(crate) [u64; 6]);
25
26impl fmt::Debug for Fp {
27    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
28        let tmp = self.to_bytes();
29        write!(f, "0x")?;
30        for &b in tmp.iter().rev() {
31            write!(f, "{b:02x}")?;
32        }
33        Ok(())
34    }
35}
36
37impl Default for Fp {
38    fn default() -> Self {
39        Fp::zero()
40    }
41}
42
43#[cfg(feature = "zeroize")]
44impl zeroize::DefaultIsZeroes for Fp {}
45
46impl ConstantTimeEq for Fp {
47    fn ct_eq(&self, other: &Self) -> Choice {
48        self.0[0].ct_eq(&other.0[0])
49            & self.0[1].ct_eq(&other.0[1])
50            & self.0[2].ct_eq(&other.0[2])
51            & self.0[3].ct_eq(&other.0[3])
52            & self.0[4].ct_eq(&other.0[4])
53            & self.0[5].ct_eq(&other.0[5])
54    }
55}
56
57// impl Eq for Fp {}
58// impl PartialEq for Fp {
59//     #[inline]
60//     fn eq(&self, other: &Self) -> bool {
61//         bool::from(self.ct_eq(other))
62//     }
63// }
64
65impl Ord for Fp {
66    fn cmp(&self, other: &Self) -> Ordering {
67        let left = self.to_repr().0;
68        let right = other.to_repr().0;
69        left.iter()
70            .zip(right.iter())
71            .rev()
72            .find_map(|(left_byte, right_byte)| match left_byte.cmp(right_byte) {
73                Ordering::Equal => None,
74                res => Some(res),
75            })
76            .unwrap_or(Ordering::Equal)
77    }
78}
79
80impl PartialOrd for Fp {
81    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
82        Some(self.cmp(other))
83    }
84}
85
86impl ConditionallySelectable for Fp {
87    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
88        Fp([
89            u64::conditional_select(&a.0[0], &b.0[0], choice),
90            u64::conditional_select(&a.0[1], &b.0[1], choice),
91            u64::conditional_select(&a.0[2], &b.0[2], choice),
92            u64::conditional_select(&a.0[3], &b.0[3], choice),
93            u64::conditional_select(&a.0[4], &b.0[4], choice),
94            u64::conditional_select(&a.0[5], &b.0[5], choice),
95        ])
96    }
97}
98
99impl From<u64> for Fp {
100    fn from(value: u64) -> Self {
101        Self([value, 0, 0, 0, 0, 0]) * R2
102    }
103}
104
105/// p = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
106const MODULUS: [u64; 6] = [
107    0xb9fe_ffff_ffff_aaab,
108    0x1eab_fffe_b153_ffff,
109    0x6730_d2a0_f6b0_f624,
110    0x6477_4b84_f385_12bf,
111    0x4b1b_a7b6_434b_acd7,
112    0x1a01_11ea_397f_e69a,
113];
114
115/// INV = -(p^{-1} mod 2^64) mod 2^64
116const INV: u64 = 0x89f3_fffc_fffc_fffd;
117
118/// R = 2^384 mod p
119const R: Fp = Fp([
120    0x7609_0000_0002_fffd,
121    0xebf4_000b_c40c_0002,
122    0x5f48_9857_53c7_58ba,
123    0x77ce_5853_7052_5745,
124    0x5c07_1a97_a256_ec6d,
125    0x15f6_5ec3_fa80_e493,
126]);
127
128/// R2 = 2^(384*2) mod p
129const R2: Fp = Fp([
130    0xf4df_1f34_1c34_1746,
131    0x0a76_e6a6_09d1_04f1,
132    0x8de5_476c_4c95_b6d5,
133    0x67eb_88a9_939d_83c0,
134    0x9a79_3e85_b519_952d,
135    0x1198_8fe5_92ca_e3aa,
136]);
137
138/// R3 = 2^(384*3) mod p
139const R3: Fp = Fp([
140    0xed48_ac6b_d94c_a1e0,
141    0x315f_831e_03a7_adf8,
142    0x9a53_352a_615e_29dd,
143    0x34c0_4e5e_921e_1761,
144    0x2512_d435_6572_4728,
145    0x0aa6_3460_9175_5d4d,
146]);
147
148/// Fp(1/2)
149/// sage: modulus = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
150/// sage: hex(((1 / 2) * (2^384)) % modulus)
151/// '0x17fbb8571a006596d3916126f2d14ca26e22d1ec31ebb502633cb57c253c276f855000053ab000011804000000015554'
152const TWO_INV: Fp = Fp([
153    0x1804000000015554,
154    0x855000053ab00001,
155    0x633cb57c253c276f,
156    0x6e22d1ec31ebb502,
157    0xd3916126f2d14ca2,
158    0x17fbb8571a006596,
159]);
160
161/// Generator of the field.
162/// sage: modulus = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
163/// sage: hex((2 * (2^384)) % modulus)
164/// '0x11ebab9dbb81e28c6cf28d7901622c038b256521ed1f9bcb57605e0db0ddbb51b93c0018d6c40005321300000006554f'
165const GENERATOR: Fp = Fp([
166    0x321300000006554f,
167    0xb93c0018d6c40005,
168    0x57605e0db0ddbb51,
169    0x8b256521ed1f9bcb,
170    0x6cf28d7901622c03,
171    0x11ebab9dbb81e28c,
172]);
173
174/// Primitive root of unity
175/// sage: modulus = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
176/// sage: hex((GF(modulus)(2) ^ ((modulus - 1) >> 1)) * (2^384))
177/// '0x40ab3263eff0206ef148d1ea0f4c069eca8f3318332bb7a07e83a49a2e99d6932b7fff2ed47fffd43f5fffffffcaaae'
178const ROOT_OF_UNITY: Fp = Fp([
179    0x43f5fffffffcaaae,
180    0x32b7fff2ed47fffd,
181    0x07e83a49a2e99d69,
182    0xeca8f3318332bb7a,
183    0xef148d1ea0f4c069,
184    0x40ab3263eff0206,
185]);
186
187/// Inverse of the primitive root of unity.
188/// sage: modulus = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
189/// sage: hex((1 / (GF(modulus)(2) ^ ((modulus - 1) >> 1))) * (2^384))
190/// '0x40ab3263eff0206ef148d1ea0f4c069eca8f3318332bb7a07e83a49a2e99d6932b7fff2ed47fffd43f5fffffffcaaae'
191const ROOT_OF_UNITY_INV: Fp = Fp([
192    0x43f5fffffffcaaae,
193    0x32b7fff2ed47fffd,
194    0x07e83a49a2e99d69,
195    0xeca8f3318332bb7a,
196    0xef148d1ea0f4c069,
197    0x40ab3263eff0206,
198]);
199
200/// DELTA
201/// DELTA
202/// sage: modulus = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
203/// sage: hex((GF(modulus)(2) ^ (2 ^ 1)) * (2^384))
204/// '0x9d645513d83de7e8ec9733bbf78ab2fb1d37ebee6ba24d7478fe97a6b0a807f53cc0032fc34000aaa270000000cfff3'
205const DELTA: Fp = Fp([
206    0xaa270000000cfff3,
207    0x53cc0032fc34000a,
208    0x478fe97a6b0a807f,
209    0xb1d37ebee6ba24d7,
210    0x8ec9733bbf78ab2f,
211    0x9d645513d83de7e,
212]);
213
214/// ZETA
215/// sage: modulus = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
216/// sage: hex((1 / (GF(modulus)(2) ^ ((modulus - 1) // 3))) * (2^384))
217/// '0x18f020655463874103f97d6e83d050d28eb60ebe01bacb9e587042afd3851b955dab22461fcda5d2cd03c9e48671f071'
218const ZETA: Fp = Fp([
219    0xcd03c9e48671f071,
220    0x5dab22461fcda5d2,
221    0x587042afd3851b95,
222    0x8eb60ebe01bacb9e,
223    0x03f97d6e83d050d2,
224    0x18f0206554638741,
225]);
226
227impl<'a> Neg for &'a Fp {
228    type Output = Fp;
229
230    #[inline]
231    fn neg(self) -> Fp {
232        self.neg()
233    }
234}
235
236impl Neg for Fp {
237    type Output = Fp;
238
239    #[inline]
240    fn neg(self) -> Fp {
241        -&self
242    }
243}
244
245impl<'a, 'b> Sub<&'b Fp> for &'a Fp {
246    type Output = Fp;
247
248    #[inline]
249    fn sub(self, rhs: &'b Fp) -> Fp {
250        self.sub(rhs)
251    }
252}
253
254impl<'a, 'b> Add<&'b Fp> for &'a Fp {
255    type Output = Fp;
256
257    #[inline]
258    fn add(self, rhs: &'b Fp) -> Fp {
259        self.add(rhs)
260    }
261}
262
263impl<'a, 'b> Mul<&'b Fp> for &'a Fp {
264    type Output = Fp;
265
266    #[inline]
267    fn mul(self, rhs: &'b Fp) -> Fp {
268        self.mul(rhs)
269    }
270}
271
272impl_binops_additive!(Fp, Fp);
273impl_binops_multiplicative!(Fp, Fp);
274
275impl<T> core::iter::Sum<T> for Fp
276where
277    T: core::borrow::Borrow<Fp>,
278{
279    fn sum<I>(iter: I) -> Self
280    where
281        I: Iterator<Item = T>,
282    {
283        iter.fold(Self::zero(), |acc, item| acc + item.borrow())
284    }
285}
286
287impl<T> core::iter::Product<T> for Fp
288where
289    T: core::borrow::Borrow<Fp>,
290{
291    fn product<I>(iter: I) -> Self
292    where
293        I: Iterator<Item = T>,
294    {
295        iter.fold(Self::one(), |acc, item| acc * item.borrow())
296    }
297}
298
299impl Field for Fp {
300    const ZERO: Self = Fp::zero();
301    const ONE: Self = Fp::one();
302
303    fn random(rng: impl RngCore) -> Self {
304        Self::random(rng)
305    }
306
307    fn square(&self) -> Self {
308        self.square()
309    }
310
311    fn double(&self) -> Self {
312        self.add(self)
313    }
314
315    fn invert(&self) -> CtOption<Self> {
316        self.invert()
317    }
318
319    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
320        ff::helpers::sqrt_ratio_generic(num, div)
321    }
322
323    fn sqrt(&self) -> CtOption<Self> {
324        self.sqrt()
325    }
326}
327
328/// This struct represents the [`Fp`] struct serialized as an array of 48 bytes
329/// in Little Endian.
330#[derive(Debug, Clone, Copy)]
331pub struct ReprFp(pub(crate) [u8; 48]);
332
333impl AsMut<[u8]> for ReprFp {
334    fn as_mut(&mut self) -> &mut [u8] {
335        &mut self.0[..]
336    }
337}
338
339impl AsRef<[u8]> for ReprFp {
340    fn as_ref(&self) -> &[u8] {
341        &self.0[..]
342    }
343}
344
345impl AsRef<[u8; 48]> for ReprFp {
346    fn as_ref(&self) -> &[u8; 48] {
347        &self.0
348    }
349}
350
351impl From<[u8; 48]> for ReprFp {
352    fn from(value: [u8; 48]) -> Self {
353        // This uses little endian and so, assumes the array passed in is
354        // in that format.
355        Self(value)
356    }
357}
358
359impl Default for ReprFp {
360    fn default() -> Self {
361        Self([0u8; 48])
362    }
363}
364
365impl PrimeField for Fp {
366    type Repr = ReprFp;
367
368    fn from_repr(r: Self::Repr) -> CtOption<Self> {
369        // This uses little endian and so, assumes the array passed in is
370        // in that format.
371        Self::from_bytes(&r.0)
372    }
373
374    fn to_repr(&self) -> Self::Repr {
375        ReprFp(self.to_bytes())
376    }
377
378    fn is_odd(&self) -> Choice {
379        Choice::from(self.to_bytes()[0] & 1)
380    }
381
382    const MODULUS: &'static str = "0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab";
383    const NUM_BITS: u32 = 381;
384    const CAPACITY: u32 = Self::NUM_BITS - 1;
385    const TWO_INV: Self = TWO_INV;
386    const MULTIPLICATIVE_GENERATOR: Self = GENERATOR;
387    const S: u32 = 1;
388    const ROOT_OF_UNITY: Self = ROOT_OF_UNITY;
389    const ROOT_OF_UNITY_INV: Self = ROOT_OF_UNITY_INV;
390    const DELTA: Self = DELTA;
391}
392
393impl WithSmallOrderMulGroup<3> for Fp {
394    const ZETA: Self = ZETA;
395}
396
397impl Fp {
398    /// Returns zero, the additive identity.
399    #[inline]
400    pub const fn zero() -> Fp {
401        Fp([0, 0, 0, 0, 0, 0])
402    }
403
404    /// Returns one, the multiplicative identity.
405    #[inline]
406    pub const fn one() -> Fp {
407        R
408    }
409
410    /// Attempts to convert a little-endian byte representation of
411    /// a scalar into an `Fp`, failing if the input is not canonical.
412    pub fn from_bytes(bytes: &[u8; 48]) -> CtOption<Fp> {
413        let mut tmp = Fp([0, 0, 0, 0, 0, 0]);
414
415        tmp.0[0] = u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[0..8]).unwrap());
416        tmp.0[1] = u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[8..16]).unwrap());
417        tmp.0[2] = u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[16..24]).unwrap());
418        tmp.0[3] = u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[24..32]).unwrap());
419        tmp.0[4] = u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[32..40]).unwrap());
420        tmp.0[5] = u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[40..48]).unwrap());
421
422        // Try to subtract the modulus
423        let (_, borrow) = sbb(tmp.0[0], MODULUS[0], 0);
424        let (_, borrow) = sbb(tmp.0[1], MODULUS[1], borrow);
425        let (_, borrow) = sbb(tmp.0[2], MODULUS[2], borrow);
426        let (_, borrow) = sbb(tmp.0[3], MODULUS[3], borrow);
427        let (_, borrow) = sbb(tmp.0[4], MODULUS[4], borrow);
428        let (_, borrow) = sbb(tmp.0[5], MODULUS[5], borrow);
429
430        // If the element is smaller than MODULUS then the
431        // subtraction will underflow, producing a borrow value
432        // of 0xffff...ffff. Otherwise, it'll be zero.
433        let is_some = (borrow as u8) & 1;
434
435        // Convert to Montgomery form by computing
436        // (a.R^0 * R^2) / R = a.R
437        tmp *= &R2;
438
439        CtOption::new(tmp, Choice::from(is_some))
440    }
441
442    /// Attempts to convert a big-endian byte representation of
443    /// a scalar into an `Fp`, failing if the input is not canonical.
444    pub fn from_bytes_be(bytes: &[u8; 48]) -> CtOption<Fp> {
445        let mut tmp = Fp([0, 0, 0, 0, 0, 0]);
446
447        tmp.0[5] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[0..8]).unwrap());
448        tmp.0[4] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[8..16]).unwrap());
449        tmp.0[3] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[16..24]).unwrap());
450        tmp.0[2] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[24..32]).unwrap());
451        tmp.0[1] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[32..40]).unwrap());
452        tmp.0[0] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[40..48]).unwrap());
453
454        // Try to subtract the modulus
455        let (_, borrow) = sbb(tmp.0[0], MODULUS[0], 0);
456        let (_, borrow) = sbb(tmp.0[1], MODULUS[1], borrow);
457        let (_, borrow) = sbb(tmp.0[2], MODULUS[2], borrow);
458        let (_, borrow) = sbb(tmp.0[3], MODULUS[3], borrow);
459        let (_, borrow) = sbb(tmp.0[4], MODULUS[4], borrow);
460        let (_, borrow) = sbb(tmp.0[5], MODULUS[5], borrow);
461
462        // If the element is smaller than MODULUS then the
463        // subtraction will underflow, producing a borrow value
464        // of 0xffff...ffff. Otherwise, it'll be zero.
465        let is_some = (borrow as u8) & 1;
466
467        // Convert to Montgomery form by computing
468        // (a.R^0 * R^2) / R = a.R
469        tmp *= &R2;
470
471        CtOption::new(tmp, Choice::from(is_some))
472    }
473
474    /// Converts an element of `Fp` into a byte representation in
475    /// big-endian byte order.
476    pub fn to_bytes_be(self) -> [u8; 48] {
477        // Turn into canonical form by computing
478        // (a.R) / R = a
479        let tmp = Fp::montgomery_reduce(
480            self.0[0], self.0[1], self.0[2], self.0[3], self.0[4], self.0[5], 0, 0, 0, 0, 0, 0,
481        );
482
483        let mut res = [0; 48];
484        res[0..8].copy_from_slice(&tmp.0[5].to_be_bytes());
485        res[8..16].copy_from_slice(&tmp.0[4].to_be_bytes());
486        res[16..24].copy_from_slice(&tmp.0[3].to_be_bytes());
487        res[24..32].copy_from_slice(&tmp.0[2].to_be_bytes());
488        res[32..40].copy_from_slice(&tmp.0[1].to_be_bytes());
489        res[40..48].copy_from_slice(&tmp.0[0].to_be_bytes());
490
491        res
492    }
493
494    /// Converts an element of `Fp` into a byte representation in
495    /// little-endian byte order.
496    pub fn to_bytes(self) -> [u8; 48] {
497        // Turn into canonical form by computing
498        // (a.R) / R = a
499        let tmp = Fp::montgomery_reduce(
500            self.0[0], self.0[1], self.0[2], self.0[3], self.0[4], self.0[5], 0, 0, 0, 0, 0, 0,
501        );
502
503        let mut res = [0; 48];
504        res[0..8].copy_from_slice(&tmp.0[0].to_le_bytes());
505        res[8..16].copy_from_slice(&tmp.0[1].to_le_bytes());
506        res[16..24].copy_from_slice(&tmp.0[2].to_le_bytes());
507        res[24..32].copy_from_slice(&tmp.0[3].to_le_bytes());
508        res[32..40].copy_from_slice(&tmp.0[4].to_le_bytes());
509        res[40..48].copy_from_slice(&tmp.0[5].to_le_bytes());
510
511        res
512    }
513
514    /// Generates a new uniformly-distributed random element using the given randomness.
515    pub fn random(mut rng: impl RngCore) -> Fp {
516        let mut bytes = [0u8; 96];
517        rng.fill_bytes(&mut bytes);
518
519        // Parse the random bytes as a big-endian number, to match Fp encoding order.
520        Fp::from_u768([
521            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[0..8]).unwrap()),
522            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[8..16]).unwrap()),
523            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[16..24]).unwrap()),
524            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[24..32]).unwrap()),
525            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[32..40]).unwrap()),
526            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[40..48]).unwrap()),
527            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[48..56]).unwrap()),
528            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[56..64]).unwrap()),
529            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[64..72]).unwrap()),
530            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[72..80]).unwrap()),
531            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[80..88]).unwrap()),
532            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[88..96]).unwrap()),
533        ])
534    }
535
536    /// Reduces a big-endian 64-bit limb representation of a 768-bit number.
537    fn from_u768(limbs: [u64; 12]) -> Fp {
538        // We reduce an arbitrary 768-bit number by decomposing it into two 384-bit digits
539        // with the higher bits multiplied by 2^384. Thus, we perform two reductions
540        //
541        // 1. the lower bits are multiplied by R^2, as normal
542        // 2. the upper bits are multiplied by R^2 * 2^384 = R^3
543        //
544        // and computing their sum in the field. It remains to see that arbitrary 384-bit
545        // numbers can be placed into Montgomery form safely using the reduction. The
546        // reduction works so long as the product is less than R=2^384 multiplied by
547        // the modulus. This holds because for any `c` smaller than the modulus, we have
548        // that (2^384 - 1)*c is an acceptable product for the reduction. Therefore, the
549        // reduction always works so long as `c` is in the field; in this case it is either the
550        // constant `R2` or `R3`.
551        let d1 = Fp([limbs[11], limbs[10], limbs[9], limbs[8], limbs[7], limbs[6]]);
552        let d0 = Fp([limbs[5], limbs[4], limbs[3], limbs[2], limbs[1], limbs[0]]);
553        // Convert to Montgomery form
554        d0 * R2 + d1 * R3
555    }
556
557    /// Returns whether or not this element is strictly lexicographically
558    /// larger than its negation.
559    pub fn lexicographically_largest(&self) -> Choice {
560        // This can be determined by checking to see if the element is
561        // larger than (p - 1) // 2. If we subtract by ((p - 1) // 2) + 1
562        // and there is no underflow, then the element must be larger than
563        // (p - 1) // 2.
564
565        // First, because self is in Montgomery form we need to reduce it
566        let tmp = Fp::montgomery_reduce(
567            self.0[0], self.0[1], self.0[2], self.0[3], self.0[4], self.0[5], 0, 0, 0, 0, 0, 0,
568        );
569
570        let (_, borrow) = sbb(tmp.0[0], 0xdcff_7fff_ffff_d556, 0);
571        let (_, borrow) = sbb(tmp.0[1], 0x0f55_ffff_58a9_ffff, borrow);
572        let (_, borrow) = sbb(tmp.0[2], 0xb398_6950_7b58_7b12, borrow);
573        let (_, borrow) = sbb(tmp.0[3], 0xb23b_a5c2_79c2_895f, borrow);
574        let (_, borrow) = sbb(tmp.0[4], 0x258d_d3db_21a5_d66b, borrow);
575        let (_, borrow) = sbb(tmp.0[5], 0x0d00_88f5_1cbf_f34d, borrow);
576
577        // If the element was smaller, the subtraction will underflow
578        // producing a borrow value of 0xffff...ffff, otherwise it will
579        // be zero. We create a Choice representing true if there was
580        // overflow (and so this element is not lexicographically larger
581        // than its negation) and then negate it.
582
583        !Choice::from((borrow as u8) & 1)
584    }
585
586    /// Constructs an element of `Fp` without checking that it is
587    /// canonical.
588    pub const fn from_raw_unchecked(v: [u64; 6]) -> Fp {
589        Fp(v)
590    }
591
592    /// Although this is labeled "vartime", it is only
593    /// variable time with respect to the exponent. It
594    /// is also not exposed in the public API.
595    pub fn pow_vartime(&self, by: &[u64; 6]) -> Self {
596        let mut res = Self::one();
597        for e in by.iter().rev() {
598            for i in (0..64).rev() {
599                res = res.square();
600
601                if ((*e >> i) & 1) == 1 {
602                    res *= self;
603                }
604            }
605        }
606        res
607    }
608
609    #[inline]
610    /// Performs the square root of an element in constant time.
611    ///
612    /// NOTE:
613    /// We use Shank's method, as p = 3 (mod 4). This means
614    /// we only need to exponentiate by (p+1)/4. This only
615    /// works for elements that are actually quadratic residue,
616    /// so we check that we got the correct result at the end.
617    pub fn sqrt(&self) -> CtOption<Self> {
618        let sqrt = self.pow_vartime(&[
619            0xee7f_bfff_ffff_eaab,
620            0x07aa_ffff_ac54_ffff,
621            0xd9cc_34a8_3dac_3d89,
622            0xd91d_d2e1_3ce1_44af,
623            0x92c6_e9ed_90d2_eb35,
624            0x0680_447a_8e5f_f9a6,
625        ]);
626
627        CtOption::new(sqrt, sqrt.square().ct_eq(self))
628    }
629
630    #[inline]
631    /// Computes the multiplicative inverse of this field
632    /// element, returning None in the case that this element
633    /// is zero.
634    pub fn invert(&self) -> CtOption<Self> {
635        // Exponentiate by p - 2
636        let t = self.pow_vartime(&[
637            0xb9fe_ffff_ffff_aaa9,
638            0x1eab_fffe_b153_ffff,
639            0x6730_d2a0_f6b0_f624,
640            0x6477_4b84_f385_12bf,
641            0x4b1b_a7b6_434b_acd7,
642            0x1a01_11ea_397f_e69a,
643        ]);
644
645        CtOption::new(t, !self.is_zero())
646    }
647
648    #[inline]
649    const fn subtract_p(&self) -> Fp {
650        let (r0, borrow) = sbb(self.0[0], MODULUS[0], 0);
651        let (r1, borrow) = sbb(self.0[1], MODULUS[1], borrow);
652        let (r2, borrow) = sbb(self.0[2], MODULUS[2], borrow);
653        let (r3, borrow) = sbb(self.0[3], MODULUS[3], borrow);
654        let (r4, borrow) = sbb(self.0[4], MODULUS[4], borrow);
655        let (r5, borrow) = sbb(self.0[5], MODULUS[5], borrow);
656
657        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
658        // borrow = 0x000...000. Thus, we use it as a mask!
659        let r0 = (self.0[0] & borrow) | (r0 & !borrow);
660        let r1 = (self.0[1] & borrow) | (r1 & !borrow);
661        let r2 = (self.0[2] & borrow) | (r2 & !borrow);
662        let r3 = (self.0[3] & borrow) | (r3 & !borrow);
663        let r4 = (self.0[4] & borrow) | (r4 & !borrow);
664        let r5 = (self.0[5] & borrow) | (r5 & !borrow);
665
666        Fp([r0, r1, r2, r3, r4, r5])
667    }
668
669    #[inline]
670    /// Performs constant time addition of two elements.
671    pub const fn add(&self, rhs: &Fp) -> Fp {
672        let (d0, carry) = adc(self.0[0], rhs.0[0], 0);
673        let (d1, carry) = adc(self.0[1], rhs.0[1], carry);
674        let (d2, carry) = adc(self.0[2], rhs.0[2], carry);
675        let (d3, carry) = adc(self.0[3], rhs.0[3], carry);
676        let (d4, carry) = adc(self.0[4], rhs.0[4], carry);
677        let (d5, _) = adc(self.0[5], rhs.0[5], carry);
678
679        // Attempt to subtract the modulus, to ensure the value
680        // is smaller than the modulus.
681        (Fp([d0, d1, d2, d3, d4, d5])).subtract_p()
682    }
683
684    #[inline]
685    /// Performs constant time negation of an element.
686    pub const fn neg(&self) -> Fp {
687        let (d0, borrow) = sbb(MODULUS[0], self.0[0], 0);
688        let (d1, borrow) = sbb(MODULUS[1], self.0[1], borrow);
689        let (d2, borrow) = sbb(MODULUS[2], self.0[2], borrow);
690        let (d3, borrow) = sbb(MODULUS[3], self.0[3], borrow);
691        let (d4, borrow) = sbb(MODULUS[4], self.0[4], borrow);
692        let (d5, _) = sbb(MODULUS[5], self.0[5], borrow);
693
694        // Let's use a mask if `self` was zero, which would mean
695        // the result of the subtraction is p.
696        let mask = (((self.0[0] | self.0[1] | self.0[2] | self.0[3] | self.0[4] | self.0[5]) == 0)
697            as u64)
698            .wrapping_sub(1);
699
700        Fp([
701            d0 & mask,
702            d1 & mask,
703            d2 & mask,
704            d3 & mask,
705            d4 & mask,
706            d5 & mask,
707        ])
708    }
709
710    #[inline]
711    /// Performs constant time subtraction of two elements.
712    pub const fn sub(&self, rhs: &Fp) -> Fp {
713        (&rhs.neg()).add(self)
714    }
715
716    /// Returns `c = a.zip(b).fold(0, |acc, (a_i, b_i)| acc + a_i * b_i)`.
717    ///
718    /// Implements Algorithm 2 from Patrick Longa's
719    /// [ePrint 2022-367](https://eprint.iacr.org/2022/367) §3.
720    #[inline]
721    pub(crate) fn sum_of_products<const T: usize>(a: [Fp; T], b: [Fp; T]) -> Fp {
722        // For a single `a x b` multiplication, operand scanning (schoolbook) takes each
723        // limb of `a` in turn, and multiplies it by all of the limbs of `b` to compute
724        // the result as a double-width intermediate representation, which is then fully
725        // reduced at the end. Here however we have pairs of multiplications (a_i, b_i),
726        // the results of which are summed.
727        //
728        // The intuition for this algorithm is two-fold:
729        // - We can interleave the operand scanning for each pair, by processing the jth
730        //   limb of each `a_i` together. As these have the same offset within the overall
731        //   operand scanning flow, their results can be summed directly.
732        // - We can interleave the multiplication and reduction steps, resulting in a
733        //   single bitshift by the limb size after each iteration. This means we only
734        //   need to store a single extra limb overall, instead of keeping around all the
735        //   intermediate results and eventually having twice as many limbs.
736
737        // Algorithm 2, line 2
738        let (u0, u1, u2, u3, u4, u5) =
739            (0..6).fold((0, 0, 0, 0, 0, 0), |(u0, u1, u2, u3, u4, u5), j| {
740                // Algorithm 2, line 3
741                // For each pair in the overall sum of products:
742                let (t0, t1, t2, t3, t4, t5, t6) = (0..T).fold(
743                    (u0, u1, u2, u3, u4, u5, 0),
744                    |(t0, t1, t2, t3, t4, t5, t6), i| {
745                        // Compute digit_j x row and accumulate into `u`.
746                        let (t0, carry) = mac(t0, a[i].0[j], b[i].0[0], 0);
747                        let (t1, carry) = mac(t1, a[i].0[j], b[i].0[1], carry);
748                        let (t2, carry) = mac(t2, a[i].0[j], b[i].0[2], carry);
749                        let (t3, carry) = mac(t3, a[i].0[j], b[i].0[3], carry);
750                        let (t4, carry) = mac(t4, a[i].0[j], b[i].0[4], carry);
751                        let (t5, carry) = mac(t5, a[i].0[j], b[i].0[5], carry);
752                        let (t6, _) = adc(t6, 0, carry);
753
754                        (t0, t1, t2, t3, t4, t5, t6)
755                    },
756                );
757
758                // Algorithm 2, lines 4-5
759                // This is a single step of the usual Montgomery reduction process.
760                let k = t0.wrapping_mul(INV);
761                let (_, carry) = mac(t0, k, MODULUS[0], 0);
762                let (r1, carry) = mac(t1, k, MODULUS[1], carry);
763                let (r2, carry) = mac(t2, k, MODULUS[2], carry);
764                let (r3, carry) = mac(t3, k, MODULUS[3], carry);
765                let (r4, carry) = mac(t4, k, MODULUS[4], carry);
766                let (r5, carry) = mac(t5, k, MODULUS[5], carry);
767                let (r6, _) = adc(t6, 0, carry);
768
769                (r1, r2, r3, r4, r5, r6)
770            });
771
772        // Because we represent F_p elements in non-redundant form, we need a final
773        // conditional subtraction to ensure the output is in range.
774        (&Fp([u0, u1, u2, u3, u4, u5])).subtract_p()
775    }
776
777    #[inline(always)]
778    pub(crate) const fn montgomery_reduce(
779        t0: u64,
780        t1: u64,
781        t2: u64,
782        t3: u64,
783        t4: u64,
784        t5: u64,
785        t6: u64,
786        t7: u64,
787        t8: u64,
788        t9: u64,
789        t10: u64,
790        t11: u64,
791    ) -> Self {
792        // The Montgomery reduction here is based on Algorithm 14.32 in
793        // Handbook of Applied Cryptography
794        // <http://cacr.uwaterloo.ca/hac/about/chap14.pdf>.
795
796        let k = t0.wrapping_mul(INV);
797        let (_, carry) = mac(t0, k, MODULUS[0], 0);
798        let (r1, carry) = mac(t1, k, MODULUS[1], carry);
799        let (r2, carry) = mac(t2, k, MODULUS[2], carry);
800        let (r3, carry) = mac(t3, k, MODULUS[3], carry);
801        let (r4, carry) = mac(t4, k, MODULUS[4], carry);
802        let (r5, carry) = mac(t5, k, MODULUS[5], carry);
803        let (r6, r7) = adc(t6, 0, carry);
804
805        let k = r1.wrapping_mul(INV);
806        let (_, carry) = mac(r1, k, MODULUS[0], 0);
807        let (r2, carry) = mac(r2, k, MODULUS[1], carry);
808        let (r3, carry) = mac(r3, k, MODULUS[2], carry);
809        let (r4, carry) = mac(r4, k, MODULUS[3], carry);
810        let (r5, carry) = mac(r5, k, MODULUS[4], carry);
811        let (r6, carry) = mac(r6, k, MODULUS[5], carry);
812        let (r7, r8) = adc(t7, r7, carry);
813
814        let k = r2.wrapping_mul(INV);
815        let (_, carry) = mac(r2, k, MODULUS[0], 0);
816        let (r3, carry) = mac(r3, k, MODULUS[1], carry);
817        let (r4, carry) = mac(r4, k, MODULUS[2], carry);
818        let (r5, carry) = mac(r5, k, MODULUS[3], carry);
819        let (r6, carry) = mac(r6, k, MODULUS[4], carry);
820        let (r7, carry) = mac(r7, k, MODULUS[5], carry);
821        let (r8, r9) = adc(t8, r8, carry);
822
823        let k = r3.wrapping_mul(INV);
824        let (_, carry) = mac(r3, k, MODULUS[0], 0);
825        let (r4, carry) = mac(r4, k, MODULUS[1], carry);
826        let (r5, carry) = mac(r5, k, MODULUS[2], carry);
827        let (r6, carry) = mac(r6, k, MODULUS[3], carry);
828        let (r7, carry) = mac(r7, k, MODULUS[4], carry);
829        let (r8, carry) = mac(r8, k, MODULUS[5], carry);
830        let (r9, r10) = adc(t9, r9, carry);
831
832        let k = r4.wrapping_mul(INV);
833        let (_, carry) = mac(r4, k, MODULUS[0], 0);
834        let (r5, carry) = mac(r5, k, MODULUS[1], carry);
835        let (r6, carry) = mac(r6, k, MODULUS[2], carry);
836        let (r7, carry) = mac(r7, k, MODULUS[3], carry);
837        let (r8, carry) = mac(r8, k, MODULUS[4], carry);
838        let (r9, carry) = mac(r9, k, MODULUS[5], carry);
839        let (r10, r11) = adc(t10, r10, carry);
840
841        let k = r5.wrapping_mul(INV);
842        let (_, carry) = mac(r5, k, MODULUS[0], 0);
843        let (r6, carry) = mac(r6, k, MODULUS[1], carry);
844        let (r7, carry) = mac(r7, k, MODULUS[2], carry);
845        let (r8, carry) = mac(r8, k, MODULUS[3], carry);
846        let (r9, carry) = mac(r9, k, MODULUS[4], carry);
847        let (r10, carry) = mac(r10, k, MODULUS[5], carry);
848        let (r11, _) = adc(t11, r11, carry);
849
850        // Attempt to subtract the modulus, to ensure the value
851        // is smaller than the modulus.
852        (&Fp([r6, r7, r8, r9, r10, r11])).subtract_p()
853    }
854
855    #[inline]
856    /// Performs constant time multiplication of two elements.
857    pub const fn mul(&self, rhs: &Fp) -> Fp {
858        let (t0, carry) = mac(0, self.0[0], rhs.0[0], 0);
859        let (t1, carry) = mac(0, self.0[0], rhs.0[1], carry);
860        let (t2, carry) = mac(0, self.0[0], rhs.0[2], carry);
861        let (t3, carry) = mac(0, self.0[0], rhs.0[3], carry);
862        let (t4, carry) = mac(0, self.0[0], rhs.0[4], carry);
863        let (t5, t6) = mac(0, self.0[0], rhs.0[5], carry);
864
865        let (t1, carry) = mac(t1, self.0[1], rhs.0[0], 0);
866        let (t2, carry) = mac(t2, self.0[1], rhs.0[1], carry);
867        let (t3, carry) = mac(t3, self.0[1], rhs.0[2], carry);
868        let (t4, carry) = mac(t4, self.0[1], rhs.0[3], carry);
869        let (t5, carry) = mac(t5, self.0[1], rhs.0[4], carry);
870        let (t6, t7) = mac(t6, self.0[1], rhs.0[5], carry);
871
872        let (t2, carry) = mac(t2, self.0[2], rhs.0[0], 0);
873        let (t3, carry) = mac(t3, self.0[2], rhs.0[1], carry);
874        let (t4, carry) = mac(t4, self.0[2], rhs.0[2], carry);
875        let (t5, carry) = mac(t5, self.0[2], rhs.0[3], carry);
876        let (t6, carry) = mac(t6, self.0[2], rhs.0[4], carry);
877        let (t7, t8) = mac(t7, self.0[2], rhs.0[5], carry);
878
879        let (t3, carry) = mac(t3, self.0[3], rhs.0[0], 0);
880        let (t4, carry) = mac(t4, self.0[3], rhs.0[1], carry);
881        let (t5, carry) = mac(t5, self.0[3], rhs.0[2], carry);
882        let (t6, carry) = mac(t6, self.0[3], rhs.0[3], carry);
883        let (t7, carry) = mac(t7, self.0[3], rhs.0[4], carry);
884        let (t8, t9) = mac(t8, self.0[3], rhs.0[5], carry);
885
886        let (t4, carry) = mac(t4, self.0[4], rhs.0[0], 0);
887        let (t5, carry) = mac(t5, self.0[4], rhs.0[1], carry);
888        let (t6, carry) = mac(t6, self.0[4], rhs.0[2], carry);
889        let (t7, carry) = mac(t7, self.0[4], rhs.0[3], carry);
890        let (t8, carry) = mac(t8, self.0[4], rhs.0[4], carry);
891        let (t9, t10) = mac(t9, self.0[4], rhs.0[5], carry);
892
893        let (t5, carry) = mac(t5, self.0[5], rhs.0[0], 0);
894        let (t6, carry) = mac(t6, self.0[5], rhs.0[1], carry);
895        let (t7, carry) = mac(t7, self.0[5], rhs.0[2], carry);
896        let (t8, carry) = mac(t8, self.0[5], rhs.0[3], carry);
897        let (t9, carry) = mac(t9, self.0[5], rhs.0[4], carry);
898        let (t10, t11) = mac(t10, self.0[5], rhs.0[5], carry);
899
900        Self::montgomery_reduce(t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11)
901    }
902
903    /// Squares this element.
904    #[inline]
905    pub const fn square(&self) -> Self {
906        let (t1, carry) = mac(0, self.0[0], self.0[1], 0);
907        let (t2, carry) = mac(0, self.0[0], self.0[2], carry);
908        let (t3, carry) = mac(0, self.0[0], self.0[3], carry);
909        let (t4, carry) = mac(0, self.0[0], self.0[4], carry);
910        let (t5, t6) = mac(0, self.0[0], self.0[5], carry);
911
912        let (t3, carry) = mac(t3, self.0[1], self.0[2], 0);
913        let (t4, carry) = mac(t4, self.0[1], self.0[3], carry);
914        let (t5, carry) = mac(t5, self.0[1], self.0[4], carry);
915        let (t6, t7) = mac(t6, self.0[1], self.0[5], carry);
916
917        let (t5, carry) = mac(t5, self.0[2], self.0[3], 0);
918        let (t6, carry) = mac(t6, self.0[2], self.0[4], carry);
919        let (t7, t8) = mac(t7, self.0[2], self.0[5], carry);
920
921        let (t7, carry) = mac(t7, self.0[3], self.0[4], 0);
922        let (t8, t9) = mac(t8, self.0[3], self.0[5], carry);
923
924        let (t9, t10) = mac(t9, self.0[4], self.0[5], 0);
925
926        let t11 = t10 >> 63;
927        let t10 = (t10 << 1) | (t9 >> 63);
928        let t9 = (t9 << 1) | (t8 >> 63);
929        let t8 = (t8 << 1) | (t7 >> 63);
930        let t7 = (t7 << 1) | (t6 >> 63);
931        let t6 = (t6 << 1) | (t5 >> 63);
932        let t5 = (t5 << 1) | (t4 >> 63);
933        let t4 = (t4 << 1) | (t3 >> 63);
934        let t3 = (t3 << 1) | (t2 >> 63);
935        let t2 = (t2 << 1) | (t1 >> 63);
936        let t1 = t1 << 1;
937
938        let (t0, carry) = mac(0, self.0[0], self.0[0], 0);
939        let (t1, carry) = adc(t1, 0, carry);
940        let (t2, carry) = mac(t2, self.0[1], self.0[1], carry);
941        let (t3, carry) = adc(t3, 0, carry);
942        let (t4, carry) = mac(t4, self.0[2], self.0[2], carry);
943        let (t5, carry) = adc(t5, 0, carry);
944        let (t6, carry) = mac(t6, self.0[3], self.0[3], carry);
945        let (t7, carry) = adc(t7, 0, carry);
946        let (t8, carry) = mac(t8, self.0[4], self.0[4], carry);
947        let (t9, carry) = adc(t9, 0, carry);
948        let (t10, carry) = mac(t10, self.0[5], self.0[5], carry);
949        let (t11, _) = adc(t11, 0, carry);
950
951        Self::montgomery_reduce(t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11)
952    }
953}
954
955impl ff::FromUniformBytes<64> for Fp {
956    /// Converts a 512-bit little endian integer into
957    /// an `Fq` by reducing by the modulus.
958    fn from_uniform_bytes(bytes: &[u8; 64]) -> Self {
959        Self::from_u512([
960            u64::from_le_bytes(bytes[0..8].try_into().unwrap()),
961            u64::from_le_bytes(bytes[8..16].try_into().unwrap()),
962            u64::from_le_bytes(bytes[16..24].try_into().unwrap()),
963            u64::from_le_bytes(bytes[24..32].try_into().unwrap()),
964            u64::from_le_bytes(bytes[32..40].try_into().unwrap()),
965            u64::from_le_bytes(bytes[40..48].try_into().unwrap()),
966            u64::from_le_bytes(bytes[48..56].try_into().unwrap()),
967            u64::from_le_bytes(bytes[56..64].try_into().unwrap()),
968        ])
969    }
970}
971
972impl Fp {
973    fn from_u512(limbs: [u64; 8]) -> Fp {
974        let d0 = Fp([limbs[0], limbs[1], limbs[2], limbs[3], limbs[4], limbs[5]]);
975        let d1 = Fp([limbs[6], limbs[7], 0, 0, 0, 0]);
976        // Convert to Montgomery form
977        d0 * R2 + d1 * R3
978    }
979}
980
981impl From<bool> for Fp {
982    fn from(bit: bool) -> Fp {
983        if bit {
984            Fp::one()
985        } else {
986            Fp::zero()
987        }
988    }
989}
990
991impl From<[u64; 6]> for Fp {
992    fn from(digits: [u64; 6]) -> Self {
993        Self::from_raw_unchecked(digits)
994    }
995}
996
997#[test]
998fn test_constants() {
999    assert_eq!(Fp::ONE.double(), GENERATOR);
1000    assert_eq!(Fp::ONE, Fp::ONE.double() * TWO_INV);
1001    assert_eq!(Fp::ONE, ROOT_OF_UNITY.pow([1 << Fp::S]));
1002    assert_eq!(Fp::ONE, ROOT_OF_UNITY * ROOT_OF_UNITY_INV);
1003    // sage: modulus = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
1004    // sage: hex((modulus - 1) >> 1)
1005    // '0xd0088f51cbff34d258dd3db21a5d66bb23ba5c279c2895fb39869507b587b120f55ffff58a9ffffdcff7fffffffd555'
1006    let t = [
1007        0xdcff7fffffffd555,
1008        0x0f55ffff58a9ffff,
1009        0xb39869507b587b12,
1010        0xb23ba5c279c2895f,
1011        0x258dd3db21a5d66b,
1012        0xd0088f51cbff34d,
1013    ];
1014    assert_eq!(Fp::ONE, DELTA.pow(t));
1015    assert_eq!(Fp::ONE, ZETA.pow([3]));
1016}
1017
1018#[test]
1019fn test_conditional_selection() {
1020    let a = Fp([1, 2, 3, 4, 5, 6]);
1021    let b = Fp([7, 8, 9, 10, 11, 12]);
1022
1023    assert_eq!(
1024        ConditionallySelectable::conditional_select(&a, &b, Choice::from(0u8)),
1025        a
1026    );
1027    assert_eq!(
1028        ConditionallySelectable::conditional_select(&a, &b, Choice::from(1u8)),
1029        b
1030    );
1031}
1032
1033#[test]
1034fn test_equality() {
1035    fn is_equal(a: &Fp, b: &Fp) -> bool {
1036        let eq = a == b;
1037        let ct_eq = a.ct_eq(b);
1038
1039        assert_eq!(eq, bool::from(ct_eq));
1040
1041        eq
1042    }
1043
1044    assert!(is_equal(&Fp([1, 2, 3, 4, 5, 6]), &Fp([1, 2, 3, 4, 5, 6])));
1045
1046    assert!(!is_equal(&Fp([7, 2, 3, 4, 5, 6]), &Fp([1, 2, 3, 4, 5, 6])));
1047    assert!(!is_equal(&Fp([1, 7, 3, 4, 5, 6]), &Fp([1, 2, 3, 4, 5, 6])));
1048    assert!(!is_equal(&Fp([1, 2, 7, 4, 5, 6]), &Fp([1, 2, 3, 4, 5, 6])));
1049    assert!(!is_equal(&Fp([1, 2, 3, 7, 5, 6]), &Fp([1, 2, 3, 4, 5, 6])));
1050    assert!(!is_equal(&Fp([1, 2, 3, 4, 7, 6]), &Fp([1, 2, 3, 4, 5, 6])));
1051    assert!(!is_equal(&Fp([1, 2, 3, 4, 5, 7]), &Fp([1, 2, 3, 4, 5, 6])));
1052}
1053
1054#[test]
1055fn test_squaring() {
1056    let a = Fp([
1057        0xd215_d276_8e83_191b,
1058        0x5085_d80f_8fb2_8261,
1059        0xce9a_032d_df39_3a56,
1060        0x3e9c_4fff_2ca0_c4bb,
1061        0x6436_b6f7_f4d9_5dfb,
1062        0x1060_6628_ad4a_4d90,
1063    ]);
1064    let b = Fp([
1065        0x33d9_c42a_3cb3_e235,
1066        0xdad1_1a09_4c4c_d455,
1067        0xa2f1_44bd_729a_aeba,
1068        0xd415_0932_be9f_feac,
1069        0xe27b_c7c4_7d44_ee50,
1070        0x14b6_a78d_3ec7_a560,
1071    ]);
1072
1073    assert_eq!(a.square(), b);
1074}
1075
1076#[test]
1077fn test_multiplication() {
1078    let a = Fp([
1079        0x0397_a383_2017_0cd4,
1080        0x734c_1b2c_9e76_1d30,
1081        0x5ed2_55ad_9a48_beb5,
1082        0x095a_3c6b_22a7_fcfc,
1083        0x2294_ce75_d4e2_6a27,
1084        0x1333_8bd8_7001_1ebb,
1085    ]);
1086    let b = Fp([
1087        0xb9c3_c7c5_b119_6af7,
1088        0x2580_e208_6ce3_35c1,
1089        0xf49a_ed3d_8a57_ef42,
1090        0x41f2_81e4_9846_e878,
1091        0xe076_2346_c384_52ce,
1092        0x0652_e893_26e5_7dc0,
1093    ]);
1094    let c = Fp([
1095        0xf96e_f3d7_11ab_5355,
1096        0xe8d4_59ea_00f1_48dd,
1097        0x53f7_354a_5f00_fa78,
1098        0x9e34_a4f3_125c_5f83,
1099        0x3fbe_0c47_ca74_c19e,
1100        0x01b0_6a8b_bd4a_dfe4,
1101    ]);
1102
1103    assert_eq!(a * b, c);
1104}
1105
1106#[test]
1107fn test_addition() {
1108    let a = Fp([
1109        0x5360_bb59_7867_8032,
1110        0x7dd2_75ae_799e_128e,
1111        0x5c5b_5071_ce4f_4dcf,
1112        0xcdb2_1f93_078d_bb3e,
1113        0xc323_65c5_e73f_474a,
1114        0x115a_2a54_89ba_be5b,
1115    ]);
1116    let b = Fp([
1117        0x9fd2_8773_3d23_dda0,
1118        0xb16b_f2af_738b_3554,
1119        0x3e57_a75b_d3cc_6d1d,
1120        0x900b_c0bd_627f_d6d6,
1121        0xd319_a080_efb2_45fe,
1122        0x15fd_caa4_e4bb_2091,
1123    ]);
1124    let c = Fp([
1125        0x3934_42cc_b58b_b327,
1126        0x1092_685f_3bd5_47e3,
1127        0x3382_252c_ab6a_c4c9,
1128        0xf946_94cb_7688_7f55,
1129        0x4b21_5e90_93a5_e071,
1130        0x0d56_e30f_34f5_f853,
1131    ]);
1132
1133    assert_eq!(a + b, c);
1134}
1135
1136#[test]
1137fn test_subtraction() {
1138    let a = Fp([
1139        0x5360_bb59_7867_8032,
1140        0x7dd2_75ae_799e_128e,
1141        0x5c5b_5071_ce4f_4dcf,
1142        0xcdb2_1f93_078d_bb3e,
1143        0xc323_65c5_e73f_474a,
1144        0x115a_2a54_89ba_be5b,
1145    ]);
1146    let b = Fp([
1147        0x9fd2_8773_3d23_dda0,
1148        0xb16b_f2af_738b_3554,
1149        0x3e57_a75b_d3cc_6d1d,
1150        0x900b_c0bd_627f_d6d6,
1151        0xd319_a080_efb2_45fe,
1152        0x15fd_caa4_e4bb_2091,
1153    ]);
1154    let c = Fp([
1155        0x6d8d_33e6_3b43_4d3d,
1156        0xeb12_82fd_b766_dd39,
1157        0x8534_7bb6_f133_d6d5,
1158        0xa21d_aa5a_9892_f727,
1159        0x3b25_6cfb_3ad8_ae23,
1160        0x155d_7199_de7f_8464,
1161    ]);
1162
1163    assert_eq!(a - b, c);
1164}
1165
1166#[test]
1167fn test_negation() {
1168    let a = Fp([
1169        0x5360_bb59_7867_8032,
1170        0x7dd2_75ae_799e_128e,
1171        0x5c5b_5071_ce4f_4dcf,
1172        0xcdb2_1f93_078d_bb3e,
1173        0xc323_65c5_e73f_474a,
1174        0x115a_2a54_89ba_be5b,
1175    ]);
1176    let b = Fp([
1177        0x669e_44a6_8798_2a79,
1178        0xa0d9_8a50_37b5_ed71,
1179        0x0ad5_822f_2861_a854,
1180        0x96c5_2bf1_ebf7_5781,
1181        0x87f8_41f0_5c0c_658c,
1182        0x08a6_e795_afc5_283e,
1183    ]);
1184
1185    assert_eq!(-a, b);
1186}
1187
1188#[test]
1189fn test_from_bytes() {
1190    let mut a = Fp([
1191        0xdc90_6d9b_e3f9_5dc8,
1192        0x8755_caf7_4596_91a1,
1193        0xcff1_a7f4_e958_3ab3,
1194        0x9b43_821f_849e_2284,
1195        0xf575_54f3_a297_4f3f,
1196        0x085d_bea8_4ed4_7f79,
1197    ]);
1198
1199    for _ in 0..100 {
1200        a = a.square();
1201        let tmp = a.to_bytes_be();
1202        let b = Fp::from_bytes_be(&tmp).unwrap();
1203
1204        assert_eq!(a, b);
1205    }
1206
1207    assert_eq!(
1208        -Fp::one(),
1209        Fp::from_bytes_be(&[
1210            26, 1, 17, 234, 57, 127, 230, 154, 75, 27, 167, 182, 67, 75, 172, 215, 100, 119, 75,
1211            132, 243, 133, 18, 191, 103, 48, 210, 160, 246, 176, 246, 36, 30, 171, 255, 254, 177,
1212            83, 255, 255, 185, 254, 255, 255, 255, 255, 170, 170
1213        ])
1214        .unwrap()
1215    );
1216
1217    assert!(bool::from(
1218        Fp::from_bytes_be(&[
1219            27, 1, 17, 234, 57, 127, 230, 154, 75, 27, 167, 182, 67, 75, 172, 215, 100, 119, 75,
1220            132, 243, 133, 18, 191, 103, 48, 210, 160, 246, 176, 246, 36, 30, 171, 255, 254, 177,
1221            83, 255, 255, 185, 254, 255, 255, 255, 255, 170, 170
1222        ])
1223        .is_none()
1224    ));
1225
1226    assert!(bool::from(Fp::from_bytes_be(&[0xff; 48]).is_none()));
1227}
1228
1229#[test]
1230fn test_sqrt() {
1231    // a = 4
1232    let a = Fp::from_raw_unchecked([
1233        0xaa27_0000_000c_fff3,
1234        0x53cc_0032_fc34_000a,
1235        0x478f_e97a_6b0a_807f,
1236        0xb1d3_7ebe_e6ba_24d7,
1237        0x8ec9_733b_bf78_ab2f,
1238        0x09d6_4551_3d83_de7e,
1239    ]);
1240
1241    assert_eq!(
1242        // sqrt(4) = -2
1243        -a.sqrt().unwrap(),
1244        // 2
1245        Fp::from_raw_unchecked([
1246            0x3213_0000_0006_554f,
1247            0xb93c_0018_d6c4_0005,
1248            0x5760_5e0d_b0dd_bb51,
1249            0x8b25_6521_ed1f_9bcb,
1250            0x6cf2_8d79_0162_2c03,
1251            0x11eb_ab9d_bb81_e28c,
1252        ])
1253    );
1254}
1255
1256#[test]
1257fn test_inversion() {
1258    let a = Fp([
1259        0x43b4_3a50_78ac_2076,
1260        0x1ce0_7630_46f8_962b,
1261        0x724a_5276_486d_735c,
1262        0x6f05_c2a6_282d_48fd,
1263        0x2095_bd5b_b4ca_9331,
1264        0x03b3_5b38_94b0_f7da,
1265    ]);
1266    let b = Fp([
1267        0x69ec_d704_0952_148f,
1268        0x985c_cc20_2219_0f55,
1269        0xe19b_ba36_a9ad_2f41,
1270        0x19bb_16c9_5219_dbd8,
1271        0x14dc_acfd_fb47_8693,
1272        0x115f_f58a_fff9_a8e1,
1273    ]);
1274
1275    assert_eq!(a.invert().unwrap(), b);
1276    assert!(bool::from(Fp::zero().invert().is_none()));
1277}
1278
1279#[test]
1280fn test_lexicographic_largest() {
1281    assert!(!bool::from(Fp::zero().lexicographically_largest()));
1282    assert!(!bool::from(Fp::one().lexicographically_largest()));
1283    assert!(!bool::from(
1284        Fp::from_raw_unchecked([
1285            0xa1fa_ffff_fffe_5557,
1286            0x995b_fff9_76a3_fffe,
1287            0x03f4_1d24_d174_ceb4,
1288            0xf654_7998_c199_5dbd,
1289            0x778a_468f_507a_6034,
1290            0x0205_5993_1f7f_8103
1291        ])
1292        .lexicographically_largest()
1293    ));
1294    assert!(bool::from(
1295        Fp::from_raw_unchecked([
1296            0x1804_0000_0001_5554,
1297            0x8550_0005_3ab0_0001,
1298            0x633c_b57c_253c_276f,
1299            0x6e22_d1ec_31eb_b502,
1300            0xd391_6126_f2d1_4ca2,
1301            0x17fb_b857_1a00_6596,
1302        ])
1303        .lexicographically_largest()
1304    ));
1305    assert!(bool::from(
1306        Fp::from_raw_unchecked([
1307            0x43f5_ffff_fffc_aaae,
1308            0x32b7_fff2_ed47_fffd,
1309            0x07e8_3a49_a2e9_9d69,
1310            0xeca8_f331_8332_bb7a,
1311            0xef14_8d1e_a0f4_c069,
1312            0x040a_b326_3eff_0206,
1313        ])
1314        .lexicographically_largest()
1315    ));
1316}
1317
1318#[cfg(feature = "zeroize")]
1319#[test]
1320fn test_zeroize() {
1321    use zeroize::Zeroize;
1322
1323    let mut a = Fp::one();
1324    a.zeroize();
1325    assert!(bool::from(a.is_zero()));
1326}
1327
1328#[test]
1329fn test_from_bytes_debug() {
1330    // let mut bytes = vec![
1331    //     220u8, 214, 26, 93, 113, 152, 62, 165, 185, 230, 195, 24, 61, 41, 116, 148, 248, 59, 10,
1332    //     81, 185, 242, 151, 83, 182, 242, 42, 201, 239, 33, 70, 221, 221, 179, 240, 87, 84, 220,
1333    //     123, 92, 72, 180, 248, 99, 100, 200, 6, 9
1334    // ];
1335    // // bytes.reserve(0);
1336    assert!(bool::from(
1337        Fp::from_bytes(&[
1338            220u8, 214, 26, 93, 113, 152, 62, 165, 185, 230, 195, 24, 61, 41, 116, 148, 248, 59,
1339            10, 81, 185, 242, 151, 83, 182, 242, 42, 201, 239, 33, 70, 221, 221, 179, 240, 87, 84,
1340            220, 123, 92, 72, 180, 248, 99, 100, 200, 6, 9
1341        ])
1342        .is_some()
1343    ));
1344}
halo2curves_axiom/bls12_381/fp.rs

halo2curves_axiom/bls12_381/
fp.rs
