1  // Copyright (c) 2019-2025 Alpha-Delta Network Inc.
  2  // This file is part of the deltavm 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  
 16  use crate::{One, PrimeField, Zero};
 17  use deltavm_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  
 33  use std::{
 34      fmt::{Debug, Display},
 35      hash::Hash,
 36      ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
 37  };
 38  
 39  use serde::{Deserialize, Serialize};
 40  
 41  /// The interface for a generic field.
 42  pub 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  }