snarkvm_fields/traits/
prime_field.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// Copyright 2024 Aleo Network Foundation
// This file is part of the snarkVM library.

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at:

// http://www.apache.org/licenses/LICENSE-2.0

// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

use crate::{FftField, FieldError, FieldParameters, PoseidonDefaultField};
use snarkvm_utilities::{biginteger::BigInteger, cmp::min, str::FromStr};

/// The interface for a prime field.
pub trait PrimeField:
    FftField<FftParameters = <Self as PrimeField>::Parameters> + PoseidonDefaultField + FromStr<Err = FieldError>
{
    /// Returns the field size in bits.
    const SIZE_IN_BITS: usize = Self::Parameters::MODULUS_BITS as usize;
    /// Returns the field capacity for data bits.
    const SIZE_IN_DATA_BITS: usize = Self::Parameters::CAPACITY as usize;

    type Parameters: FieldParameters<BigInteger = Self::BigInteger>;
    type BigInteger: BigInteger;

    /// Constructs a `PrimeField` element given a human-readable `Self::BigInteger`.
    fn from_bigint(repr: Self::BigInteger) -> Option<Self>;

    /// Returns a human-readable `Self::BigInteger` in the range `0..(Self::MODULUS - 1)`.
    fn to_bigint(&self) -> Self::BigInteger;

    /// Returns the decomposition of the scalar.
    fn decompose(
        &self,
        q1: &[u64; 4],
        q2: &[u64; 4],
        b1: Self,
        b2: Self,
        r128: Self,
        half_r: &[u64; 8],
    ) -> (Self, Self, bool, bool);

    /// Returns the field size in bits.
    fn size_in_bits() -> usize {
        Self::Parameters::MODULUS_BITS as usize
    }

    /// Returns the capacity size for data bits.
    fn size_in_data_bits() -> usize {
        Self::Parameters::CAPACITY as usize
    }

    /// Returns the modulus.
    fn modulus() -> Self::BigInteger {
        Self::Parameters::MODULUS
    }

    /// Returns the modulus minus one divided by two.
    fn modulus_minus_one_div_two() -> Self::BigInteger {
        Self::Parameters::MODULUS_MINUS_ONE_DIV_TWO
    }

    /// Returns the trace.
    fn trace() -> Self::BigInteger {
        Self::Parameters::T
    }

    /// Returns the trace minus one divided by two.
    fn trace_minus_one_div_two() -> Self::BigInteger {
        Self::Parameters::T_MINUS_ONE_DIV_TWO
    }

    /// Reads bytes in big-endian, and converts them to a field element.
    /// If the bytes are larger than the modulus, it will reduce them.
    fn from_bytes_be_mod_order(bytes: &[u8]) -> Self {
        let num_modulus_bytes = ((Self::Parameters::MODULUS_BITS + 7) / 8) as usize;
        let num_bytes_to_directly_convert = min(num_modulus_bytes - 1, bytes.len());
        let (leading_bytes, remaining_bytes) = bytes.split_at(num_bytes_to_directly_convert);
        // Copy the leading big-endian bytes directly into a field element.
        // The number of bytes directly converted must be less than the
        // number of bytes needed to represent the modulus, as we must begin
        // modular reduction once the data is of the same number of bytes as the modulus.
        let mut bytes_to_directly_convert = leading_bytes.to_vec();
        bytes_to_directly_convert.reverse();
        // Guaranteed to not be None, as the input is less than the modulus size.
        let mut res = Self::from_random_bytes(&bytes_to_directly_convert).unwrap();

        // Update the result, byte by byte.
        // We go through existing field arithmetic, which handles the reduction.
        let window_size = Self::from(256u64);
        for byte in remaining_bytes {
            res *= window_size;
            res += Self::from(*byte);
        }
        res
    }

    /// Reads bytes in little-endian, and converts them to a field element.
    /// If the bytes are larger than the modulus, it will reduce them.
    fn from_bytes_le_mod_order(bytes: &[u8]) -> Self {
        let mut bytes_copy = bytes.to_vec();
        bytes_copy.reverse();
        Self::from_bytes_be_mod_order(&bytes_copy)
    }
}