ark_ff/fields/
prime.rs

1use crate::{BigInteger, FftField, Field};
2
3use ark_std::{cmp::min, str::FromStr};
4use num_bigint::BigUint;
5
6/// The interface for a prime field, i.e. the field of integers modulo a prime $p$.  
7/// In the following example we'll use the prime field underlying the BLS12-381 G1 curve.
8/// ```rust
9/// use ark_ff::{BigInteger, Field, PrimeField};
10/// use ark_std::{test_rng, One, UniformRand, Zero};
11/// use ark_test_curves::bls12_381::Fq as F;
12///
13/// let mut rng = test_rng();
14/// let a = F::rand(&mut rng);
15/// // We can access the prime modulus associated with `F`:
16/// let modulus = <F as PrimeField>::MODULUS;
17/// assert_eq!(a.pow(&modulus), a); // the Euler-Fermat theorem tells us: a^{p-1} = 1 mod p
18///
19/// // We can convert field elements to integers in the range [0, MODULUS - 1]:
20/// let one: num_bigint::BigUint = F::one().into();
21/// assert_eq!(one, num_bigint::BigUint::one());
22///
23/// // We can construct field elements from an arbitrary sequence of bytes:
24/// let n = F::from_le_bytes_mod_order(&modulus.to_bytes_le());
25/// assert_eq!(n, F::zero());
26/// ```
27pub trait PrimeField:
28    Field<BasePrimeField = Self>
29    + FftField
30    + FromStr
31    + From<<Self as PrimeField>::BigInt>
32    + Into<<Self as PrimeField>::BigInt>
33    + From<BigUint>
34    + Into<BigUint>
35{
36    /// A `BigInteger` type that can represent elements of this field.
37    type BigInt: BigInteger;
38
39    /// The modulus `p`.
40    const MODULUS: Self::BigInt;
41
42    /// The value `(p - 1)/ 2`.
43    const MODULUS_MINUS_ONE_DIV_TWO: Self::BigInt;
44
45    /// The size of the modulus in bits.
46    const MODULUS_BIT_SIZE: u32;
47
48    /// The trace of the field is defined as the smallest integer `t` such that by
49    /// `2^s * t = p - 1`, and `t` is coprime to 2.
50    const TRACE: Self::BigInt;
51    /// The value `(t - 1)/ 2`.
52    const TRACE_MINUS_ONE_DIV_TWO: Self::BigInt;
53
54    /// Construct a prime field element from an integer in the range 0..(p - 1).
55    fn from_bigint(repr: Self::BigInt) -> Option<Self>;
56
57    /// Converts an element of the prime field into an integer in the range 0..(p - 1).
58    fn into_bigint(self) -> Self::BigInt;
59
60    /// Reads bytes in big-endian, and converts them to a field element.
61    /// If the integer represented by `bytes` is larger than the modulus `p`, this method
62    /// performs the appropriate reduction.
63    fn from_be_bytes_mod_order(bytes: &[u8]) -> Self {
64        let mut bytes_copy = bytes.to_vec();
65        bytes_copy.reverse();
66        Self::from_le_bytes_mod_order(&bytes_copy)
67    }
68
69    /// Reads bytes in little-endian, and converts them to a field element.
70    /// If the integer represented by `bytes` is larger than the modulus `p`, this method
71    /// performs the appropriate reduction.
72    fn from_le_bytes_mod_order(bytes: &[u8]) -> Self {
73        let num_modulus_bytes = ((Self::MODULUS_BIT_SIZE + 7) / 8) as usize;
74        let num_bytes_to_directly_convert = min(num_modulus_bytes - 1, bytes.len());
75        // Copy the leading little-endian bytes directly into a field element.
76        // The number of bytes directly converted must be less than the
77        // number of bytes needed to represent the modulus, as we must begin
78        // modular reduction once the data is of the same number of bytes as the
79        // modulus.
80        let (bytes, bytes_to_directly_convert) =
81            bytes.split_at(bytes.len() - num_bytes_to_directly_convert);
82        // Guaranteed to not be None, as the input is less than the modulus size.
83        let mut res = Self::from_random_bytes(&bytes_to_directly_convert).unwrap();
84
85        // Update the result, byte by byte.
86        // We go through existing field arithmetic, which handles the reduction.
87        // TODO: If we need higher speeds, parse more bytes at once, or implement
88        // modular multiplication by a u64
89        let window_size = Self::from(256u64);
90        for byte in bytes.iter().rev() {
91            res *= window_size;
92            res += Self::from(*byte);
93        }
94        res
95    }
96}
ark_ff/fields/prime.rs

ark_ff/fields/
prime.rs
