primeorder/
field.rs

Help
1/// Implements a field element type whose internal representation is in
2/// Montgomery form, providing a combination of trait impls and inherent impls
3/// which are `const fn` where possible.
4///
5/// Accepts a set of `const fn` arithmetic operation functions as arguments.
6///
7/// # Inherent impls
8/// - `const ZERO: Self`
9/// - `const ONE: Self` (multiplicative identity)
10/// - `pub fn from_bytes`
11/// - `pub fn from_slice`
12/// - `pub fn from_uint`
13/// - `fn from_uint_unchecked`
14/// - `pub fn to_bytes`
15/// - `pub fn to_canonical`
16/// - `pub fn is_odd`
17/// - `pub fn is_zero`
18/// - `pub fn double`
19///
20/// NOTE: field implementations must provide their own inherent impls of
21/// the following methods in order for the code generated by this macro to
22/// compile:
23///
24/// - `pub fn invert`
25/// - `pub fn sqrt`
26///
27/// # Trait impls
28/// - `AsRef<$arr>`
29/// - `ConditionallySelectable`
30/// - `ConstantTimeEq`
31/// - `ConstantTimeGreater`
32/// - `ConstantTimeLess`
33/// - `Default`
34/// - `DefaultIsZeroes`
35/// - `Eq`
36/// - `Field`
37/// - `PartialEq`
38///
39/// ## Ops
40/// - `Add`
41/// - `AddAssign`
42/// - `Sub`
43/// - `SubAssign`
44/// - `Mul`
45/// - `MulAssign`
46/// - `Neg`
47#[macro_export]
48macro_rules! impl_mont_field_element {
49    (
50        $curve:tt,
51        $fe:tt,
52        $bytes:ty,
53        $uint:ty,
54        $modulus:expr,
55        $arr:ty,
56        $from_mont:ident,
57        $to_mont:ident,
58        $add:ident,
59        $sub:ident,
60        $mul:ident,
61        $neg:ident,
62        $square:ident
63    ) => {
64        impl $fe {
65            /// Zero element.
66            pub const ZERO: Self = Self(<$uint>::ZERO);
67
68            /// Multiplicative identity.
69            pub const ONE: Self = Self::from_uint_unchecked(<$uint>::ONE);
70
71            /// Create a [`
72            #[doc = stringify!($fe)]
73            /// `] from a canonical big-endian representation.
74            pub fn from_bytes(repr: &$bytes) -> $crate::elliptic_curve::subtle::CtOption<Self> {
75                use $crate::elliptic_curve::FieldBytesEncoding;
76                Self::from_uint(FieldBytesEncoding::<$curve>::decode_field_bytes(repr))
77            }
78
79            /// Decode [`
80            #[doc = stringify!($fe)]
81            /// `] from a big endian byte slice.
82            pub fn from_slice(slice: &[u8]) -> $crate::elliptic_curve::Result<Self> {
83                use $crate::elliptic_curve::generic_array::{typenum::Unsigned, GenericArray};
84
85                if slice.len() != <$curve as $crate::elliptic_curve::Curve>::FieldBytesSize::USIZE {
86                    return Err($crate::elliptic_curve::Error);
87                }
88
89                Option::from(Self::from_bytes(GenericArray::from_slice(slice)))
90                    .ok_or($crate::elliptic_curve::Error)
91            }
92
93            /// Decode [`
94            #[doc = stringify!($fe)]
95            /// `]
96            /// from [`
97            #[doc = stringify!($uint)]
98            /// `] converting it into Montgomery form:
99            ///
100            /// ```text
101            /// w * R^2 * R^-1 mod p = wR mod p
102            /// ```
103            pub fn from_uint(uint: $uint) -> $crate::elliptic_curve::subtle::CtOption<Self> {
104                use $crate::elliptic_curve::subtle::ConstantTimeLess as _;
105                let is_some = uint.ct_lt(&$modulus);
106                $crate::elliptic_curve::subtle::CtOption::new(
107                    Self::from_uint_unchecked(uint),
108                    is_some,
109                )
110            }
111
112            /// Parse a [`
113            #[doc = stringify!($fe)]
114            /// `] from big endian hex-encoded bytes.
115            ///
116            /// Does *not* perform a check that the field element does not overflow the order.
117            ///
118            /// This method is primarily intended for defining internal constants.
119            #[allow(dead_code)]
120            pub(crate) const fn from_hex(hex: &str) -> Self {
121                Self::from_uint_unchecked(<$uint>::from_be_hex(hex))
122            }
123
124            /// Convert a `u64` into a [`
125            #[doc = stringify!($fe)]
126            /// `].
127            pub const fn from_u64(w: u64) -> Self {
128                Self::from_uint_unchecked(<$uint>::from_u64(w))
129            }
130
131            /// Decode [`
132            #[doc = stringify!($fe)]
133            /// `] from [`
134            #[doc = stringify!($uint)]
135            /// `] converting it into Montgomery form.
136            ///
137            /// Does *not* perform a check that the field element does not overflow the order.
138            ///
139            /// Used incorrectly this can lead to invalid results!
140            pub(crate) const fn from_uint_unchecked(w: $uint) -> Self {
141                Self(<$uint>::from_words($to_mont(w.as_words())))
142            }
143
144            /// Returns the big-endian encoding of this [`
145            #[doc = stringify!($fe)]
146            /// `].
147            pub fn to_bytes(self) -> $bytes {
148                use $crate::elliptic_curve::FieldBytesEncoding;
149                FieldBytesEncoding::<$curve>::encode_field_bytes(&self.to_canonical())
150            }
151
152            /// Translate [`
153            #[doc = stringify!($fe)]
154            /// `] out of the Montgomery domain, returning a [`
155            #[doc = stringify!($uint)]
156            /// `] in canonical form.
157            #[inline]
158            pub const fn to_canonical(self) -> $uint {
159                <$uint>::from_words($from_mont(self.0.as_words()))
160            }
161
162            /// Determine if this [`
163            #[doc = stringify!($fe)]
164            /// `] is odd in the SEC1 sense: `self mod 2 == 1`.
165            ///
166            /// # Returns
167            ///
168            /// If odd, return `Choice(1)`.  Otherwise, return `Choice(0)`.
169            pub fn is_odd(&self) -> Choice {
170                use $crate::elliptic_curve::bigint::Integer;
171                self.to_canonical().is_odd()
172            }
173
174            /// Determine if this [`
175            #[doc = stringify!($fe)]
176            /// `] is even in the SEC1 sense: `self mod 2 == 0`.
177            ///
178            /// # Returns
179            ///
180            /// If even, return `Choice(1)`.  Otherwise, return `Choice(0)`.
181            pub fn is_even(&self) -> Choice {
182                !self.is_odd()
183            }
184
185            /// Determine if this [`
186            #[doc = stringify!($fe)]
187            /// `] is zero.
188            ///
189            /// # Returns
190            ///
191            /// If zero, return `Choice(1)`.  Otherwise, return `Choice(0)`.
192            pub fn is_zero(&self) -> Choice {
193                self.ct_eq(&Self::ZERO)
194            }
195
196            /// Add elements.
197            pub const fn add(&self, rhs: &Self) -> Self {
198                Self(<$uint>::from_words($add(
199                    self.0.as_words(),
200                    rhs.0.as_words(),
201                )))
202            }
203
204            /// Double element (add it to itself).
205            #[must_use]
206            pub const fn double(&self) -> Self {
207                self.add(self)
208            }
209
210            /// Subtract elements.
211            pub const fn sub(&self, rhs: &Self) -> Self {
212                Self(<$uint>::from_words($sub(
213                    self.0.as_words(),
214                    rhs.0.as_words(),
215                )))
216            }
217
218            /// Multiply elements.
219            pub const fn multiply(&self, rhs: &Self) -> Self {
220                Self(<$uint>::from_words($mul(
221                    self.0.as_words(),
222                    rhs.0.as_words(),
223                )))
224            }
225
226            /// Negate element.
227            pub const fn neg(&self) -> Self {
228                Self(<$uint>::from_words($neg(self.0.as_words())))
229            }
230
231            /// Compute modular square.
232            #[must_use]
233            pub const fn square(&self) -> Self {
234                Self(<$uint>::from_words($square(self.0.as_words())))
235            }
236
237            /// Returns `self^exp`, where `exp` is a little-endian integer exponent.
238            ///
239            /// **This operation is variable time with respect to the exponent.**
240            ///
241            /// If the exponent is fixed, this operation is effectively constant time.
242            pub const fn pow_vartime(&self, exp: &[u64]) -> Self {
243                let mut res = Self::ONE;
244                let mut i = exp.len();
245
246                while i > 0 {
247                    i -= 1;
248
249                    let mut j = 64;
250                    while j > 0 {
251                        j -= 1;
252                        res = res.square();
253
254                        if ((exp[i] >> j) & 1) == 1 {
255                            res = res.multiply(self);
256                        }
257                    }
258                }
259
260                res
261            }
262        }
263
264        $crate::impl_mont_field_element_arithmetic!(
265            $fe, $bytes, $uint, $arr, $add, $sub, $mul, $neg
266        );
267    };
268}
269
270/// Add arithmetic impls to the given field element.
271#[macro_export]
272macro_rules! impl_mont_field_element_arithmetic {
273    (
274        $fe:tt,
275        $bytes:ty,
276        $uint:ty,
277        $arr:ty,
278        $add:ident,
279        $sub:ident,
280        $mul:ident,
281        $neg:ident
282    ) => {
283        impl AsRef<$arr> for $fe {
284            fn as_ref(&self) -> &$arr {
285                self.0.as_ref()
286            }
287        }
288
289        impl Default for $fe {
290            fn default() -> Self {
291                Self::ZERO
292            }
293        }
294
295        impl Eq for $fe {}
296        impl PartialEq for $fe {
297            fn eq(&self, rhs: &Self) -> bool {
298                self.0.ct_eq(&(rhs.0)).into()
299            }
300        }
301
302        impl From<u32> for $fe {
303            fn from(n: u32) -> $fe {
304                Self::from_uint_unchecked(<$uint>::from(n))
305            }
306        }
307
308        impl From<u64> for $fe {
309            fn from(n: u64) -> $fe {
310                Self::from_uint_unchecked(<$uint>::from(n))
311            }
312        }
313
314        impl From<u128> for $fe {
315            fn from(n: u128) -> $fe {
316                Self::from_uint_unchecked(<$uint>::from(n))
317            }
318        }
319
320        impl $crate::elliptic_curve::subtle::ConditionallySelectable for $fe {
321            fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
322                Self(<$uint>::conditional_select(&a.0, &b.0, choice))
323            }
324        }
325
326        impl $crate::elliptic_curve::subtle::ConstantTimeEq for $fe {
327            fn ct_eq(&self, other: &Self) -> $crate::elliptic_curve::subtle::Choice {
328                self.0.ct_eq(&other.0)
329            }
330        }
331
332        impl $crate::elliptic_curve::subtle::ConstantTimeGreater for $fe {
333            fn ct_gt(&self, other: &Self) -> $crate::elliptic_curve::subtle::Choice {
334                self.0.ct_gt(&other.0)
335            }
336        }
337
338        impl $crate::elliptic_curve::subtle::ConstantTimeLess for $fe {
339            fn ct_lt(&self, other: &Self) -> $crate::elliptic_curve::subtle::Choice {
340                self.0.ct_lt(&other.0)
341            }
342        }
343
344        impl $crate::elliptic_curve::zeroize::DefaultIsZeroes for $fe {}
345
346        impl $crate::elliptic_curve::ff::Field for $fe {
347            const ZERO: Self = Self::ZERO;
348            const ONE: Self = Self::ONE;
349
350            fn random(mut rng: impl $crate::elliptic_curve::rand_core::RngCore) -> Self {
351                // NOTE: can't use ScalarPrimitive::random due to CryptoRng bound
352                let mut bytes = <$bytes>::default();
353
354                loop {
355                    rng.fill_bytes(&mut bytes);
356                    if let Some(fe) = Self::from_bytes(&bytes).into() {
357                        return fe;
358                    }
359                }
360            }
361
362            fn is_zero(&self) -> Choice {
363                Self::ZERO.ct_eq(self)
364            }
365
366            #[must_use]
367            fn square(&self) -> Self {
368                self.square()
369            }
370
371            #[must_use]
372            fn double(&self) -> Self {
373                self.double()
374            }
375
376            fn invert(&self) -> CtOption<Self> {
377                self.invert()
378            }
379
380            fn sqrt(&self) -> CtOption<Self> {
381                self.sqrt()
382            }
383
384            fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
385                $crate::elliptic_curve::ff::helpers::sqrt_ratio_generic(num, div)
386            }
387        }
388
389        $crate::impl_field_op!($fe, Add, add, $add);
390        $crate::impl_field_op!($fe, Sub, sub, $sub);
391        $crate::impl_field_op!($fe, Mul, mul, $mul);
392
393        impl AddAssign<$fe> for $fe {
394            #[inline]
395            fn add_assign(&mut self, other: $fe) {
396                *self = *self + other;
397            }
398        }
399
400        impl AddAssign<&$fe> for $fe {
401            #[inline]
402            fn add_assign(&mut self, other: &$fe) {
403                *self = *self + other;
404            }
405        }
406
407        impl SubAssign<$fe> for $fe {
408            #[inline]
409            fn sub_assign(&mut self, other: $fe) {
410                *self = *self - other;
411            }
412        }
413
414        impl SubAssign<&$fe> for $fe {
415            #[inline]
416            fn sub_assign(&mut self, other: &$fe) {
417                *self = *self - other;
418            }
419        }
420
421        impl MulAssign<&$fe> for $fe {
422            #[inline]
423            fn mul_assign(&mut self, other: &$fe) {
424                *self = *self * other;
425            }
426        }
427
428        impl MulAssign for $fe {
429            #[inline]
430            fn mul_assign(&mut self, other: $fe) {
431                *self = *self * other;
432            }
433        }
434
435        impl Neg for $fe {
436            type Output = $fe;
437
438            #[inline]
439            fn neg(self) -> $fe {
440                Self($neg(self.as_ref()).into())
441            }
442        }
443
444        impl Sum for $fe {
445            fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
446                iter.reduce(core::ops::Add::add).unwrap_or(Self::ZERO)
447            }
448        }
449
450        impl<'a> Sum<&'a $fe> for $fe {
451            fn sum<I: Iterator<Item = &'a $fe>>(iter: I) -> Self {
452                iter.copied().sum()
453            }
454        }
455
456        impl Product for $fe {
457            fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
458                iter.reduce(core::ops::Mul::mul).unwrap_or(Self::ONE)
459            }
460        }
461
462        impl<'a> Product<&'a $fe> for $fe {
463            fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
464                iter.copied().product()
465            }
466        }
467    };
468}
469
470/// Emit impls for a `core::ops` trait for all combinations of reference types,
471/// which thunk to the given function.
472#[macro_export]
473macro_rules! impl_field_op {
474    ($fe:tt, $op:tt, $op_fn:ident, $func:ident) => {
475        impl ::core::ops::$op for $fe {
476            type Output = $fe;
477
478            #[inline]
479            fn $op_fn(self, rhs: $fe) -> $fe {
480                $fe($func(self.as_ref(), rhs.as_ref()).into())
481            }
482        }
483
484        impl ::core::ops::$op<&$fe> for $fe {
485            type Output = $fe;
486
487            #[inline]
488            fn $op_fn(self, rhs: &$fe) -> $fe {
489                $fe($func(self.as_ref(), rhs.as_ref()).into())
490            }
491        }
492
493        impl ::core::ops::$op<&$fe> for &$fe {
494            type Output = $fe;
495
496            #[inline]
497            fn $op_fn(self, rhs: &$fe) -> $fe {
498                $fe($func(self.as_ref(), rhs.as_ref()).into())
499            }
500        }
501    };
502}
503
504/// Implement Bernstein-Yang field element inversion.
505#[macro_export]
506macro_rules! impl_bernstein_yang_invert {
507    (
508        $a:expr,
509        $one:expr,
510        $d:expr,
511        $nlimbs:expr,
512        $word:ty,
513        $from_mont:ident,
514        $mul:ident,
515        $neg:ident,
516        $divstep_precomp:ident,
517        $divstep:ident,
518        $msat:ident,
519        $selectznz:ident,
520    ) => {{
521        // See Bernstein-Yang 2019 p.366
522        const ITERATIONS: usize = (49 * $d + 57) / 17;
523
524        let a = $from_mont($a);
525        let mut d = 1;
526        let mut f = $msat();
527        let mut g = [0; $nlimbs + 1];
528        let mut v = [0; $nlimbs];
529        let mut r = $one;
530        let mut i = 0;
531        let mut j = 0;
532
533        while j < $nlimbs {
534            g[j] = a[j];
535            j += 1;
536        }
537
538        while i < ITERATIONS - ITERATIONS % 2 {
539            let (out1, out2, out3, out4, out5) = $divstep(d, &f, &g, &v, &r);
540            let (out1, out2, out3, out4, out5) = $divstep(out1, &out2, &out3, &out4, &out5);
541            d = out1;
542            f = out2;
543            g = out3;
544            v = out4;
545            r = out5;
546            i += 2;
547        }
548
549        if ITERATIONS % 2 != 0 {
550            let (_out1, out2, _out3, out4, _out5) = $divstep(d, &f, &g, &v, &r);
551            v = out4;
552            f = out2;
553        }
554
555        let s = ((f[f.len() - 1] >> <$word>::BITS - 1) & 1) as u8;
556        let v = $selectznz(s, &v, &$neg(&v));
557        $mul(&v, &$divstep_precomp())
558    }};
559}
560
561/// Implement field element identity tests.
562#[macro_export]
563macro_rules! impl_field_identity_tests {
564    ($fe:tt) => {
565        #[test]
566        fn zero_is_additive_identity() {
567            let zero = $fe::ZERO;
568            let one = $fe::ONE;
569            assert_eq!(zero.add(&zero), zero);
570            assert_eq!(one.add(&zero), one);
571        }
572
573        #[test]
574        fn one_is_multiplicative_identity() {
575            let one = $fe::ONE;
576            assert_eq!(one.multiply(&one), one);
577        }
578    };
579}
580
581/// Implement field element inversion tests.
582#[macro_export]
583macro_rules! impl_field_invert_tests {
584    ($fe:tt) => {
585        #[test]
586        fn invert() {
587            let one = $fe::ONE;
588            assert_eq!(one.invert().unwrap(), one);
589
590            let three = one + &one + &one;
591            let inv_three = three.invert().unwrap();
592            assert_eq!(three * &inv_three, one);
593
594            let minus_three = -three;
595            let inv_minus_three = minus_three.invert().unwrap();
596            assert_eq!(inv_minus_three, -inv_three);
597            assert_eq!(three * &inv_minus_three, -one);
598        }
599    };
600}
601
602/// Implement field element square root tests.
603#[macro_export]
604macro_rules! impl_field_sqrt_tests {
605    ($fe:tt) => {
606        #[test]
607        fn sqrt() {
608            for &n in &[1u64, 4, 9, 16, 25, 36, 49, 64] {
609                let fe = $fe::from(n);
610                let sqrt = fe.sqrt().unwrap();
611                assert_eq!(sqrt.square(), fe);
612            }
613        }
614    };
615}
616
617/// Implement tests for the `PrimeField` trait.
618#[macro_export]
619macro_rules! impl_primefield_tests {
620    ($fe:tt, $t:expr) => {
621        #[test]
622        fn two_inv_constant() {
623            assert_eq!($fe::from(2u32) * $fe::TWO_INV, $fe::ONE);
624        }
625
626        #[test]
627        fn root_of_unity_constant() {
628            assert!($fe::S < 128);
629            let two_to_s = 1u128 << $fe::S;
630
631            // ROOT_OF_UNITY^{2^s} mod m == 1
632            assert_eq!(
633                $fe::ROOT_OF_UNITY.pow_vartime(&[
634                    (two_to_s & 0xFFFFFFFFFFFFFFFF) as u64,
635                    (two_to_s >> 64) as u64,
636                    0,
637                    0
638                ]),
639                $fe::ONE
640            );
641
642            // MULTIPLICATIVE_GENERATOR^{t} mod m == ROOT_OF_UNITY
643            assert_eq!(
644                $fe::MULTIPLICATIVE_GENERATOR.pow_vartime(&$t),
645                $fe::ROOT_OF_UNITY
646            )
647        }
648
649        #[test]
650        fn root_of_unity_inv_constant() {
651            assert_eq!($fe::ROOT_OF_UNITY * $fe::ROOT_OF_UNITY_INV, $fe::ONE);
652        }
653
654        #[test]
655        fn delta_constant() {
656            // DELTA^{t} mod m == 1
657            assert_eq!($fe::DELTA.pow_vartime(&$t), $fe::ONE);
658        }
659    };
660}
primeorder/field.rs

primeorder/
field.rs
