snarkvm_fields/traits/
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::{One, PrimeField, Zero};
17use snarkvm_utilities::{
18    FromBytes,
19    ToBits,
20    ToBytes,
21    bititerator::BitIteratorBE,
22    rand::Uniform,
23    serialize::{
24        CanonicalDeserialize,
25        CanonicalDeserializeWithFlags,
26        CanonicalSerialize,
27        CanonicalSerializeWithFlags,
28        EmptyFlags,
29        Flags,
30    },
31};
32
33use std::{
34    fmt::{Debug, Display},
35    hash::Hash,
36    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
37};
38
39use serde::{Deserialize, Serialize};
40
41/// The interface for a generic field.
42pub trait Field:
43    'static
44    + ToBits
45    + ToBytes
46    + FromBytes
47    + Copy
48    + Clone
49    + Debug
50    + Display
51    + Default
52    + Send
53    + Sync
54    + Eq
55    + One
56    + Ord
57    + Neg<Output = Self>
58    + Uniform
59    + Zero
60    + Sized
61    + Hash
62    + From<u128>
63    + From<u64>
64    + From<u32>
65    + From<u16>
66    + From<u8>
67    + Add<Self, Output = Self>
68    + Sub<Self, Output = Self>
69    + Mul<Self, Output = Self>
70    + Div<Self, Output = Self>
71    + AddAssign<Self>
72    + SubAssign<Self>
73    + MulAssign<Self>
74    + DivAssign<Self>
75    + for<'a> Add<&'a Self, Output = Self>
76    + for<'a> Sub<&'a Self, Output = Self>
77    + for<'a> Mul<&'a Self, Output = Self>
78    + for<'a> Div<&'a Self, Output = Self>
79    + for<'a> AddAssign<&'a Self>
80    + for<'a> SubAssign<&'a Self>
81    + for<'a> MulAssign<&'a Self>
82    + for<'a> DivAssign<&'a Self>
83    + core::iter::Sum<Self>
84    + for<'a> core::iter::Sum<&'a Self>
85    + core::iter::Product<Self>
86    + for<'a> core::iter::Product<&'a Self>
87    + CanonicalSerialize
88    + CanonicalSerializeWithFlags
89    + CanonicalDeserialize
90    + CanonicalDeserializeWithFlags
91    + Serialize
92    + for<'a> Deserialize<'a>
93{
94    type BasePrimeField: PrimeField;
95
96    /// Constructs an element of `Self` from an element of the base
97    /// prime field.
98    fn from_base_prime_field(other: Self::BasePrimeField) -> Self;
99
100    /// Returns the constant 2^{-1}.
101    fn half() -> Self {
102        Self::from_base_prime_field(Self::BasePrimeField::half())
103    }
104
105    /// Returns the characteristic of the field.
106    fn characteristic<'a>() -> &'a [u64];
107
108    /// Returns `self + self`.
109    #[must_use]
110    fn double(&self) -> Self;
111
112    /// Doubles `self` in place.
113    fn double_in_place(&mut self);
114
115    /// Returns `self * self`.
116    #[must_use]
117    fn square(&self) -> Self;
118
119    /// Squares `self` in place.
120    fn square_in_place(&mut self) -> &mut Self;
121
122    fn sum_of_products<'a>(
123        a: impl Iterator<Item = &'a Self> + Clone,
124        b: impl Iterator<Item = &'a Self> + Clone,
125    ) -> Self {
126        a.zip(b).map(|(a, b)| *a * b).sum::<Self>()
127    }
128
129    /// Computes the multiplicative inverse of `self` if `self` is nonzero.
130    #[must_use]
131    fn inverse(&self) -> Option<Self>;
132
133    /// Sets `self` to `self`'s inverse if it exists. Otherwise it is a no-op.
134    fn inverse_in_place(&mut self) -> Option<&mut Self>;
135
136    /// Exponentiates this element by a power of the base prime modulus via
137    /// the Frobenius automorphism.
138    fn frobenius_map(&mut self, power: usize);
139
140    /// Exponentiates this element by a number represented with `u64` limbs,
141    /// least significant limb first.
142    #[must_use]
143    fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
144        let mut res = Self::one();
145
146        let mut found_one = false;
147
148        for i in BitIteratorBE::new(exp) {
149            if !found_one {
150                if i {
151                    found_one = true;
152                } else {
153                    continue;
154                }
155            }
156
157            res.square_in_place();
158
159            if i {
160                res *= self;
161            }
162        }
163        res
164    }
165
166    /// Returns a field element if the set of bytes forms a valid field element,
167    /// otherwise returns None. This function is primarily intended for sampling
168    /// random field elements from a hash-function or RNG output.
169    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
170        Self::from_random_bytes_with_flags::<EmptyFlags>(bytes).map(|f| f.0)
171    }
172
173    /// Returns a field element with an extra sign bit used for group parsing if
174    /// the set of bytes forms a valid field element, otherwise returns
175    /// None. This function is primarily intended for sampling
176    /// random field elements from a hash-function or RNG output.
177    fn from_random_bytes_with_flags<F: Flags>(bytes: &[u8]) -> Option<(Self, F)>;
178}
snarkvm_fields/traits/field.rs

snarkvm_fields/traits/
field.rs
