snarkvm_fields/traits/
prime_field.rs

1// Copyright (c) 2019-2025 Provable Inc.
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 std::{cmp::min, str::FromStr};
17
18use crate::{FftField, FieldError, FieldParameters, PoseidonDefaultField};
19use snarkvm_utilities::biginteger::BigInteger;
20
21/// The interface for a prime field.
22pub trait PrimeField:
23    FftField<FftParameters = <Self as PrimeField>::Parameters> + PoseidonDefaultField + FromStr<Err = FieldError>
24{
25    /// Returns the field size in bits.
26    const SIZE_IN_BITS: usize = Self::Parameters::MODULUS_BITS as usize;
27    /// Returns the field capacity for data bits.
28    const SIZE_IN_DATA_BITS: usize = Self::Parameters::CAPACITY as usize;
29
30    type Parameters: FieldParameters<BigInteger = Self::BigInteger>;
31    type BigInteger: BigInteger;
32
33    /// Constructs a `PrimeField` element given a human-readable `Self::BigInteger`.
34    fn from_bigint(repr: Self::BigInteger) -> Option<Self>;
35
36    /// Returns a human-readable `Self::BigInteger` in the range `0..(Self::MODULUS - 1)`.
37    fn to_bigint(&self) -> Self::BigInteger;
38
39    /// Returns the decomposition of the scalar.
40    fn decompose(
41        &self,
42        q1: &[u64; 4],
43        q2: &[u64; 4],
44        b1: Self,
45        b2: Self,
46        r128: Self,
47        half_r: &[u64; 8],
48    ) -> (Self, Self, bool, bool);
49
50    /// Returns the field size in bits.
51    fn size_in_bits() -> usize {
52        Self::Parameters::MODULUS_BITS as usize
53    }
54
55    /// Returns the capacity size for data bits.
56    fn size_in_data_bits() -> usize {
57        Self::Parameters::CAPACITY as usize
58    }
59
60    /// Returns the modulus.
61    fn modulus() -> Self::BigInteger {
62        Self::Parameters::MODULUS
63    }
64
65    /// Returns the modulus minus one divided by two.
66    fn modulus_minus_one_div_two() -> Self::BigInteger {
67        Self::Parameters::MODULUS_MINUS_ONE_DIV_TWO
68    }
69
70    /// Returns the trace.
71    fn trace() -> Self::BigInteger {
72        Self::Parameters::T
73    }
74
75    /// Returns the trace minus one divided by two.
76    fn trace_minus_one_div_two() -> Self::BigInteger {
77        Self::Parameters::T_MINUS_ONE_DIV_TWO
78    }
79
80    /// Reads bytes in big-endian, and converts them to a field element.
81    /// If the bytes are larger than the modulus, it will reduce them.
82    fn from_bytes_be_mod_order(bytes: &[u8]) -> Self {
83        let num_modulus_bytes = Self::Parameters::MODULUS_BITS.div_ceil(8) as usize;
84        let num_bytes_to_directly_convert = min(num_modulus_bytes - 1, bytes.len());
85        let (leading_bytes, remaining_bytes) = bytes.split_at(num_bytes_to_directly_convert);
86        // Copy the leading big-endian bytes directly into a field element.
87        // The number of bytes directly converted must be less than the
88        // number of bytes needed to represent the modulus, as we must begin
89        // modular reduction once the data is of the same number of bytes as the modulus.
90        let mut bytes_to_directly_convert = leading_bytes.to_vec();
91        bytes_to_directly_convert.reverse();
92        // Guaranteed to not be None, as the input is less than the modulus size.
93        let mut res = Self::from_random_bytes(&bytes_to_directly_convert).unwrap();
94
95        // Update the result, byte by byte.
96        // We go through existing field arithmetic, which handles the reduction.
97        let window_size = Self::from(256u64);
98        for byte in remaining_bytes {
99            res *= window_size;
100            res += Self::from(*byte);
101        }
102        res
103    }
104
105    /// Reads bytes in little-endian, and converts them to a field element.
106    /// If the bytes are larger than the modulus, it will reduce them.
107    fn from_bytes_le_mod_order(bytes: &[u8]) -> Self {
108        let mut bytes_copy = bytes.to_vec();
109        bytes_copy.reverse();
110        Self::from_bytes_be_mod_order(&bytes_copy)
111    }
112}
snarkvm_fields/traits/prime_field.rs

snarkvm_fields/traits/
prime_field.rs
