bls12_381/
fp.rs

Help
1//! This module provides an implementation of the BLS12-381 base field `GF(p)`
2//! where `p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab`
3
4use core::fmt;
5use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
6use rand_core::RngCore;
7use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
8
9use crate::util::{adc, mac, sbb};
10
11// The internal representation of this type is six 64-bit unsigned
12// integers in little-endian order. `Fp` values are always in
13// Montgomery form; i.e., Scalar(a) = aR mod p, with R = 2^384.
14#[derive(Copy, Clone)]
15pub struct Fp(pub(crate) [u64; 6]);
16
17impl fmt::Debug for Fp {
18    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
19        let tmp = self.to_bytes();
20        write!(f, "0x")?;
21        for &b in tmp.iter() {
22            write!(f, "{:02x}", b)?;
23        }
24        Ok(())
25    }
26}
27
28impl Default for Fp {
29    fn default() -> Self {
30        Fp::zero()
31    }
32}
33
34#[cfg(feature = "zeroize")]
35impl zeroize::DefaultIsZeroes for Fp {}
36
37impl ConstantTimeEq for Fp {
38    fn ct_eq(&self, other: &Self) -> Choice {
39        self.0[0].ct_eq(&other.0[0])
40            & self.0[1].ct_eq(&other.0[1])
41            & self.0[2].ct_eq(&other.0[2])
42            & self.0[3].ct_eq(&other.0[3])
43            & self.0[4].ct_eq(&other.0[4])
44            & self.0[5].ct_eq(&other.0[5])
45    }
46}
47
48impl Eq for Fp {}
49impl PartialEq for Fp {
50    #[inline]
51    fn eq(&self, other: &Self) -> bool {
52        bool::from(self.ct_eq(other))
53    }
54}
55
56impl ConditionallySelectable for Fp {
57    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
58        Fp([
59            u64::conditional_select(&a.0[0], &b.0[0], choice),
60            u64::conditional_select(&a.0[1], &b.0[1], choice),
61            u64::conditional_select(&a.0[2], &b.0[2], choice),
62            u64::conditional_select(&a.0[3], &b.0[3], choice),
63            u64::conditional_select(&a.0[4], &b.0[4], choice),
64            u64::conditional_select(&a.0[5], &b.0[5], choice),
65        ])
66    }
67}
68
69/// p = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
70const MODULUS: [u64; 6] = [
71    0xb9fe_ffff_ffff_aaab,
72    0x1eab_fffe_b153_ffff,
73    0x6730_d2a0_f6b0_f624,
74    0x6477_4b84_f385_12bf,
75    0x4b1b_a7b6_434b_acd7,
76    0x1a01_11ea_397f_e69a,
77];
78
79/// INV = -(p^{-1} mod 2^64) mod 2^64
80const INV: u64 = 0x89f3_fffc_fffc_fffd;
81
82/// R = 2^384 mod p
83const R: Fp = Fp([
84    0x7609_0000_0002_fffd,
85    0xebf4_000b_c40c_0002,
86    0x5f48_9857_53c7_58ba,
87    0x77ce_5853_7052_5745,
88    0x5c07_1a97_a256_ec6d,
89    0x15f6_5ec3_fa80_e493,
90]);
91
92/// R2 = 2^(384*2) mod p
93const R2: Fp = Fp([
94    0xf4df_1f34_1c34_1746,
95    0x0a76_e6a6_09d1_04f1,
96    0x8de5_476c_4c95_b6d5,
97    0x67eb_88a9_939d_83c0,
98    0x9a79_3e85_b519_952d,
99    0x1198_8fe5_92ca_e3aa,
100]);
101
102/// R3 = 2^(384*3) mod p
103const R3: Fp = Fp([
104    0xed48_ac6b_d94c_a1e0,
105    0x315f_831e_03a7_adf8,
106    0x9a53_352a_615e_29dd,
107    0x34c0_4e5e_921e_1761,
108    0x2512_d435_6572_4728,
109    0x0aa6_3460_9175_5d4d,
110]);
111
112impl<'a> Neg for &'a Fp {
113    type Output = Fp;
114
115    #[inline]
116    fn neg(self) -> Fp {
117        self.neg()
118    }
119}
120
121impl Neg for Fp {
122    type Output = Fp;
123
124    #[inline]
125    fn neg(self) -> Fp {
126        -&self
127    }
128}
129
130impl<'a, 'b> Sub<&'b Fp> for &'a Fp {
131    type Output = Fp;
132
133    #[inline]
134    fn sub(self, rhs: &'b Fp) -> Fp {
135        self.sub(rhs)
136    }
137}
138
139impl<'a, 'b> Add<&'b Fp> for &'a Fp {
140    type Output = Fp;
141
142    #[inline]
143    fn add(self, rhs: &'b Fp) -> Fp {
144        self.add(rhs)
145    }
146}
147
148impl<'a, 'b> Mul<&'b Fp> for &'a Fp {
149    type Output = Fp;
150
151    #[inline]
152    fn mul(self, rhs: &'b Fp) -> Fp {
153        self.mul(rhs)
154    }
155}
156
157impl_binops_additive!(Fp, Fp);
158impl_binops_multiplicative!(Fp, Fp);
159
160impl Fp {
161    /// Returns zero, the additive identity.
162    #[inline]
163    pub const fn zero() -> Fp {
164        Fp([0, 0, 0, 0, 0, 0])
165    }
166
167    /// Returns one, the multiplicative identity.
168    #[inline]
169    pub const fn one() -> Fp {
170        R
171    }
172
173    pub fn is_zero(&self) -> Choice {
174        self.ct_eq(&Fp::zero())
175    }
176
177    /// Attempts to convert a big-endian byte representation of
178    /// a scalar into an `Fp`, failing if the input is not canonical.
179    pub fn from_bytes(bytes: &[u8; 48]) -> CtOption<Fp> {
180        let mut tmp = Fp([0, 0, 0, 0, 0, 0]);
181
182        tmp.0[5] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[0..8]).unwrap());
183        tmp.0[4] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[8..16]).unwrap());
184        tmp.0[3] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[16..24]).unwrap());
185        tmp.0[2] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[24..32]).unwrap());
186        tmp.0[1] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[32..40]).unwrap());
187        tmp.0[0] = u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[40..48]).unwrap());
188
189        // Try to subtract the modulus
190        let (_, borrow) = sbb(tmp.0[0], MODULUS[0], 0);
191        let (_, borrow) = sbb(tmp.0[1], MODULUS[1], borrow);
192        let (_, borrow) = sbb(tmp.0[2], MODULUS[2], borrow);
193        let (_, borrow) = sbb(tmp.0[3], MODULUS[3], borrow);
194        let (_, borrow) = sbb(tmp.0[4], MODULUS[4], borrow);
195        let (_, borrow) = sbb(tmp.0[5], MODULUS[5], borrow);
196
197        // If the element is smaller than MODULUS then the
198        // subtraction will underflow, producing a borrow value
199        // of 0xffff...ffff. Otherwise, it'll be zero.
200        let is_some = (borrow as u8) & 1;
201
202        // Convert to Montgomery form by computing
203        // (a.R^0 * R^2) / R = a.R
204        tmp *= &R2;
205
206        CtOption::new(tmp, Choice::from(is_some))
207    }
208
209    /// Converts an element of `Fp` into a byte representation in
210    /// big-endian byte order.
211    pub fn to_bytes(self) -> [u8; 48] {
212        // Turn into canonical form by computing
213        // (a.R) / R = a
214        let tmp = Fp::montgomery_reduce(
215            self.0[0], self.0[1], self.0[2], self.0[3], self.0[4], self.0[5], 0, 0, 0, 0, 0, 0,
216        );
217
218        let mut res = [0; 48];
219        res[0..8].copy_from_slice(&tmp.0[5].to_be_bytes());
220        res[8..16].copy_from_slice(&tmp.0[4].to_be_bytes());
221        res[16..24].copy_from_slice(&tmp.0[3].to_be_bytes());
222        res[24..32].copy_from_slice(&tmp.0[2].to_be_bytes());
223        res[32..40].copy_from_slice(&tmp.0[1].to_be_bytes());
224        res[40..48].copy_from_slice(&tmp.0[0].to_be_bytes());
225
226        res
227    }
228
229    pub(crate) fn random(mut rng: impl RngCore) -> Fp {
230        let mut bytes = [0u8; 96];
231        rng.fill_bytes(&mut bytes);
232
233        // Parse the random bytes as a big-endian number, to match Fp encoding order.
234        Fp::from_u768([
235            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[0..8]).unwrap()),
236            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[8..16]).unwrap()),
237            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[16..24]).unwrap()),
238            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[24..32]).unwrap()),
239            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[32..40]).unwrap()),
240            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[40..48]).unwrap()),
241            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[48..56]).unwrap()),
242            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[56..64]).unwrap()),
243            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[64..72]).unwrap()),
244            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[72..80]).unwrap()),
245            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[80..88]).unwrap()),
246            u64::from_be_bytes(<[u8; 8]>::try_from(&bytes[88..96]).unwrap()),
247        ])
248    }
249
250    /// Reduces a big-endian 64-bit limb representation of a 768-bit number.
251    fn from_u768(limbs: [u64; 12]) -> Fp {
252        // We reduce an arbitrary 768-bit number by decomposing it into two 384-bit digits
253        // with the higher bits multiplied by 2^384. Thus, we perform two reductions
254        //
255        // 1. the lower bits are multiplied by R^2, as normal
256        // 2. the upper bits are multiplied by R^2 * 2^384 = R^3
257        //
258        // and computing their sum in the field. It remains to see that arbitrary 384-bit
259        // numbers can be placed into Montgomery form safely using the reduction. The
260        // reduction works so long as the product is less than R=2^384 multiplied by
261        // the modulus. This holds because for any `c` smaller than the modulus, we have
262        // that (2^384 - 1)*c is an acceptable product for the reduction. Therefore, the
263        // reduction always works so long as `c` is in the field; in this case it is either the
264        // constant `R2` or `R3`.
265        let d1 = Fp([limbs[11], limbs[10], limbs[9], limbs[8], limbs[7], limbs[6]]);
266        let d0 = Fp([limbs[5], limbs[4], limbs[3], limbs[2], limbs[1], limbs[0]]);
267        // Convert to Montgomery form
268        d0 * R2 + d1 * R3
269    }
270
271    /// Returns whether or not this element is strictly lexicographically
272    /// larger than its negation.
273    pub fn lexicographically_largest(&self) -> Choice {
274        // This can be determined by checking to see if the element is
275        // larger than (p - 1) // 2. If we subtract by ((p - 1) // 2) + 1
276        // and there is no underflow, then the element must be larger than
277        // (p - 1) // 2.
278
279        // First, because self is in Montgomery form we need to reduce it
280        let tmp = Fp::montgomery_reduce(
281            self.0[0], self.0[1], self.0[2], self.0[3], self.0[4], self.0[5], 0, 0, 0, 0, 0, 0,
282        );
283
284        let (_, borrow) = sbb(tmp.0[0], 0xdcff_7fff_ffff_d556, 0);
285        let (_, borrow) = sbb(tmp.0[1], 0x0f55_ffff_58a9_ffff, borrow);
286        let (_, borrow) = sbb(tmp.0[2], 0xb398_6950_7b58_7b12, borrow);
287        let (_, borrow) = sbb(tmp.0[3], 0xb23b_a5c2_79c2_895f, borrow);
288        let (_, borrow) = sbb(tmp.0[4], 0x258d_d3db_21a5_d66b, borrow);
289        let (_, borrow) = sbb(tmp.0[5], 0x0d00_88f5_1cbf_f34d, borrow);
290
291        // If the element was smaller, the subtraction will underflow
292        // producing a borrow value of 0xffff...ffff, otherwise it will
293        // be zero. We create a Choice representing true if there was
294        // overflow (and so this element is not lexicographically larger
295        // than its negation) and then negate it.
296
297        !Choice::from((borrow as u8) & 1)
298    }
299
300    /// Constructs an element of `Fp` without checking that it is
301    /// canonical.
302    pub const fn from_raw_unchecked(v: [u64; 6]) -> Fp {
303        Fp(v)
304    }
305
306    /// Although this is labeled "vartime", it is only
307    /// variable time with respect to the exponent. It
308    /// is also not exposed in the public API.
309    pub fn pow_vartime(&self, by: &[u64; 6]) -> Self {
310        let mut res = Self::one();
311        for e in by.iter().rev() {
312            for i in (0..64).rev() {
313                res = res.square();
314
315                if ((*e >> i) & 1) == 1 {
316                    res *= self;
317                }
318            }
319        }
320        res
321    }
322
323    #[inline]
324    pub fn sqrt(&self) -> CtOption<Self> {
325        // We use Shank's method, as p = 3 (mod 4). This means
326        // we only need to exponentiate by (p+1)/4. This only
327        // works for elements that are actually quadratic residue,
328        // so we check that we got the correct result at the end.
329
330        let sqrt = self.pow_vartime(&[
331            0xee7f_bfff_ffff_eaab,
332            0x07aa_ffff_ac54_ffff,
333            0xd9cc_34a8_3dac_3d89,
334            0xd91d_d2e1_3ce1_44af,
335            0x92c6_e9ed_90d2_eb35,
336            0x0680_447a_8e5f_f9a6,
337        ]);
338
339        CtOption::new(sqrt, sqrt.square().ct_eq(self))
340    }
341
342    #[inline]
343    /// Computes the multiplicative inverse of this field
344    /// element, returning None in the case that this element
345    /// is zero.
346    pub fn invert(&self) -> CtOption<Self> {
347        // Exponentiate by p - 2
348        let t = self.pow_vartime(&[
349            0xb9fe_ffff_ffff_aaa9,
350            0x1eab_fffe_b153_ffff,
351            0x6730_d2a0_f6b0_f624,
352            0x6477_4b84_f385_12bf,
353            0x4b1b_a7b6_434b_acd7,
354            0x1a01_11ea_397f_e69a,
355        ]);
356
357        CtOption::new(t, !self.is_zero())
358    }
359
360    #[inline]
361    const fn subtract_p(&self) -> Fp {
362        let (r0, borrow) = sbb(self.0[0], MODULUS[0], 0);
363        let (r1, borrow) = sbb(self.0[1], MODULUS[1], borrow);
364        let (r2, borrow) = sbb(self.0[2], MODULUS[2], borrow);
365        let (r3, borrow) = sbb(self.0[3], MODULUS[3], borrow);
366        let (r4, borrow) = sbb(self.0[4], MODULUS[4], borrow);
367        let (r5, borrow) = sbb(self.0[5], MODULUS[5], borrow);
368
369        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
370        // borrow = 0x000...000. Thus, we use it as a mask!
371        let r0 = (self.0[0] & borrow) | (r0 & !borrow);
372        let r1 = (self.0[1] & borrow) | (r1 & !borrow);
373        let r2 = (self.0[2] & borrow) | (r2 & !borrow);
374        let r3 = (self.0[3] & borrow) | (r3 & !borrow);
375        let r4 = (self.0[4] & borrow) | (r4 & !borrow);
376        let r5 = (self.0[5] & borrow) | (r5 & !borrow);
377
378        Fp([r0, r1, r2, r3, r4, r5])
379    }
380
381    #[inline]
382    pub const fn add(&self, rhs: &Fp) -> Fp {
383        let (d0, carry) = adc(self.0[0], rhs.0[0], 0);
384        let (d1, carry) = adc(self.0[1], rhs.0[1], carry);
385        let (d2, carry) = adc(self.0[2], rhs.0[2], carry);
386        let (d3, carry) = adc(self.0[3], rhs.0[3], carry);
387        let (d4, carry) = adc(self.0[4], rhs.0[4], carry);
388        let (d5, _) = adc(self.0[5], rhs.0[5], carry);
389
390        // Attempt to subtract the modulus, to ensure the value
391        // is smaller than the modulus.
392        (&Fp([d0, d1, d2, d3, d4, d5])).subtract_p()
393    }
394
395    #[inline]
396    pub const fn neg(&self) -> Fp {
397        let (d0, borrow) = sbb(MODULUS[0], self.0[0], 0);
398        let (d1, borrow) = sbb(MODULUS[1], self.0[1], borrow);
399        let (d2, borrow) = sbb(MODULUS[2], self.0[2], borrow);
400        let (d3, borrow) = sbb(MODULUS[3], self.0[3], borrow);
401        let (d4, borrow) = sbb(MODULUS[4], self.0[4], borrow);
402        let (d5, _) = sbb(MODULUS[5], self.0[5], borrow);
403
404        // Let's use a mask if `self` was zero, which would mean
405        // the result of the subtraction is p.
406        let mask = (((self.0[0] | self.0[1] | self.0[2] | self.0[3] | self.0[4] | self.0[5]) == 0)
407            as u64)
408            .wrapping_sub(1);
409
410        Fp([
411            d0 & mask,
412            d1 & mask,
413            d2 & mask,
414            d3 & mask,
415            d4 & mask,
416            d5 & mask,
417        ])
418    }
419
420    #[inline]
421    pub const fn sub(&self, rhs: &Fp) -> Fp {
422        (&rhs.neg()).add(self)
423    }
424
425    /// Returns `c = a.zip(b).fold(0, |acc, (a_i, b_i)| acc + a_i * b_i)`.
426    ///
427    /// Implements Algorithm 2 from Patrick Longa's
428    /// [ePrint 2022-367](https://eprint.iacr.org/2022/367) §3.
429    #[inline]
430    pub(crate) fn sum_of_products<const T: usize>(a: [Fp; T], b: [Fp; T]) -> Fp {
431        // For a single `a x b` multiplication, operand scanning (schoolbook) takes each
432        // limb of `a` in turn, and multiplies it by all of the limbs of `b` to compute
433        // the result as a double-width intermediate representation, which is then fully
434        // reduced at the end. Here however we have pairs of multiplications (a_i, b_i),
435        // the results of which are summed.
436        //
437        // The intuition for this algorithm is two-fold:
438        // - We can interleave the operand scanning for each pair, by processing the jth
439        //   limb of each `a_i` together. As these have the same offset within the overall
440        //   operand scanning flow, their results can be summed directly.
441        // - We can interleave the multiplication and reduction steps, resulting in a
442        //   single bitshift by the limb size after each iteration. This means we only
443        //   need to store a single extra limb overall, instead of keeping around all the
444        //   intermediate results and eventually having twice as many limbs.
445
446        // Algorithm 2, line 2
447        let (u0, u1, u2, u3, u4, u5) =
448            (0..6).fold((0, 0, 0, 0, 0, 0), |(u0, u1, u2, u3, u4, u5), j| {
449                // Algorithm 2, line 3
450                // For each pair in the overall sum of products:
451                let (t0, t1, t2, t3, t4, t5, t6) = (0..T).fold(
452                    (u0, u1, u2, u3, u4, u5, 0),
453                    |(t0, t1, t2, t3, t4, t5, t6), i| {
454                        // Compute digit_j x row and accumulate into `u`.
455                        let (t0, carry) = mac(t0, a[i].0[j], b[i].0[0], 0);
456                        let (t1, carry) = mac(t1, a[i].0[j], b[i].0[1], carry);
457                        let (t2, carry) = mac(t2, a[i].0[j], b[i].0[2], carry);
458                        let (t3, carry) = mac(t3, a[i].0[j], b[i].0[3], carry);
459                        let (t4, carry) = mac(t4, a[i].0[j], b[i].0[4], carry);
460                        let (t5, carry) = mac(t5, a[i].0[j], b[i].0[5], carry);
461                        let (t6, _) = adc(t6, 0, carry);
462
463                        (t0, t1, t2, t3, t4, t5, t6)
464                    },
465                );
466
467                // Algorithm 2, lines 4-5
468                // This is a single step of the usual Montgomery reduction process.
469                let k = t0.wrapping_mul(INV);
470                let (_, carry) = mac(t0, k, MODULUS[0], 0);
471                let (r1, carry) = mac(t1, k, MODULUS[1], carry);
472                let (r2, carry) = mac(t2, k, MODULUS[2], carry);
473                let (r3, carry) = mac(t3, k, MODULUS[3], carry);
474                let (r4, carry) = mac(t4, k, MODULUS[4], carry);
475                let (r5, carry) = mac(t5, k, MODULUS[5], carry);
476                let (r6, _) = adc(t6, 0, carry);
477
478                (r1, r2, r3, r4, r5, r6)
479            });
480
481        // Because we represent F_p elements in non-redundant form, we need a final
482        // conditional subtraction to ensure the output is in range.
483        (&Fp([u0, u1, u2, u3, u4, u5])).subtract_p()
484    }
485
486    #[inline(always)]
487    pub(crate) const fn montgomery_reduce(
488        t0: u64,
489        t1: u64,
490        t2: u64,
491        t3: u64,
492        t4: u64,
493        t5: u64,
494        t6: u64,
495        t7: u64,
496        t8: u64,
497        t9: u64,
498        t10: u64,
499        t11: u64,
500    ) -> Self {
501        // The Montgomery reduction here is based on Algorithm 14.32 in
502        // Handbook of Applied Cryptography
503        // <http://cacr.uwaterloo.ca/hac/about/chap14.pdf>.
504
505        let k = t0.wrapping_mul(INV);
506        let (_, carry) = mac(t0, k, MODULUS[0], 0);
507        let (r1, carry) = mac(t1, k, MODULUS[1], carry);
508        let (r2, carry) = mac(t2, k, MODULUS[2], carry);
509        let (r3, carry) = mac(t3, k, MODULUS[3], carry);
510        let (r4, carry) = mac(t4, k, MODULUS[4], carry);
511        let (r5, carry) = mac(t5, k, MODULUS[5], carry);
512        let (r6, r7) = adc(t6, 0, carry);
513
514        let k = r1.wrapping_mul(INV);
515        let (_, carry) = mac(r1, k, MODULUS[0], 0);
516        let (r2, carry) = mac(r2, k, MODULUS[1], carry);
517        let (r3, carry) = mac(r3, k, MODULUS[2], carry);
518        let (r4, carry) = mac(r4, k, MODULUS[3], carry);
519        let (r5, carry) = mac(r5, k, MODULUS[4], carry);
520        let (r6, carry) = mac(r6, k, MODULUS[5], carry);
521        let (r7, r8) = adc(t7, r7, carry);
522
523        let k = r2.wrapping_mul(INV);
524        let (_, carry) = mac(r2, k, MODULUS[0], 0);
525        let (r3, carry) = mac(r3, k, MODULUS[1], carry);
526        let (r4, carry) = mac(r4, k, MODULUS[2], carry);
527        let (r5, carry) = mac(r5, k, MODULUS[3], carry);
528        let (r6, carry) = mac(r6, k, MODULUS[4], carry);
529        let (r7, carry) = mac(r7, k, MODULUS[5], carry);
530        let (r8, r9) = adc(t8, r8, carry);
531
532        let k = r3.wrapping_mul(INV);
533        let (_, carry) = mac(r3, k, MODULUS[0], 0);
534        let (r4, carry) = mac(r4, k, MODULUS[1], carry);
535        let (r5, carry) = mac(r5, k, MODULUS[2], carry);
536        let (r6, carry) = mac(r6, k, MODULUS[3], carry);
537        let (r7, carry) = mac(r7, k, MODULUS[4], carry);
538        let (r8, carry) = mac(r8, k, MODULUS[5], carry);
539        let (r9, r10) = adc(t9, r9, carry);
540
541        let k = r4.wrapping_mul(INV);
542        let (_, carry) = mac(r4, k, MODULUS[0], 0);
543        let (r5, carry) = mac(r5, k, MODULUS[1], carry);
544        let (r6, carry) = mac(r6, k, MODULUS[2], carry);
545        let (r7, carry) = mac(r7, k, MODULUS[3], carry);
546        let (r8, carry) = mac(r8, k, MODULUS[4], carry);
547        let (r9, carry) = mac(r9, k, MODULUS[5], carry);
548        let (r10, r11) = adc(t10, r10, carry);
549
550        let k = r5.wrapping_mul(INV);
551        let (_, carry) = mac(r5, k, MODULUS[0], 0);
552        let (r6, carry) = mac(r6, k, MODULUS[1], carry);
553        let (r7, carry) = mac(r7, k, MODULUS[2], carry);
554        let (r8, carry) = mac(r8, k, MODULUS[3], carry);
555        let (r9, carry) = mac(r9, k, MODULUS[4], carry);
556        let (r10, carry) = mac(r10, k, MODULUS[5], carry);
557        let (r11, _) = adc(t11, r11, carry);
558
559        // Attempt to subtract the modulus, to ensure the value
560        // is smaller than the modulus.
561        (&Fp([r6, r7, r8, r9, r10, r11])).subtract_p()
562    }
563
564    #[inline]
565    pub const fn mul(&self, rhs: &Fp) -> Fp {
566        let (t0, carry) = mac(0, self.0[0], rhs.0[0], 0);
567        let (t1, carry) = mac(0, self.0[0], rhs.0[1], carry);
568        let (t2, carry) = mac(0, self.0[0], rhs.0[2], carry);
569        let (t3, carry) = mac(0, self.0[0], rhs.0[3], carry);
570        let (t4, carry) = mac(0, self.0[0], rhs.0[4], carry);
571        let (t5, t6) = mac(0, self.0[0], rhs.0[5], carry);
572
573        let (t1, carry) = mac(t1, self.0[1], rhs.0[0], 0);
574        let (t2, carry) = mac(t2, self.0[1], rhs.0[1], carry);
575        let (t3, carry) = mac(t3, self.0[1], rhs.0[2], carry);
576        let (t4, carry) = mac(t4, self.0[1], rhs.0[3], carry);
577        let (t5, carry) = mac(t5, self.0[1], rhs.0[4], carry);
578        let (t6, t7) = mac(t6, self.0[1], rhs.0[5], carry);
579
580        let (t2, carry) = mac(t2, self.0[2], rhs.0[0], 0);
581        let (t3, carry) = mac(t3, self.0[2], rhs.0[1], carry);
582        let (t4, carry) = mac(t4, self.0[2], rhs.0[2], carry);
583        let (t5, carry) = mac(t5, self.0[2], rhs.0[3], carry);
584        let (t6, carry) = mac(t6, self.0[2], rhs.0[4], carry);
585        let (t7, t8) = mac(t7, self.0[2], rhs.0[5], carry);
586
587        let (t3, carry) = mac(t3, self.0[3], rhs.0[0], 0);
588        let (t4, carry) = mac(t4, self.0[3], rhs.0[1], carry);
589        let (t5, carry) = mac(t5, self.0[3], rhs.0[2], carry);
590        let (t6, carry) = mac(t6, self.0[3], rhs.0[3], carry);
591        let (t7, carry) = mac(t7, self.0[3], rhs.0[4], carry);
592        let (t8, t9) = mac(t8, self.0[3], rhs.0[5], carry);
593
594        let (t4, carry) = mac(t4, self.0[4], rhs.0[0], 0);
595        let (t5, carry) = mac(t5, self.0[4], rhs.0[1], carry);
596        let (t6, carry) = mac(t6, self.0[4], rhs.0[2], carry);
597        let (t7, carry) = mac(t7, self.0[4], rhs.0[3], carry);
598        let (t8, carry) = mac(t8, self.0[4], rhs.0[4], carry);
599        let (t9, t10) = mac(t9, self.0[4], rhs.0[5], carry);
600
601        let (t5, carry) = mac(t5, self.0[5], rhs.0[0], 0);
602        let (t6, carry) = mac(t6, self.0[5], rhs.0[1], carry);
603        let (t7, carry) = mac(t7, self.0[5], rhs.0[2], carry);
604        let (t8, carry) = mac(t8, self.0[5], rhs.0[3], carry);
605        let (t9, carry) = mac(t9, self.0[5], rhs.0[4], carry);
606        let (t10, t11) = mac(t10, self.0[5], rhs.0[5], carry);
607
608        Self::montgomery_reduce(t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11)
609    }
610
611    /// Squares this element.
612    #[inline]
613    pub const fn square(&self) -> Self {
614        let (t1, carry) = mac(0, self.0[0], self.0[1], 0);
615        let (t2, carry) = mac(0, self.0[0], self.0[2], carry);
616        let (t3, carry) = mac(0, self.0[0], self.0[3], carry);
617        let (t4, carry) = mac(0, self.0[0], self.0[4], carry);
618        let (t5, t6) = mac(0, self.0[0], self.0[5], carry);
619
620        let (t3, carry) = mac(t3, self.0[1], self.0[2], 0);
621        let (t4, carry) = mac(t4, self.0[1], self.0[3], carry);
622        let (t5, carry) = mac(t5, self.0[1], self.0[4], carry);
623        let (t6, t7) = mac(t6, self.0[1], self.0[5], carry);
624
625        let (t5, carry) = mac(t5, self.0[2], self.0[3], 0);
626        let (t6, carry) = mac(t6, self.0[2], self.0[4], carry);
627        let (t7, t8) = mac(t7, self.0[2], self.0[5], carry);
628
629        let (t7, carry) = mac(t7, self.0[3], self.0[4], 0);
630        let (t8, t9) = mac(t8, self.0[3], self.0[5], carry);
631
632        let (t9, t10) = mac(t9, self.0[4], self.0[5], 0);
633
634        let t11 = t10 >> 63;
635        let t10 = (t10 << 1) | (t9 >> 63);
636        let t9 = (t9 << 1) | (t8 >> 63);
637        let t8 = (t8 << 1) | (t7 >> 63);
638        let t7 = (t7 << 1) | (t6 >> 63);
639        let t6 = (t6 << 1) | (t5 >> 63);
640        let t5 = (t5 << 1) | (t4 >> 63);
641        let t4 = (t4 << 1) | (t3 >> 63);
642        let t3 = (t3 << 1) | (t2 >> 63);
643        let t2 = (t2 << 1) | (t1 >> 63);
644        let t1 = t1 << 1;
645
646        let (t0, carry) = mac(0, self.0[0], self.0[0], 0);
647        let (t1, carry) = adc(t1, 0, carry);
648        let (t2, carry) = mac(t2, self.0[1], self.0[1], carry);
649        let (t3, carry) = adc(t3, 0, carry);
650        let (t4, carry) = mac(t4, self.0[2], self.0[2], carry);
651        let (t5, carry) = adc(t5, 0, carry);
652        let (t6, carry) = mac(t6, self.0[3], self.0[3], carry);
653        let (t7, carry) = adc(t7, 0, carry);
654        let (t8, carry) = mac(t8, self.0[4], self.0[4], carry);
655        let (t9, carry) = adc(t9, 0, carry);
656        let (t10, carry) = mac(t10, self.0[5], self.0[5], carry);
657        let (t11, _) = adc(t11, 0, carry);
658
659        Self::montgomery_reduce(t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11)
660    }
661}
662
663#[test]
664fn test_conditional_selection() {
665    let a = Fp([1, 2, 3, 4, 5, 6]);
666    let b = Fp([7, 8, 9, 10, 11, 12]);
667
668    assert_eq!(
669        ConditionallySelectable::conditional_select(&a, &b, Choice::from(0u8)),
670        a
671    );
672    assert_eq!(
673        ConditionallySelectable::conditional_select(&a, &b, Choice::from(1u8)),
674        b
675    );
676}
677
678#[test]
679fn test_equality() {
680    fn is_equal(a: &Fp, b: &Fp) -> bool {
681        let eq = a == b;
682        let ct_eq = a.ct_eq(&b);
683
684        assert_eq!(eq, bool::from(ct_eq));
685
686        eq
687    }
688
689    assert!(is_equal(&Fp([1, 2, 3, 4, 5, 6]), &Fp([1, 2, 3, 4, 5, 6])));
690
691    assert!(!is_equal(&Fp([7, 2, 3, 4, 5, 6]), &Fp([1, 2, 3, 4, 5, 6])));
692    assert!(!is_equal(&Fp([1, 7, 3, 4, 5, 6]), &Fp([1, 2, 3, 4, 5, 6])));
693    assert!(!is_equal(&Fp([1, 2, 7, 4, 5, 6]), &Fp([1, 2, 3, 4, 5, 6])));
694    assert!(!is_equal(&Fp([1, 2, 3, 7, 5, 6]), &Fp([1, 2, 3, 4, 5, 6])));
695    assert!(!is_equal(&Fp([1, 2, 3, 4, 7, 6]), &Fp([1, 2, 3, 4, 5, 6])));
696    assert!(!is_equal(&Fp([1, 2, 3, 4, 5, 7]), &Fp([1, 2, 3, 4, 5, 6])));
697}
698
699#[test]
700fn test_squaring() {
701    let a = Fp([
702        0xd215_d276_8e83_191b,
703        0x5085_d80f_8fb2_8261,
704        0xce9a_032d_df39_3a56,
705        0x3e9c_4fff_2ca0_c4bb,
706        0x6436_b6f7_f4d9_5dfb,
707        0x1060_6628_ad4a_4d90,
708    ]);
709    let b = Fp([
710        0x33d9_c42a_3cb3_e235,
711        0xdad1_1a09_4c4c_d455,
712        0xa2f1_44bd_729a_aeba,
713        0xd415_0932_be9f_feac,
714        0xe27b_c7c4_7d44_ee50,
715        0x14b6_a78d_3ec7_a560,
716    ]);
717
718    assert_eq!(a.square(), b);
719}
720
721#[test]
722fn test_multiplication() {
723    let a = Fp([
724        0x0397_a383_2017_0cd4,
725        0x734c_1b2c_9e76_1d30,
726        0x5ed2_55ad_9a48_beb5,
727        0x095a_3c6b_22a7_fcfc,
728        0x2294_ce75_d4e2_6a27,
729        0x1333_8bd8_7001_1ebb,
730    ]);
731    let b = Fp([
732        0xb9c3_c7c5_b119_6af7,
733        0x2580_e208_6ce3_35c1,
734        0xf49a_ed3d_8a57_ef42,
735        0x41f2_81e4_9846_e878,
736        0xe076_2346_c384_52ce,
737        0x0652_e893_26e5_7dc0,
738    ]);
739    let c = Fp([
740        0xf96e_f3d7_11ab_5355,
741        0xe8d4_59ea_00f1_48dd,
742        0x53f7_354a_5f00_fa78,
743        0x9e34_a4f3_125c_5f83,
744        0x3fbe_0c47_ca74_c19e,
745        0x01b0_6a8b_bd4a_dfe4,
746    ]);
747
748    assert_eq!(a * b, c);
749}
750
751#[test]
752fn test_addition() {
753    let a = Fp([
754        0x5360_bb59_7867_8032,
755        0x7dd2_75ae_799e_128e,
756        0x5c5b_5071_ce4f_4dcf,
757        0xcdb2_1f93_078d_bb3e,
758        0xc323_65c5_e73f_474a,
759        0x115a_2a54_89ba_be5b,
760    ]);
761    let b = Fp([
762        0x9fd2_8773_3d23_dda0,
763        0xb16b_f2af_738b_3554,
764        0x3e57_a75b_d3cc_6d1d,
765        0x900b_c0bd_627f_d6d6,
766        0xd319_a080_efb2_45fe,
767        0x15fd_caa4_e4bb_2091,
768    ]);
769    let c = Fp([
770        0x3934_42cc_b58b_b327,
771        0x1092_685f_3bd5_47e3,
772        0x3382_252c_ab6a_c4c9,
773        0xf946_94cb_7688_7f55,
774        0x4b21_5e90_93a5_e071,
775        0x0d56_e30f_34f5_f853,
776    ]);
777
778    assert_eq!(a + b, c);
779}
780
781#[test]
782fn test_subtraction() {
783    let a = Fp([
784        0x5360_bb59_7867_8032,
785        0x7dd2_75ae_799e_128e,
786        0x5c5b_5071_ce4f_4dcf,
787        0xcdb2_1f93_078d_bb3e,
788        0xc323_65c5_e73f_474a,
789        0x115a_2a54_89ba_be5b,
790    ]);
791    let b = Fp([
792        0x9fd2_8773_3d23_dda0,
793        0xb16b_f2af_738b_3554,
794        0x3e57_a75b_d3cc_6d1d,
795        0x900b_c0bd_627f_d6d6,
796        0xd319_a080_efb2_45fe,
797        0x15fd_caa4_e4bb_2091,
798    ]);
799    let c = Fp([
800        0x6d8d_33e6_3b43_4d3d,
801        0xeb12_82fd_b766_dd39,
802        0x8534_7bb6_f133_d6d5,
803        0xa21d_aa5a_9892_f727,
804        0x3b25_6cfb_3ad8_ae23,
805        0x155d_7199_de7f_8464,
806    ]);
807
808    assert_eq!(a - b, c);
809}
810
811#[test]
812fn test_negation() {
813    let a = Fp([
814        0x5360_bb59_7867_8032,
815        0x7dd2_75ae_799e_128e,
816        0x5c5b_5071_ce4f_4dcf,
817        0xcdb2_1f93_078d_bb3e,
818        0xc323_65c5_e73f_474a,
819        0x115a_2a54_89ba_be5b,
820    ]);
821    let b = Fp([
822        0x669e_44a6_8798_2a79,
823        0xa0d9_8a50_37b5_ed71,
824        0x0ad5_822f_2861_a854,
825        0x96c5_2bf1_ebf7_5781,
826        0x87f8_41f0_5c0c_658c,
827        0x08a6_e795_afc5_283e,
828    ]);
829
830    assert_eq!(-a, b);
831}
832
833#[test]
834fn test_debug() {
835    assert_eq!(
836        format!(
837            "{:?}",
838            Fp([
839                0x5360_bb59_7867_8032,
840                0x7dd2_75ae_799e_128e,
841                0x5c5b_5071_ce4f_4dcf,
842                0xcdb2_1f93_078d_bb3e,
843                0xc323_65c5_e73f_474a,
844                0x115a_2a54_89ba_be5b,
845            ])
846        ),
847        "0x104bf052ad3bc99bcb176c24a06a6c3aad4eaf2308fc4d282e106c84a757d061052630515305e59bdddf8111bfdeb704"
848    );
849}
850
851#[test]
852fn test_from_bytes() {
853    let mut a = Fp([
854        0xdc90_6d9b_e3f9_5dc8,
855        0x8755_caf7_4596_91a1,
856        0xcff1_a7f4_e958_3ab3,
857        0x9b43_821f_849e_2284,
858        0xf575_54f3_a297_4f3f,
859        0x085d_bea8_4ed4_7f79,
860    ]);
861
862    for _ in 0..100 {
863        a = a.square();
864        let tmp = a.to_bytes();
865        let b = Fp::from_bytes(&tmp).unwrap();
866
867        assert_eq!(a, b);
868    }
869
870    assert_eq!(
871        -Fp::one(),
872        Fp::from_bytes(&[
873            26, 1, 17, 234, 57, 127, 230, 154, 75, 27, 167, 182, 67, 75, 172, 215, 100, 119, 75,
874            132, 243, 133, 18, 191, 103, 48, 210, 160, 246, 176, 246, 36, 30, 171, 255, 254, 177,
875            83, 255, 255, 185, 254, 255, 255, 255, 255, 170, 170
876        ])
877        .unwrap()
878    );
879
880    assert!(bool::from(
881        Fp::from_bytes(&[
882            27, 1, 17, 234, 57, 127, 230, 154, 75, 27, 167, 182, 67, 75, 172, 215, 100, 119, 75,
883            132, 243, 133, 18, 191, 103, 48, 210, 160, 246, 176, 246, 36, 30, 171, 255, 254, 177,
884            83, 255, 255, 185, 254, 255, 255, 255, 255, 170, 170
885        ])
886        .is_none()
887    ));
888
889    assert!(bool::from(Fp::from_bytes(&[0xff; 48]).is_none()));
890}
891
892#[test]
893fn test_sqrt() {
894    // a = 4
895    let a = Fp::from_raw_unchecked([
896        0xaa27_0000_000c_fff3,
897        0x53cc_0032_fc34_000a,
898        0x478f_e97a_6b0a_807f,
899        0xb1d3_7ebe_e6ba_24d7,
900        0x8ec9_733b_bf78_ab2f,
901        0x09d6_4551_3d83_de7e,
902    ]);
903
904    assert_eq!(
905        // sqrt(4) = -2
906        -a.sqrt().unwrap(),
907        // 2
908        Fp::from_raw_unchecked([
909            0x3213_0000_0006_554f,
910            0xb93c_0018_d6c4_0005,
911            0x5760_5e0d_b0dd_bb51,
912            0x8b25_6521_ed1f_9bcb,
913            0x6cf2_8d79_0162_2c03,
914            0x11eb_ab9d_bb81_e28c,
915        ])
916    );
917}
918
919#[test]
920fn test_inversion() {
921    let a = Fp([
922        0x43b4_3a50_78ac_2076,
923        0x1ce0_7630_46f8_962b,
924        0x724a_5276_486d_735c,
925        0x6f05_c2a6_282d_48fd,
926        0x2095_bd5b_b4ca_9331,
927        0x03b3_5b38_94b0_f7da,
928    ]);
929    let b = Fp([
930        0x69ec_d704_0952_148f,
931        0x985c_cc20_2219_0f55,
932        0xe19b_ba36_a9ad_2f41,
933        0x19bb_16c9_5219_dbd8,
934        0x14dc_acfd_fb47_8693,
935        0x115f_f58a_fff9_a8e1,
936    ]);
937
938    assert_eq!(a.invert().unwrap(), b);
939    assert!(bool::from(Fp::zero().invert().is_none()));
940}
941
942#[test]
943fn test_lexicographic_largest() {
944    assert!(!bool::from(Fp::zero().lexicographically_largest()));
945    assert!(!bool::from(Fp::one().lexicographically_largest()));
946    assert!(!bool::from(
947        Fp::from_raw_unchecked([
948            0xa1fa_ffff_fffe_5557,
949            0x995b_fff9_76a3_fffe,
950            0x03f4_1d24_d174_ceb4,
951            0xf654_7998_c199_5dbd,
952            0x778a_468f_507a_6034,
953            0x0205_5993_1f7f_8103
954        ])
955        .lexicographically_largest()
956    ));
957    assert!(bool::from(
958        Fp::from_raw_unchecked([
959            0x1804_0000_0001_5554,
960            0x8550_0005_3ab0_0001,
961            0x633c_b57c_253c_276f,
962            0x6e22_d1ec_31eb_b502,
963            0xd391_6126_f2d1_4ca2,
964            0x17fb_b857_1a00_6596,
965        ])
966        .lexicographically_largest()
967    ));
968    assert!(bool::from(
969        Fp::from_raw_unchecked([
970            0x43f5_ffff_fffc_aaae,
971            0x32b7_fff2_ed47_fffd,
972            0x07e8_3a49_a2e9_9d69,
973            0xeca8_f331_8332_bb7a,
974            0xef14_8d1e_a0f4_c069,
975            0x040a_b326_3eff_0206,
976        ])
977        .lexicographically_largest()
978    ));
979}
980
981#[cfg(feature = "zeroize")]
982#[test]
983fn test_zeroize() {
984    use zeroize::Zeroize;
985
986    let mut a = Fp::one();
987    a.zeroize();
988    assert!(bool::from(a.is_zero()));
989}
bls12_381/fp.rs

bls12_381/
fp.rs
