snarkvm_fields/traits/
prime_field.rs

1// Copyright 2024 Aleo Network Foundation
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use crate::{FftField, FieldError, FieldParameters, PoseidonDefaultField};
17use snarkvm_utilities::{biginteger::BigInteger, cmp::min, str::FromStr};
18
19/// The interface for a prime field.
20pub trait PrimeField:
21    FftField<FftParameters = <Self as PrimeField>::Parameters> + PoseidonDefaultField + FromStr<Err = FieldError>
22{
23    /// Returns the field size in bits.
24    const SIZE_IN_BITS: usize = Self::Parameters::MODULUS_BITS as usize;
25    /// Returns the field capacity for data bits.
26    const SIZE_IN_DATA_BITS: usize = Self::Parameters::CAPACITY as usize;
27
28    type Parameters: FieldParameters<BigInteger = Self::BigInteger>;
29    type BigInteger: BigInteger;
30
31    /// Constructs a `PrimeField` element given a human-readable `Self::BigInteger`.
32    fn from_bigint(repr: Self::BigInteger) -> Option<Self>;
33
34    /// Returns a human-readable `Self::BigInteger` in the range `0..(Self::MODULUS - 1)`.
35    fn to_bigint(&self) -> Self::BigInteger;
36
37    /// Returns the decomposition of the scalar.
38    fn decompose(
39        &self,
40        q1: &[u64; 4],
41        q2: &[u64; 4],
42        b1: Self,
43        b2: Self,
44        r128: Self,
45        half_r: &[u64; 8],
46    ) -> (Self, Self, bool, bool);
47
48    /// Returns the field size in bits.
49    fn size_in_bits() -> usize {
50        Self::Parameters::MODULUS_BITS as usize
51    }
52
53    /// Returns the capacity size for data bits.
54    fn size_in_data_bits() -> usize {
55        Self::Parameters::CAPACITY as usize
56    }
57
58    /// Returns the modulus.
59    fn modulus() -> Self::BigInteger {
60        Self::Parameters::MODULUS
61    }
62
63    /// Returns the modulus minus one divided by two.
64    fn modulus_minus_one_div_two() -> Self::BigInteger {
65        Self::Parameters::MODULUS_MINUS_ONE_DIV_TWO
66    }
67
68    /// Returns the trace.
69    fn trace() -> Self::BigInteger {
70        Self::Parameters::T
71    }
72
73    /// Returns the trace minus one divided by two.
74    fn trace_minus_one_div_two() -> Self::BigInteger {
75        Self::Parameters::T_MINUS_ONE_DIV_TWO
76    }
77
78    /// Reads bytes in big-endian, and converts them to a field element.
79    /// If the bytes are larger than the modulus, it will reduce them.
80    fn from_bytes_be_mod_order(bytes: &[u8]) -> Self {
81        let num_modulus_bytes = ((Self::Parameters::MODULUS_BITS + 7) / 8) as usize;
82        let num_bytes_to_directly_convert = min(num_modulus_bytes - 1, bytes.len());
83        let (leading_bytes, remaining_bytes) = bytes.split_at(num_bytes_to_directly_convert);
84        // Copy the leading big-endian bytes directly into a field element.
85        // The number of bytes directly converted must be less than the
86        // number of bytes needed to represent the modulus, as we must begin
87        // modular reduction once the data is of the same number of bytes as the modulus.
88        let mut bytes_to_directly_convert = leading_bytes.to_vec();
89        bytes_to_directly_convert.reverse();
90        // Guaranteed to not be None, as the input is less than the modulus size.
91        let mut res = Self::from_random_bytes(&bytes_to_directly_convert).unwrap();
92
93        // Update the result, byte by byte.
94        // We go through existing field arithmetic, which handles the reduction.
95        let window_size = Self::from(256u64);
96        for byte in remaining_bytes {
97            res *= window_size;
98            res += Self::from(*byte);
99        }
100        res
101    }
102
103    /// Reads bytes in little-endian, and converts them to a field element.
104    /// If the bytes are larger than the modulus, it will reduce them.
105    fn from_bytes_le_mod_order(bytes: &[u8]) -> Self {
106        let mut bytes_copy = bytes.to_vec();
107        bytes_copy.reverse();
108        Self::from_bytes_be_mod_order(&bytes_copy)
109    }
110}
snarkvm_fields/traits/prime_field.rs

snarkvm_fields/traits/
prime_field.rs
