binius_field/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 111 112 113 114 115 116 117 118 119
// Copyright 2024 Ulvetanna Inc.
use crate::{
arithmetic_traits::{InvertOrZero, Square},
as_packed_field::PackScalar,
underlier::WithUnderlier,
};
use rand::RngCore;
use std::{
fmt::{Debug, Display},
iter::{Product, Sum},
ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
};
/// This trait is based on `ff::Field` with some unused functionality removed.
pub trait Field:
Sized
+ Eq
+ Copy
+ Clone
+ Default
+ Send
+ Sync
+ Debug
+ Display
+ 'static
+ Neg<Output = Self>
+ Add<Output = Self>
+ Sub<Output = Self>
+ Mul<Output = Self>
+ Sum
+ Product
+ for<'a> Add<&'a Self, Output = Self>
+ for<'a> Sub<&'a Self, Output = Self>
+ for<'a> Mul<&'a Self, Output = Self>
+ for<'a> Sum<&'a Self>
+ for<'a> Product<&'a Self>
+ AddAssign
+ SubAssign
+ MulAssign
+ for<'a> AddAssign<&'a Self>
+ for<'a> SubAssign<&'a Self>
+ for<'a> MulAssign<&'a Self>
+ Square
+ InvertOrZero
// `Underlier: PackScalar<Self>` is an obvious property but it can't be deduced by the compiler so we are id here.
+ WithUnderlier<Underlier: PackScalar<Self>>
{
/// The zero element of the field, the additive identity.
const ZERO: Self;
/// The one element of the field, the multiplicative identity.
const ONE: Self;
/// Returns an element chosen uniformly at random using a user-provided RNG.
fn random(rng: impl RngCore) -> Self;
/// Returns true iff this element is zero.
fn is_zero(&self) -> bool {
*self == Self::ZERO
}
/// Doubles this element.
#[must_use]
fn double(&self) -> Self;
/// Computes the multiplicative inverse of this element,
/// failing if the element is zero.
fn invert(&self) -> Option<Self> {
let inv = self.invert_or_zero();
(!inv.is_zero()).then_some(inv)
}
/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
/// exponent.
///
/// # Guarantees
///
/// This operation is constant time with respect to `self`, for all exponents with the
/// same number of digits (`exp.as_ref().len()`). It is variable time with respect to
/// the number of digits in the exponent.
fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
let mut res = Self::ONE;
for e in exp.as_ref().iter().rev() {
for i in (0..64).rev() {
res = res.square();
let mut tmp = res;
tmp *= self;
if ((*e >> i) & 1) != 0 {
res = tmp;
}
}
}
res
}
/// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
/// exponent.
///
/// # Guarantees
///
/// **This operation is variable time with respect to `self`, for all exponent.** If
/// the exponent is fixed, this operation is effectively constant time. However, for
/// stronger constant-time guarantees, [`Field::pow`] should be used.
fn pow_vartime<S: AsRef<[u64]>>(&self, exp: S) -> Self {
let mut res = Self::ONE;
for e in exp.as_ref().iter().rev() {
for i in (0..64).rev() {
res = res.square();
if ((*e >> i) & 1) == 1 {
res.mul_assign(self);
}
}
}
res
}
}