ark_ff/fields/
mod.rs

1use crate::UniformRand;
2use ark_serialize::{
3    CanonicalDeserialize, CanonicalDeserializeWithFlags, CanonicalSerialize,
4    CanonicalSerializeWithFlags, EmptyFlags, Flags,
5};
6use ark_std::{
7    fmt::{Debug, Display},
8    hash::Hash,
9    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
10    vec::Vec,
11};
12
13pub use ark_ff_macros;
14use num_traits::{One, Zero};
15use zeroize::Zeroize;
16
17pub mod utils;
18
19#[macro_use]
20pub mod arithmetic;
21
22#[macro_use]
23pub mod models;
24pub use self::models::*;
25
26pub mod field_hashers;
27
28mod prime;
29pub use prime::*;
30
31mod fft_friendly;
32pub use fft_friendly::*;
33
34mod cyclotomic;
35pub use cyclotomic::*;
36
37mod sqrt;
38pub use sqrt::*;
39
40#[cfg(feature = "parallel")]
41use ark_std::cmp::max;
42#[cfg(feature = "parallel")]
43use rayon::prelude::*;
44
45/// The interface for a generic field.  
46/// Types implementing [`Field`] support common field operations such as addition, subtraction, multiplication, and inverses.
47///
48/// ## Defining your own field
49/// To demonstrate the various field operations, we can first define a prime ordered field $\mathbb{F}_{p}$ with $p = 17$. When defining a field $\mathbb{F}_p$, we need to provide the modulus(the $p$ in $\mathbb{F}_p$) and a generator. Recall that a generator $g \in \mathbb{F}_p$ is a field element whose powers comprise the entire field: $\mathbb{F}_p =\\{g, g^1, \ldots, g^{p-1}\\}$.
50/// We can then manually construct the field element associated with an integer with `Fp::from` and perform field addition, subtraction, multiplication, and inversion on it.
51/// ```rust
52/// use ark_ff::fields::{Field, Fp64, MontBackend, MontConfig};
53///
54/// #[derive(MontConfig)]
55/// #[modulus = "17"]
56/// #[generator = "3"]
57/// pub struct FqConfig;
58/// pub type Fq = Fp64<MontBackend<FqConfig, 1>>;
59///
60/// # fn main() {
61/// let a = Fq::from(9);
62/// let b = Fq::from(10);
63///
64/// assert_eq!(a, Fq::from(26));          // 26 =  9 mod 17
65/// assert_eq!(a - b, Fq::from(16));      // -1 = 16 mod 17
66/// assert_eq!(a + b, Fq::from(2));       // 19 =  2 mod 17
67/// assert_eq!(a * b, Fq::from(5));       // 90 =  5 mod 17
68/// assert_eq!(a.square(), Fq::from(13)); // 81 = 13 mod 17
69/// assert_eq!(b.double(), Fq::from(3));  // 20 =  3 mod 17
70/// assert_eq!(a / b, a * b.inverse().unwrap()); // need to unwrap since `b` could be 0 which is not invertible
71/// # }
72/// ```
73///
74/// ## Using pre-defined fields
75/// In the following example, we’ll use the field associated with the BLS12-381 pairing-friendly group.
76/// ```rust
77/// use ark_ff::Field;
78/// use ark_test_curves::bls12_381::Fq as F;
79/// use ark_std::{One, UniformRand, test_rng};
80///
81/// let mut rng = test_rng();
82/// // Let's sample uniformly random field elements:
83/// let a = F::rand(&mut rng);
84/// let b = F::rand(&mut rng);
85///
86/// let c = a + b;
87/// let d = a - b;
88/// assert_eq!(c + d, a.double());
89///
90/// let e = c * d;
91/// assert_eq!(e, a.square() - b.square());         // (a + b)(a - b) = a^2 - b^2
92/// assert_eq!(a.inverse().unwrap() * a, F::one()); // Euler-Fermat theorem tells us: a * a^{-1} = 1 mod p
93/// ```
94pub trait Field:
95    'static
96    + Copy
97    + Clone
98    + Debug
99    + Display
100    + Default
101    + Send
102    + Sync
103    + Eq
104    + Zero
105    + One
106    + Ord
107    + Neg<Output = Self>
108    + UniformRand
109    + Zeroize
110    + Sized
111    + Hash
112    + CanonicalSerialize
113    + CanonicalSerializeWithFlags
114    + CanonicalDeserialize
115    + CanonicalDeserializeWithFlags
116    + Add<Self, Output = Self>
117    + Sub<Self, Output = Self>
118    + Mul<Self, Output = Self>
119    + Div<Self, Output = Self>
120    + AddAssign<Self>
121    + SubAssign<Self>
122    + MulAssign<Self>
123    + DivAssign<Self>
124    + for<'a> Add<&'a Self, Output = Self>
125    + for<'a> Sub<&'a Self, Output = Self>
126    + for<'a> Mul<&'a Self, Output = Self>
127    + for<'a> Div<&'a Self, Output = Self>
128    + for<'a> AddAssign<&'a Self>
129    + for<'a> SubAssign<&'a Self>
130    + for<'a> MulAssign<&'a Self>
131    + for<'a> DivAssign<&'a Self>
132    + for<'a> Add<&'a mut Self, Output = Self>
133    + for<'a> Sub<&'a mut Self, Output = Self>
134    + for<'a> Mul<&'a mut Self, Output = Self>
135    + for<'a> Div<&'a mut Self, Output = Self>
136    + for<'a> AddAssign<&'a mut Self>
137    + for<'a> SubAssign<&'a mut Self>
138    + for<'a> MulAssign<&'a mut Self>
139    + for<'a> DivAssign<&'a mut Self>
140    + core::iter::Sum<Self>
141    + for<'a> core::iter::Sum<&'a Self>
142    + core::iter::Product<Self>
143    + for<'a> core::iter::Product<&'a Self>
144    + From<u128>
145    + From<u64>
146    + From<u32>
147    + From<u16>
148    + From<u8>
149    + From<bool>
150{
151    type BasePrimeField: PrimeField;
152
153    type BasePrimeFieldIter: Iterator<Item = Self::BasePrimeField>;
154
155    /// Determines the algorithm for computing square roots.
156    const SQRT_PRECOMP: Option<SqrtPrecomputation<Self>>;
157
158    /// The additive identity of the field.
159    const ZERO: Self;
160    /// The multiplicative identity of the field.
161    const ONE: Self;
162
163    /// Returns the characteristic of the field,
164    /// in little-endian representation.
165    fn characteristic() -> &'static [u64] {
166        Self::BasePrimeField::characteristic()
167    }
168
169    /// Returns the extension degree of this field with respect
170    /// to `Self::BasePrimeField`.
171    fn extension_degree() -> u64;
172
173    fn to_base_prime_field_elements(&self) -> Self::BasePrimeFieldIter;
174
175    /// Convert a slice of base prime field elements into a field element.
176    /// If the slice length != Self::extension_degree(), must return None.
177    fn from_base_prime_field_elems(elems: &[Self::BasePrimeField]) -> Option<Self>;
178
179    /// Constructs a field element from a single base prime field elements.
180    /// ```
181    /// # use ark_ff::Field;
182    /// # use ark_test_curves::bls12_381::Fq as F;
183    /// # use ark_test_curves::bls12_381::Fq2 as F2;
184    /// # use ark_std::One;
185    /// assert_eq!(F2::from_base_prime_field(F::one()), F2::one());
186    /// ```
187    fn from_base_prime_field(elem: Self::BasePrimeField) -> Self;
188
189    /// Returns `self + self`.
190    #[must_use]
191    fn double(&self) -> Self;
192
193    /// Doubles `self` in place.
194    fn double_in_place(&mut self) -> &mut Self;
195
196    /// Negates `self` in place.
197    fn neg_in_place(&mut self) -> &mut Self;
198
199    /// Attempt to deserialize a field element. Returns `None` if the
200    /// deserialization fails.
201    ///
202    /// This function is primarily intended for sampling random field elements
203    /// from a hash-function or RNG output.
204    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
205        Self::from_random_bytes_with_flags::<EmptyFlags>(bytes).map(|f| f.0)
206    }
207
208    /// Attempt to deserialize a field element, splitting the bitflags metadata
209    /// according to `F` specification. Returns `None` if the deserialization
210    /// fails.
211    ///
212    /// This function is primarily intended for sampling random field elements
213    /// from a hash-function or RNG output.
214    fn from_random_bytes_with_flags<F: Flags>(bytes: &[u8]) -> Option<(Self, F)>;
215
216    /// Returns a `LegendreSymbol`, which indicates whether this field element
217    /// is  1 : a quadratic residue
218    ///  0 : equal to 0
219    /// -1 : a quadratic non-residue
220    fn legendre(&self) -> LegendreSymbol;
221
222    /// Returns the square root of self, if it exists.
223    #[must_use]
224    fn sqrt(&self) -> Option<Self> {
225        match Self::SQRT_PRECOMP {
226            Some(tv) => tv.sqrt(self),
227            None => unimplemented!(),
228        }
229    }
230
231    /// Sets `self` to be the square root of `self`, if it exists.
232    fn sqrt_in_place(&mut self) -> Option<&mut Self> {
233        (*self).sqrt().map(|sqrt| {
234            *self = sqrt;
235            self
236        })
237    }
238
239    /// Returns `self * self`.
240    #[must_use]
241    fn square(&self) -> Self;
242
243    /// Squares `self` in place.
244    fn square_in_place(&mut self) -> &mut Self;
245
246    /// Computes the multiplicative inverse of `self` if `self` is nonzero.
247    #[must_use]
248    fn inverse(&self) -> Option<Self>;
249
250    /// If `self.inverse().is_none()`, this just returns `None`. Otherwise, it sets
251    /// `self` to `self.inverse().unwrap()`.
252    fn inverse_in_place(&mut self) -> Option<&mut Self>;
253
254    /// Returns `sum([a_i * b_i])`.
255    #[inline]
256    fn sum_of_products<const T: usize>(a: &[Self; T], b: &[Self; T]) -> Self {
257        let mut sum = Self::zero();
258        for i in 0..a.len() {
259            sum += a[i] * b[i];
260        }
261        sum
262    }
263
264    /// Sets `self` to `self^s`, where `s = Self::BasePrimeField::MODULUS^power`.
265    /// This is also called the Frobenius automorphism.
266    fn frobenius_map_in_place(&mut self, power: usize);
267
268    /// Returns `self^s`, where `s = Self::BasePrimeField::MODULUS^power`.
269    /// This is also called the Frobenius automorphism.
270    #[must_use]
271    fn frobenius_map(&self, power: usize) -> Self {
272        let mut this = *self;
273        this.frobenius_map_in_place(power);
274        this
275    }
276
277    /// Returns `self^exp`, where `exp` is an integer represented with `u64` limbs,
278    /// least significant limb first.
279    #[must_use]
280    fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
281        let mut res = Self::one();
282
283        for i in crate::BitIteratorBE::without_leading_zeros(exp) {
284            res.square_in_place();
285
286            if i {
287                res *= self;
288            }
289        }
290        res
291    }
292
293    /// Exponentiates a field element `f` by a number represented with `u64`
294    /// limbs, using a precomputed table containing as many powers of 2 of
295    /// `f` as the 1 + the floor of log2 of the exponent `exp`, starting
296    /// from the 1st power. That is, `powers_of_2` should equal `&[p, p^2,
297    /// p^4, ..., p^(2^n)]` when `exp` has at most `n` bits.
298    ///
299    /// This returns `None` when a power is missing from the table.
300    #[inline]
301    fn pow_with_table<S: AsRef<[u64]>>(powers_of_2: &[Self], exp: S) -> Option<Self> {
302        let mut res = Self::one();
303        for (pow, bit) in crate::BitIteratorLE::without_trailing_zeros(exp).enumerate() {
304            if bit {
305                res *= powers_of_2.get(pow)?;
306            }
307        }
308        Some(res)
309    }
310}
311
312// Given a vector of field elements {v_i}, compute the vector {v_i^(-1)}
313pub fn batch_inversion<F: Field>(v: &mut [F]) {
314    batch_inversion_and_mul(v, &F::one());
315}
316
317#[cfg(not(feature = "parallel"))]
318// Given a vector of field elements {v_i}, compute the vector {coeff * v_i^(-1)}
319pub fn batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
320    serial_batch_inversion_and_mul(v, coeff);
321}
322
323#[cfg(feature = "parallel")]
324// Given a vector of field elements {v_i}, compute the vector {coeff * v_i^(-1)}
325pub fn batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
326    // Divide the vector v evenly between all available cores
327    let min_elements_per_thread = 1;
328    let num_cpus_available = rayon::current_num_threads();
329    let num_elems = v.len();
330    let num_elem_per_thread = max(num_elems / num_cpus_available, min_elements_per_thread);
331
332    // Batch invert in parallel, without copying the vector
333    v.par_chunks_mut(num_elem_per_thread).for_each(|mut chunk| {
334        serial_batch_inversion_and_mul(&mut chunk, coeff);
335    });
336}
337
338/// Given a vector of field elements {v_i}, compute the vector {coeff * v_i^(-1)}.
339/// This method is explicitly single-threaded.
340fn serial_batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
341    // Montgomery’s Trick and Fast Implementation of Masked AES
342    // Genelle, Prouff and Quisquater
343    // Section 3.2
344    // but with an optimization to multiply every element in the returned vector by
345    // coeff
346
347    // First pass: compute [a, ab, abc, ...]
348    let mut prod = Vec::with_capacity(v.len());
349    let mut tmp = F::one();
350    for f in v.iter().filter(|f| !f.is_zero()) {
351        tmp.mul_assign(f);
352        prod.push(tmp);
353    }
354
355    // Invert `tmp`.
356    tmp = tmp.inverse().unwrap(); // Guaranteed to be nonzero.
357
358    // Multiply product by coeff, so all inverses will be scaled by coeff
359    tmp *= coeff;
360
361    // Second pass: iterate backwards to compute inverses
362    for (f, s) in v.iter_mut()
363        // Backwards
364        .rev()
365        // Ignore normalized elements
366        .filter(|f| !f.is_zero())
367        // Backwards, skip last element, fill in one for last term.
368        .zip(prod.into_iter().rev().skip(1).chain(Some(F::one())))
369    {
370        // tmp := tmp * f; f := tmp * s = 1/f
371        let new_tmp = tmp * *f;
372        *f = tmp * &s;
373        tmp = new_tmp;
374    }
375}
376
377#[cfg(all(test, feature = "std"))]
378mod std_tests {
379    use crate::BitIteratorLE;
380
381    #[test]
382    fn bit_iterator_le() {
383        let bits = BitIteratorLE::new(&[0, 1 << 10]).collect::<Vec<_>>();
384        dbg!(&bits);
385        assert!(bits[74]);
386        for (i, bit) in bits.into_iter().enumerate() {
387            if i != 74 {
388                assert!(!bit)
389            } else {
390                assert!(bit)
391            }
392        }
393    }
394}
395
396#[cfg(test)]
397mod no_std_tests {
398    use super::*;
399    use ark_std::{str::FromStr, test_rng};
400    use num_bigint::*;
401
402    // TODO: only Fr & FrConfig should need to be imported.
403    // The rest of imports are caused by cargo not resolving the deps properly
404    // from this crate and from ark_test_curves
405    use ark_test_curves::{batch_inversion, batch_inversion_and_mul, bls12_381::Fr, PrimeField};
406
407    #[test]
408    fn test_batch_inversion() {
409        let mut random_coeffs = Vec::<Fr>::new();
410        let vec_size = 1000;
411
412        for _ in 0..=vec_size {
413            random_coeffs.push(Fr::rand(&mut test_rng()));
414        }
415
416        let mut random_coeffs_inv = random_coeffs.clone();
417        batch_inversion::<Fr>(&mut random_coeffs_inv);
418        for i in 0..=vec_size {
419            assert_eq!(random_coeffs_inv[i] * random_coeffs[i], Fr::one());
420        }
421        let rand_multiplier = Fr::rand(&mut test_rng());
422        let mut random_coeffs_inv_shifted = random_coeffs.clone();
423        batch_inversion_and_mul(&mut random_coeffs_inv_shifted, &rand_multiplier);
424        for i in 0..=vec_size {
425            assert_eq!(
426                random_coeffs_inv_shifted[i] * random_coeffs[i],
427                rand_multiplier
428            );
429        }
430    }
431
432    #[test]
433    fn test_from_into_biguint() {
434        let mut rng = ark_std::test_rng();
435
436        let modulus_bits = Fr::MODULUS_BIT_SIZE;
437        let modulus: num_bigint::BigUint = Fr::MODULUS.into();
438
439        let mut rand_bytes = Vec::new();
440        for _ in 0..(2 * modulus_bits / 8) {
441            rand_bytes.push(u8::rand(&mut rng));
442        }
443
444        let rand = BigUint::from_bytes_le(&rand_bytes);
445
446        let a: BigUint = Fr::from(rand.clone()).into();
447        let b = rand % modulus;
448
449        assert_eq!(a, b);
450    }
451
452    #[test]
453    fn test_from_be_bytes_mod_order() {
454        // Each test vector is a byte array,
455        // and its tested by parsing it with from_bytes_mod_order, and the num-bigint
456        // library. The bytes are currently generated from scripts/test_vectors.py.
457        // TODO: Eventually generate all the test vector bytes via computation with the
458        // modulus
459        use ark_std::{rand::Rng, string::ToString};
460        use ark_test_curves::BigInteger;
461        use num_bigint::BigUint;
462
463        let ref_modulus = BigUint::from_bytes_be(&Fr::MODULUS.to_bytes_be());
464
465        let mut test_vectors = vec![
466            // 0
467            vec![0u8],
468            // 1
469            vec![1u8],
470            // 255
471            vec![255u8],
472            // 256
473            vec![1u8, 0u8],
474            // 65791
475            vec![1u8, 0u8, 255u8],
476            // 204827637402836681560342736360101429053478720705186085244545541796635082752
477            vec![
478                115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
479                161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
480                255u8, 255u8, 255u8, 0u8, 0u8, 0u8,
481            ],
482            // 204827637402836681560342736360101429053478720705186085244545541796635082753
483            vec![
484                115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
485                161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
486                255u8, 255u8, 255u8, 0u8, 0u8, 1u8,
487            ],
488            // 52435875175126190479447740508185965837690552500527637822603658699938581184512
489            vec![
490                115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
491                161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
492                255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 0u8,
493            ],
494            // 52435875175126190479447740508185965837690552500527637822603658699938581184513
495            vec![
496                115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
497                161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
498                255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 1u8,
499            ],
500            // 52435875175126190479447740508185965837690552500527637822603658699938581184514
501            vec![
502                115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
503                161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
504                255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 2u8,
505            ],
506            // 104871750350252380958895481016371931675381105001055275645207317399877162369026
507            vec![
508                231u8, 219u8, 78u8, 166u8, 83u8, 58u8, 250u8, 144u8, 102u8, 115u8, 176u8, 16u8,
509                19u8, 67u8, 176u8, 10u8, 167u8, 123u8, 72u8, 5u8, 255u8, 252u8, 183u8, 253u8,
510                255u8, 255u8, 255u8, 254u8, 0u8, 0u8, 0u8, 2u8,
511            ],
512            // 13423584044832304762738621570095607254448781440135075282586536627184276783235328
513            vec![
514                115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
515                161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
516                255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 1u8, 0u8,
517            ],
518            // 115792089237316195423570985008687907853269984665640564039457584007913129639953
519            vec![
520                1u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8,
521                0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8,
522                17u8,
523            ],
524            // 168227964412442385903018725516873873690960537166168201862061242707851710824468
525            vec![
526                1u8, 115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8,
527                9u8, 161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
528                255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 20u8,
529            ],
530            // 29695210719928072218913619902732290376274806626904512031923745164725699769008210
531            vec![
532                1u8, 0u8, 115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8,
533                8u8, 9u8, 161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8,
534                255u8, 255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 82u8,
535            ],
536        ];
537        // Add random bytestrings to the test vector list
538        for i in 1..512 {
539            let mut rng = test_rng();
540            let data: Vec<u8> = (0..i).map(|_| rng.gen()).collect();
541            test_vectors.push(data);
542        }
543        for i in test_vectors {
544            let mut expected_biguint = BigUint::from_bytes_be(&i);
545            // Reduce expected_biguint using modpow API
546            expected_biguint =
547                expected_biguint.modpow(&BigUint::from_bytes_be(&[1u8]), &ref_modulus);
548            let expected_string = expected_biguint.to_string();
549            let expected = Fr::from_str(&expected_string).unwrap();
550            let actual = Fr::from_be_bytes_mod_order(&i);
551            assert_eq!(expected, actual, "failed on test {:?}", i);
552        }
553    }
554}
ark_ff/fields/mod.rs

ark_ff/fields/
mod.rs
