openzeppelin_crypto/field/
mod.rs

1//! This module provides common arithmetics to work with finite fields.
2//! Implementations of some used fields provided in the [`instance`]
3//! module.
4//!
5//! Abstractions and api in this module are similar to Arkworks Algebra [ark-ff
6//! library].
7//!
8//! Here is an example operations over a prime finite field (aka Fp) with a
9//! prime modulus `17` and generator element `3`.
10//!
11//! # Examples
12//!
13//! ```rust
14//! use openzeppelin_crypto::{
15//!     arithmetic::uint::U64,
16//!     field::{
17//!         fp::{Fp64, FpParams, LIMBS_64},
18//!         group::AdditiveGroup,
19//!         Field,
20//!     },
21//!     fp_from_num,
22//!     from_num,
23//! };
24//!
25//! pub type ExampleField = Fp64<FpParam>;
26//! pub struct FpParam;
27//! impl FpParams<LIMBS_64> for FpParam {
28//!     const MODULUS: U64 = from_num!("17");
29//!     const GENERATOR: Fp64<FpParam> = fp_from_num!("3");
30//! }
31//!
32//! # fn main() {
33//! let a = ExampleField::from(9);
34//! let b = ExampleField::from(10);
35//!
36//! assert_eq!(a, ExampleField::from(26));          // 26 =  9 mod 17
37//! assert_eq!(a - b, ExampleField::from(16));      // -1 = 16 mod 17
38//! assert_eq!(a + b, ExampleField::from(2));       // 19 =  2 mod 17
39//! assert_eq!(a * b, ExampleField::from(5));       // 90 =  5 mod 17
40//! assert_eq!(a.square(), ExampleField::from(13)); // 81 = 13 mod 17
41//! assert_eq!(b.double(), ExampleField::from(3));  // 20 =  3 mod 17
42//! assert_eq!(a / b, a * b.inverse().unwrap());    // need to unwrap since `b` could be 0 which is not invertible
43//! # }
44//! ```
45//!
46//! [ark-ff library]: https://github.com/arkworks-rs/algebra/tree/master/ff
47use core::{
48    fmt::{Debug, Display},
49    hash::Hash,
50    iter::Product,
51    ops::{Div, DivAssign, Neg},
52};
53
54use group::AdditiveGroup;
55use num_traits::{One, Zero};
56use zeroize::Zeroize;
57
58use crate::bits::BitIteratorBE;
59
60pub mod fp;
61pub mod group;
62pub mod instance;
63pub mod prime;
64
65/// Defines an abstract field.
66/// Types implementing [`Field`] support common field operations such as
67/// addition, subtraction, multiplication, and inverses.
68pub trait Field:
69    'static
70    + Copy
71    + Clone
72    + Debug
73    + Display
74    + Default
75    + Send
76    + Sync
77    + Eq
78    + Zero
79    + One
80    + Ord
81    + Neg<Output = Self>
82    + Zeroize
83    + Sized
84    + Hash
85    + AdditiveGroup<Scalar = Self>
86    + Div<Self, Output = Self>
87    + DivAssign<Self>
88    + for<'a> Div<&'a Self, Output = Self>
89    + for<'a> DivAssign<&'a Self>
90    + for<'a> Div<&'a mut Self, Output = Self>
91    + for<'a> DivAssign<&'a mut Self>
92    + for<'a> Product<&'a Self>
93    + From<u128>
94    + From<u64>
95    + From<u32>
96    + From<u16>
97    + From<u8>
98    + From<i128>
99    + From<i64>
100    + From<i32>
101    + From<i16>
102    + From<i8>
103    + From<bool>
104    + Product<Self>
105{
106    /// The multiplicative identity of the field.
107    const ONE: Self;
108
109    /// Returns the extension degree of this field.
110    #[must_use]
111    fn extension_degree() -> usize;
112
113    /// Returns `self * self`.
114    #[must_use]
115    fn square(&self) -> Self;
116
117    /// Squares `self` in place.
118    fn square_in_place(&mut self) -> &mut Self;
119
120    /// Computes the multiplicative inverse of `self` if `self` is nonzero.
121    fn inverse(&self) -> Option<Self>;
122
123    /// If `self.inverse().is_none()`, this just returns `None`. Otherwise, it
124    /// sets `self` to `self.inverse().unwrap()`.
125    fn inverse_in_place(&mut self) -> Option<&mut Self>;
126
127    /// Returns `self^exp`, where `exp` is an integer.
128    ///
129    /// NOTE: Consumers should pass `exp`'s type `S` with the least bit size
130    /// possible.
131    /// e.g. for `pow(12)` u8 type is small enough to represent `12`.
132    #[must_use]
133    fn pow<S: BitIteratorBE>(&self, exp: S) -> Self {
134        // Variant `Option::<Self>::None` corresponds to `one`.
135        // This approach removes pointless multiplications by one, that
136        // are still expensive.
137        let mut res: Option<Self> = None;
138
139        for has_bit in exp.bit_be_trimmed_iter() {
140            // If res is not empty, square it.
141            if let Some(res) = &mut res {
142                res.square_in_place();
143            }
144
145            // If bit is set,
146            if has_bit {
147                match res {
148                    None => {
149                        // and res is empty, set it to self.
150                        res = Some(*self);
151                    }
152                    Some(ref mut res) => {
153                        // and res is not empty, multiply it by self.
154                        *res *= self;
155                    }
156                }
157            }
158        }
159
160        // If res is empty, return one.
161        res.unwrap_or(Self::ONE)
162    }
163
164    /// Returns `sum([a_i * b_i])`.
165    #[inline]
166    fn sum_of_products<const T: usize>(a: &[Self; T], b: &[Self; T]) -> Self {
167        let mut sum = Self::zero();
168        for i in 0..a.len() {
169            sum += a[i] * b[i];
170        }
171        sum
172    }
173}
openzeppelin_crypto/field/mod.rs

openzeppelin_crypto/field/
mod.rs
