p521/arithmetic/
field.rs

1//! Field arithmetic modulo p = 2^{521} − 1
2//!
3//! Arithmetic implementations have been synthesized using fiat-crypto.
4//!
5//! # License
6//!
7//! Copyright (c) 2015-2020 the fiat-crypto authors
8//!
9//! fiat-crypto is distributed under the terms of the MIT License, the
10//! Apache License (Version 2.0), and the BSD 1-Clause License;
11//! users may pick which license to apply.
12
13use crate::{FieldBytes, NistP521, Uint};
14use core::{
15    cmp::Ordering,
16    fmt::{self, Debug},
17    iter::{Product, Sum},
18    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
19};
20use elliptic_curve::{
21    Error, Generate,
22    array::Array,
23    bigint::{self, Limb, Odd, Word, cpubits, modular::Retrieve},
24    ff::{self, Field, PrimeField},
25    field::bytes_to_uint,
26    ops::{BatchInvert, Invert},
27    rand_core::TryRng,
28    subtle::{Choice, ConditionallySelectable, ConstantTimeEq, ConstantTimeLess, CtOption},
29    zeroize::DefaultIsZeroes,
30};
31use primefield::{FieldExt, PrimeFieldExt};
32
33// TODO(tarcieri): remove `allow(dead_code)` when we can use `const _` to silence warnings
34cpubits! {
35    32 => {
36        #[allow(dead_code, missing_debug_implementations, trivial_numeric_casts)]
37        #[allow(
38            clippy::cast_possible_truncation,
39            clippy::cast_possible_wrap,
40            clippy::cast_sign_loss,
41            clippy::needless_lifetimes,
42            clippy::unnecessary_cast
43        )]
44        #[rustfmt::skip]
45        #[path = "field/p521_32.rs"]
46        mod field_impl;
47    }
48    64 => {
49        #[allow(dead_code, missing_debug_implementations, trivial_numeric_casts)]
50        #[allow(
51            clippy::cast_possible_truncation,
52            clippy::cast_possible_wrap,
53            clippy::cast_sign_loss,
54            clippy::needless_lifetimes,
55            clippy::unnecessary_cast
56        )]
57        #[rustfmt::skip]
58        #[path = "field/p521_64.rs"]
59        mod field_impl;
60    }
61}
62
63mod loose;
64
65use self::field_impl::*;
66pub(crate) use self::loose::LooseFieldElement;
67
68const MODULUS_HEX: &str = {
69    cpubits! {
70        32 => {
71            "000001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
72        }
73        64 => {
74            "00000000000001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
75        }
76    }
77};
78
79/// Field modulus: p = 2^{521} − 1
80pub(crate) const MODULUS: Uint = Uint::from_be_hex(MODULUS_HEX);
81
82/// Element of the secp521r1 base field used for curve coordinates.
83#[derive(Clone, Copy)]
84pub struct FieldElement(pub(crate) fiat_p521_tight_field_element);
85
86impl FieldElement {
87    /// Zero element.
88    pub const ZERO: Self = Self::from_u64(0);
89
90    /// Multiplicative identity.
91    pub const ONE: Self = Self::from_u64(1);
92
93    cpubits! {
94        32 => { const LIMBS: usize = 19; }
95        64 => { const LIMBS: usize = 9; }
96    }
97
98    /// Create a [`FieldElement`] from a canonical big-endian representation.
99    pub fn from_bytes(repr: &FieldBytes) -> CtOption<Self> {
100        Self::from_uint(bytes_to_uint::<NistP521>(repr))
101    }
102
103    /// Decode [`FieldElement`] from a big endian byte slice.
104    pub fn from_slice(slice: &[u8]) -> elliptic_curve::Result<Self> {
105        let field_bytes = FieldBytes::try_from(slice).map_err(|_| Error)?;
106        Self::from_bytes(&field_bytes).into_option().ok_or(Error)
107    }
108
109    /// Decode [`FieldElement`] from [`Uint`].
110    pub fn from_uint(uint: Uint) -> CtOption<Self> {
111        let is_some = uint.ct_lt(&MODULUS);
112        CtOption::new(Self::from_uint_unchecked(uint), is_some)
113    }
114
115    /// Parse a [`FieldElement`] from big endian hex-encoded bytes.
116    ///
117    /// This method is primarily intended for defining internal constants.
118    ///
119    /// # Panics
120    /// - if the input in hex is not the correct length
121    /// - if the given value when decoded from hex overflows the modulus
122    pub(crate) const fn from_hex(hex: &str) -> Self {
123        assert!(
124            hex.len() == 521usize.div_ceil(8) * 2,
125            "hex is the wrong length (expected 132 hex chars)"
126        );
127
128        // Build a hex string of the expected size, regardless of the size of `Uint`
129        let mut hex_bytes = [b'0'; { Uint::BITS as usize / 4 }];
130
131        let offset = hex_bytes.len() - hex.len();
132        let mut i = 0;
133        while i < hex.len() {
134            hex_bytes[i + offset] = hex.as_bytes()[i];
135            i += 1;
136        }
137
138        let uint = match core::str::from_utf8(&hex_bytes) {
139            Ok(padded_hex) => Uint::from_be_hex(padded_hex),
140            Err(_) => panic!("invalid hex string"),
141        };
142
143        assert!(matches!(uint.cmp_vartime(&MODULUS), Ordering::Less));
144        Self::from_uint_unchecked(uint)
145    }
146
147    /// Convert a `u64` into a [`FieldElement`].
148    pub const fn from_u64(w: u64) -> Self {
149        Self::from_uint_unchecked(Uint::from_u64(w))
150    }
151
152    /// Decode [`FieldElement`] from [`Uint`].
153    ///
154    /// Does *not* perform a check that the field element does not overflow the order.
155    ///
156    /// Used incorrectly this can lead to invalid results!
157    pub(crate) const fn from_uint_unchecked(w: Uint) -> Self {
158        // Converts the saturated representation used by `Uint` into a 66-byte array with a
159        // little-endian byte ordering.
160        // TODO(tarcieri): use `FieldBytesEncoding::encode_field_bytes` when `const impl` is stable
161        let le_bytes_wide = w.to_le_bytes();
162
163        let mut le_bytes = [0u8; 66];
164        let mut i = 0;
165
166        // Extract the first 66-bytes of the 72-byte (576-bit) little endian serialized value
167        while i < le_bytes.len() {
168            le_bytes[i] = le_bytes_wide.as_slice()[i];
169            i += 1;
170        }
171
172        // Decode the little endian serialization into the unsaturated big integer form used by
173        // the fiat-crypto synthesized code.
174        let mut out = fiat_p521_tight_field_element([0; Self::LIMBS]);
175        fiat_p521_from_bytes(&mut out, &le_bytes);
176        Self(out)
177    }
178
179    /// Returns the big-endian encoding of this [`FieldElement`].
180    pub const fn to_bytes(self) -> FieldBytes {
181        const BYTES: usize = 66;
182
183        let mut ret = [0u8; BYTES];
184        fiat_p521_to_bytes(&mut ret, &self.0);
185
186        // TODO(tarcieri): use `reverse` when const-stable (MSRV 1.90)
187        // ret.reverse();
188        let mut i = 0;
189        while i < (BYTES / 2) {
190            let j = BYTES - i - 1;
191            let tmp = ret[i];
192            ret[i] = ret[j];
193            ret[j] = tmp;
194            i += 1;
195        }
196
197        Array(ret)
198    }
199
200    /// Determine if this [`FieldElement`] is odd in the SEC1 sense: `self mod 2 == 1`.
201    ///
202    /// # Returns
203    ///
204    /// If odd, return `Choice(1)`.  Otherwise, return `Choice(0)`.
205    pub fn is_odd(&self) -> Choice {
206        Choice::from((self.0[0] & 1) as u8)
207    }
208
209    /// Determine if this [`FieldElement`] is even in the SEC1 sense: `self mod 2 == 0`.
210    ///
211    /// # Returns
212    ///
213    /// If even, return `Choice(1)`.  Otherwise, return `Choice(0)`.
214    pub fn is_even(&self) -> Choice {
215        !self.is_odd()
216    }
217
218    /// Determine if this [`FieldElement`] is zero.
219    ///
220    /// # Returns
221    ///
222    /// If zero, return `Choice(1)`.  Otherwise, return `Choice(0)`.
223    pub fn is_zero(&self) -> Choice {
224        self.ct_eq(&Self::ZERO)
225    }
226
227    /// Add elements.
228    #[inline]
229    pub const fn add_loose(&self, rhs: &Self) -> LooseFieldElement {
230        let mut out = fiat_p521_loose_field_element([0; Self::LIMBS]);
231        fiat_p521_add(&mut out, &self.0, &rhs.0);
232        LooseFieldElement(out)
233    }
234
235    /// Double element (add it to itself).
236    #[inline]
237    #[must_use]
238    pub const fn double_loose(&self) -> LooseFieldElement {
239        self.add_loose(self)
240    }
241
242    /// Subtract elements, returning a loose field element.
243    #[inline]
244    pub const fn sub_loose(&self, rhs: &Self) -> LooseFieldElement {
245        let mut out = fiat_p521_loose_field_element([0; Self::LIMBS]);
246        fiat_p521_sub(&mut out, &self.0, &rhs.0);
247        LooseFieldElement(out)
248    }
249
250    /// Negate element, returning a loose field element.
251    #[inline]
252    pub const fn neg_loose(&self) -> LooseFieldElement {
253        let mut out = fiat_p521_loose_field_element([0; Self::LIMBS]);
254        fiat_p521_opp(&mut out, &self.0);
255        LooseFieldElement(out)
256    }
257
258    /// Add two field elements.
259    #[inline]
260    pub const fn add(&self, rhs: &Self) -> Self {
261        let mut out = fiat_p521_tight_field_element([0; Self::LIMBS]);
262        fiat_p521_carry_add(&mut out, &self.0, &rhs.0);
263        Self(out)
264    }
265
266    /// Subtract field elements.
267    #[inline]
268    pub const fn sub(&self, rhs: &Self) -> Self {
269        let mut out = fiat_p521_tight_field_element([0; Self::LIMBS]);
270        fiat_p521_carry_sub(&mut out, &self.0, &rhs.0);
271        Self(out)
272    }
273
274    /// Negate element.
275    #[inline]
276    pub const fn neg(&self) -> Self {
277        let mut out = fiat_p521_tight_field_element([0; Self::LIMBS]);
278        fiat_p521_carry_opp(&mut out, &self.0);
279        Self(out)
280    }
281
282    /// Double element (add it to itself).
283    #[inline]
284    #[must_use]
285    pub const fn double(&self) -> Self {
286        self.add(self)
287    }
288
289    /// Multiply elements.
290    #[inline]
291    pub const fn multiply(&self, rhs: &Self) -> Self {
292        self.relax().multiply(&rhs.relax())
293    }
294
295    /// Square element.
296    #[inline]
297    pub const fn square(&self) -> Self {
298        self.relax().square()
299    }
300
301    /// Returns self^(2^n) mod p
302    const fn sqn(&self, n: usize) -> Self {
303        self.sqn_vartime(n)
304    }
305
306    /// Returns `self^exp`, where `exp` is a little-endian integer exponent.
307    ///
308    /// **This operation is variable time with respect to the exponent `exp`.**
309    ///
310    /// If the exponent is fixed, this operation is constant time.
311    pub const fn pow_vartime<const RHS_LIMBS: usize>(&self, exp: &bigint::Uint<RHS_LIMBS>) -> Self {
312        let mut res = Self::ONE;
313        let mut i = RHS_LIMBS;
314
315        while i > 0 {
316            i -= 1;
317
318            let mut j = Limb::BITS;
319            while j > 0 {
320                j -= 1;
321                res = res.square();
322
323                if ((exp.as_limbs()[i].0 >> j) & 1) == 1 {
324                    res = res.multiply(self);
325                }
326            }
327        }
328
329        res
330    }
331
332    /// Returns `self^(2^n) mod p`.
333    ///
334    /// **This operation is variable time with respect to the exponent `n`.**
335    ///
336    /// If the exponent is fixed, this operation is constant time.
337    pub const fn sqn_vartime(&self, n: usize) -> Self {
338        let mut x = *self;
339        let mut i = 0;
340        while i < n {
341            x = x.square();
342            i += 1;
343        }
344        x
345    }
346
347    /// Compute [`FieldElement`] inversion: `1 / self`.
348    pub fn invert(&self) -> CtOption<Self> {
349        self.to_uint()
350            .invert_odd_mod(const { &Odd::from_be_hex(MODULUS_HEX) })
351            .map(Self::from_uint_unchecked)
352            .into()
353    }
354
355    /// Compute [`FieldElement`] inversion: `1 / self` in variable-time.
356    pub fn invert_vartime(&self) -> CtOption<Self> {
357        self.to_uint()
358            .invert_odd_mod_vartime(const { &Odd::from_be_hex(MODULUS_HEX) })
359            .map(Self::from_uint_unchecked)
360            .into()
361    }
362
363    /// Returns the multiplicative inverse of self.
364    ///
365    /// # Panics
366    /// Will panic in the event `self` is zero
367    const fn invert_unwrap(&self) -> Self {
368        Self::from_uint_unchecked(
369            self.to_uint()
370                .invert_odd_mod(const { &Odd::from_be_hex(MODULUS_HEX) })
371                .expect_copied("input should be non-zero"),
372        )
373    }
374
375    /// Returns the square root of self mod p, or `None` if no square root
376    /// exists.
377    ///
378    /// # Implementation details
379    /// If _x_ has a sqrt, then due to Euler's criterion this implies x<sup>(p - 1)/2</sup> = 1.
380    /// 1. x<sup>(p + 1)/2</sup> = x.
381    /// 2. There's a special property due to _p ≡ 3 (mod 4)_ which implies _(p + 1)/4_ is an integer.
382    /// 3. We can rewrite `1.` as x<sup>((p+1)/4)<sup>2</sup></sup>
383    /// 4. x<sup>(p+1)/4</sup> is the square root.
384    /// 5. This is simplified as (2<sup>251</sup> - 1 + 1) /4 = 2<sup>519</sup>
385    /// 6. Hence, x<sup>2<sup>519</sup></sup> is the square root iff _result.square() == self_
386    pub fn sqrt(&self) -> CtOption<Self> {
387        let sqrt = self.sqn(519);
388        CtOption::new(sqrt, sqrt.square().ct_eq(self))
389    }
390
391    /// Relax a tight field element into a loose one.
392    #[inline]
393    pub const fn relax(&self) -> LooseFieldElement {
394        let mut out = fiat_p521_loose_field_element([0; Self::LIMBS]);
395        fiat_p521_relax(&mut out, &self.0);
396        LooseFieldElement(out)
397    }
398
399    /// Raise this field element into a canonical integer representative.
400    #[inline]
401    pub(crate) const fn to_uint(self) -> Uint {
402        let field_bytes = self.to_bytes();
403        let mut uint_bytes = [0u8; Uint::LIMBS * Limb::BYTES];
404
405        let offset = uint_bytes.len() - field_bytes.0.len();
406        let mut i = 0;
407        while i < field_bytes.0.len() {
408            uint_bytes[i + offset] = field_bytes.0[i];
409            i += 1;
410        }
411
412        Uint::from_be_slice(&uint_bytes)
413    }
414}
415
416impl AsRef<fiat_p521_tight_field_element> for FieldElement {
417    fn as_ref(&self) -> &fiat_p521_tight_field_element {
418        &self.0
419    }
420}
421
422impl BatchInvert for FieldElement {}
423
424impl Default for FieldElement {
425    fn default() -> Self {
426        Self::ZERO
427    }
428}
429
430impl Debug for FieldElement {
431    /// Formatting machinery for [`FieldElement`]
432    ///
433    /// # Why
434    /// ```ignore
435    /// let fe1 = FieldElement([9, 0, 0, 0, 0, 0, 0, 0, 0]);
436    /// let fe2 = FieldElement([
437    ///     8,
438    ///     0,
439    ///     288230376151711744,
440    ///     288230376151711743,
441    ///     288230376151711743,
442    ///     288230376151711743,
443    ///     288230376151711743,
444    ///     288230376151711743,
445    ///     144115188075855871,
446    /// ]);
447    /// ```
448    ///
449    /// For the above example, deriving [`core::fmt::Debug`] will result in returning 2 different
450    /// strings, which are in reality the same due to p521's unsaturated math, instead print the
451    /// output as a hex string in big-endian.
452    ///
453    /// This makes debugging easier.
454    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
455        let bytes = self.to_bytes();
456        let formatter = base16ct::HexDisplay(&bytes);
457        f.debug_tuple("FieldElement")
458            .field(&format_args!("0x{formatter:X}"))
459            .finish()
460    }
461}
462
463impl Eq for FieldElement {}
464impl PartialEq for FieldElement {
465    fn eq(&self, rhs: &Self) -> bool {
466        self.ct_eq(rhs).into()
467    }
468}
469
470impl From<u32> for FieldElement {
471    fn from(n: u32) -> FieldElement {
472        Self::from_uint_unchecked(Uint::from(n))
473    }
474}
475
476impl From<u64> for FieldElement {
477    fn from(n: u64) -> FieldElement {
478        Self::from_uint_unchecked(Uint::from(n))
479    }
480}
481
482impl From<u128> for FieldElement {
483    fn from(n: u128) -> FieldElement {
484        Self::from_uint_unchecked(Uint::from(n))
485    }
486}
487
488impl ConditionallySelectable for FieldElement {
489    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
490        let out = <[Word; Self::LIMBS]>::conditional_select(&a.0.0, &b.0.0, choice);
491        Self(fiat_p521_tight_field_element(out))
492    }
493}
494
495impl ConstantTimeEq for FieldElement {
496    fn ct_eq(&self, other: &Self) -> Choice {
497        let a = self.to_bytes();
498        let b = other.to_bytes();
499        a.ct_eq(&b)
500    }
501}
502
503impl DefaultIsZeroes for FieldElement {}
504
505impl Field for FieldElement {
506    const ZERO: Self = Self::ZERO;
507    const ONE: Self = Self::ONE;
508
509    fn try_random<R: TryRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
510        // NOTE: can't use ScalarValue::random due to CryptoRng bound
511        let mut bytes = <FieldBytes>::default();
512
513        loop {
514            rng.try_fill_bytes(&mut bytes)?;
515            if let Some(fe) = Self::from_bytes(&bytes).into() {
516                return Ok(fe);
517            }
518        }
519    }
520
521    fn is_zero(&self) -> Choice {
522        Self::ZERO.ct_eq(self)
523    }
524
525    fn square(&self) -> Self {
526        self.square()
527    }
528
529    fn double(&self) -> Self {
530        self.double()
531    }
532
533    fn invert(&self) -> CtOption<Self> {
534        self.invert()
535    }
536
537    fn sqrt(&self) -> CtOption<Self> {
538        self.sqrt()
539    }
540
541    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
542        ff::helpers::sqrt_ratio_generic(num, div)
543    }
544}
545
546impl FieldExt for FieldElement {}
547impl PrimeFieldExt for FieldElement {}
548
549impl Generate for FieldElement {
550    fn try_generate_from_rng<R: TryRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
551        Self::try_random(rng)
552    }
553}
554
555impl PrimeField for FieldElement {
556    type Repr = FieldBytes;
557
558    const MODULUS: &'static str = MODULUS_HEX;
559    const NUM_BITS: u32 = 521;
560    const CAPACITY: u32 = 520;
561    const TWO_INV: Self = Self::from_u64(2).invert_unwrap();
562    const MULTIPLICATIVE_GENERATOR: Self = Self::from_u64(3);
563    const S: u32 = 1;
564    const ROOT_OF_UNITY: Self = Self::from_hex(
565        "01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe",
566    );
567    const ROOT_OF_UNITY_INV: Self = Self::ROOT_OF_UNITY.invert_unwrap();
568    const DELTA: Self = Self::from_u64(9);
569
570    #[inline]
571    fn from_repr(bytes: FieldBytes) -> CtOption<Self> {
572        Self::from_bytes(&bytes)
573    }
574
575    #[inline]
576    fn to_repr(&self) -> FieldBytes {
577        self.to_bytes()
578    }
579
580    #[inline]
581    fn is_odd(&self) -> Choice {
582        self.is_odd()
583    }
584}
585
586//
587// `core::ops` impls
588//
589
590impl Add for FieldElement {
591    type Output = FieldElement;
592
593    #[inline]
594    fn add(self, rhs: FieldElement) -> FieldElement {
595        Self::add(&self, &rhs)
596    }
597}
598
599impl Add<&FieldElement> for FieldElement {
600    type Output = FieldElement;
601
602    #[inline]
603    fn add(self, rhs: &FieldElement) -> FieldElement {
604        Self::add(&self, rhs)
605    }
606}
607
608impl Add<&FieldElement> for &FieldElement {
609    type Output = FieldElement;
610
611    #[inline]
612    fn add(self, rhs: &FieldElement) -> FieldElement {
613        FieldElement::add(self, rhs)
614    }
615}
616
617impl AddAssign<FieldElement> for FieldElement {
618    #[inline]
619    fn add_assign(&mut self, other: FieldElement) {
620        *self = *self + other;
621    }
622}
623
624impl AddAssign<&FieldElement> for FieldElement {
625    #[inline]
626    fn add_assign(&mut self, other: &FieldElement) {
627        *self = *self + other;
628    }
629}
630
631impl Sub for FieldElement {
632    type Output = FieldElement;
633
634    #[inline]
635    fn sub(self, rhs: FieldElement) -> FieldElement {
636        Self::sub(&self, &rhs)
637    }
638}
639
640impl Sub<&FieldElement> for FieldElement {
641    type Output = FieldElement;
642
643    #[inline]
644    fn sub(self, rhs: &FieldElement) -> FieldElement {
645        Self::sub(&self, rhs)
646    }
647}
648
649impl Sub<&FieldElement> for &FieldElement {
650    type Output = FieldElement;
651
652    #[inline]
653    fn sub(self, rhs: &FieldElement) -> FieldElement {
654        FieldElement::sub(self, rhs)
655    }
656}
657
658impl SubAssign<FieldElement> for FieldElement {
659    #[inline]
660    fn sub_assign(&mut self, other: FieldElement) {
661        *self = *self - other;
662    }
663}
664
665impl SubAssign<&FieldElement> for FieldElement {
666    #[inline]
667    fn sub_assign(&mut self, other: &FieldElement) {
668        *self = *self - other;
669    }
670}
671
672impl Mul for FieldElement {
673    type Output = FieldElement;
674
675    #[inline]
676    fn mul(self, rhs: FieldElement) -> FieldElement {
677        self.relax().mul(&rhs.relax())
678    }
679}
680
681impl Mul<&FieldElement> for FieldElement {
682    type Output = FieldElement;
683
684    #[inline]
685    fn mul(self, rhs: &FieldElement) -> FieldElement {
686        self.relax().mul(&rhs.relax())
687    }
688}
689
690impl Mul<&FieldElement> for &FieldElement {
691    type Output = FieldElement;
692
693    #[inline]
694    fn mul(self, rhs: &FieldElement) -> FieldElement {
695        self.relax().mul(&rhs.relax())
696    }
697}
698
699impl MulAssign<&FieldElement> for FieldElement {
700    #[inline]
701    fn mul_assign(&mut self, other: &FieldElement) {
702        *self = *self * other;
703    }
704}
705
706impl MulAssign for FieldElement {
707    #[inline]
708    fn mul_assign(&mut self, other: FieldElement) {
709        *self = *self * other;
710    }
711}
712
713impl Neg for FieldElement {
714    type Output = FieldElement;
715
716    #[inline]
717    fn neg(self) -> FieldElement {
718        Self::neg(&self)
719    }
720}
721
722//
723// `core::iter` trait impls
724//
725
726impl Sum for FieldElement {
727    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
728        iter.reduce(Add::add).unwrap_or(Self::ZERO)
729    }
730}
731
732impl<'a> Sum<&'a FieldElement> for FieldElement {
733    fn sum<I: Iterator<Item = &'a FieldElement>>(iter: I) -> Self {
734        iter.copied().sum()
735    }
736}
737
738impl Product for FieldElement {
739    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
740        iter.reduce(Mul::mul).unwrap_or(Self::ONE)
741    }
742}
743
744impl<'a> Product<&'a FieldElement> for FieldElement {
745    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
746        iter.copied().product()
747    }
748}
749
750// `crypto-bigint` trait impls
751
752impl Invert for FieldElement {
753    type Output = CtOption<Self>;
754
755    fn invert(&self) -> CtOption<Self> {
756        self.invert()
757    }
758
759    fn invert_vartime(&self) -> CtOption<Self> {
760        self.invert_vartime()
761    }
762}
763
764impl Retrieve for FieldElement {
765    type Output = Uint;
766
767    fn retrieve(&self) -> Uint {
768        self.to_uint()
769    }
770}
771
772#[cfg(test)]
773mod tests {
774    use super::{FieldElement, Uint};
775    use hex_literal::hex;
776
777    primefield::test_primefield!(FieldElement, Uint);
778
779    /// Regression test for RustCrypto/elliptic-curves#965
780    #[test]
781    fn decode_invalid_field_element_returns_err() {
782        let overflowing_bytes = hex!(
783            "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
784        );
785        let ct_option = FieldElement::from_bytes(&overflowing_bytes.into());
786        assert!(bool::from(ct_option.is_none()));
787    }
788
789    #[test]
790    fn sqn_edge_cases() {
791        let a = FieldElement::from_u64(5);
792        assert_eq!(a.sqn(0), a);
793        assert_eq!(a.sqn(1), a.square());
794        assert_eq!(a.sqn(2), a.square().square());
795    }
796}
p521/arithmetic/field.rs

p521/arithmetic/
field.rs
