use crate::{
biginteger::BigInteger,
bytes::{FromBytes, ToBytes},
fields::utils::k_adicity,
UniformRand,
};
use ark_serialize::{
CanonicalDeserialize, CanonicalDeserializeWithFlags, CanonicalSerialize,
CanonicalSerializeWithFlags, EmptyFlags, Flags,
};
use ark_std::{
cmp::min,
fmt::{Debug, Display},
hash::Hash,
ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
str::FromStr,
vec::Vec,
};
pub use ark_ff_macros;
use num_traits::{One, Zero};
use zeroize::Zeroize;
#[macro_use]
pub mod macros;
pub mod utils;
#[macro_use]
pub mod arithmetic;
pub mod models;
pub use self::models::*;
#[cfg(feature = "parallel")]
use ark_std::cmp::max;
#[cfg(feature = "parallel")]
use rayon::prelude::*;
#[macro_export]
macro_rules! field_new {
($name:ident, $c0:expr) => {{
use $crate::FpParameters;
type Params = <$name as $crate::PrimeField>::Params;
let (is_positive, limbs) = $crate::ark_ff_macros::to_sign_and_limbs!($c0);
$name::const_from_str(
&limbs,
is_positive,
Params::R2,
Params::MODULUS,
Params::INV,
)
}};
($name:ident, $c0:expr, $c1:expr $(,)?) => {
$name {
c0: $c0,
c1: $c1,
_parameters: core::marker::PhantomData,
}
};
($name:ident, $c0:expr, $c1:expr, $c2:expr $(,)?) => {
$name {
c0: $c0,
c1: $c1,
c2: $c2,
_parameters: core::marker::PhantomData,
}
};
}
pub trait Field:
ToBytes
+ 'static
+ FromBytes
+ Copy
+ Clone
+ Debug
+ Display
+ Default
+ Send
+ Sync
+ Eq
+ Zero
+ One
+ Ord
+ Neg<Output = Self>
+ UniformRand
+ Zeroize
+ Sized
+ Hash
+ CanonicalSerialize
+ CanonicalSerializeWithFlags
+ CanonicalDeserialize
+ CanonicalDeserializeWithFlags
+ Add<Self, Output = Self>
+ Sub<Self, Output = Self>
+ Mul<Self, Output = Self>
+ Div<Self, Output = Self>
+ AddAssign<Self>
+ SubAssign<Self>
+ MulAssign<Self>
+ DivAssign<Self>
+ for<'a> Add<&'a Self, Output = Self>
+ for<'a> Sub<&'a Self, Output = Self>
+ for<'a> Mul<&'a Self, Output = Self>
+ for<'a> Div<&'a Self, Output = Self>
+ for<'a> AddAssign<&'a Self>
+ for<'a> SubAssign<&'a Self>
+ for<'a> MulAssign<&'a Self>
+ for<'a> DivAssign<&'a Self>
+ core::iter::Sum<Self>
+ for<'a> core::iter::Sum<&'a Self>
+ core::iter::Product<Self>
+ for<'a> core::iter::Product<&'a Self>
+ From<u128>
+ From<u64>
+ From<u32>
+ From<u16>
+ From<u8>
+ From<bool>
{
type BasePrimeField: PrimeField;
fn characteristic<'a>() -> &'a [u64] {
Self::BasePrimeField::characteristic()
}
fn extension_degree() -> u64;
fn from_base_prime_field_elems(elems: &[Self::BasePrimeField]) -> Option<Self>;
#[must_use]
fn double(&self) -> Self;
fn double_in_place(&mut self) -> &mut Self;
fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
Self::from_random_bytes_with_flags::<EmptyFlags>(bytes).map(|f| f.0)
}
fn from_random_bytes_with_flags<F: Flags>(bytes: &[u8]) -> Option<(Self, F)>;
#[must_use]
fn square(&self) -> Self;
fn square_in_place(&mut self) -> &mut Self;
#[must_use]
fn inverse(&self) -> Option<Self>;
fn inverse_in_place(&mut self) -> Option<&mut Self>;
fn frobenius_map(&mut self, power: usize);
#[must_use]
fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
let mut res = Self::one();
for i in BitIteratorBE::without_leading_zeros(exp) {
res.square_in_place();
if i {
res *= self;
}
}
res
}
#[inline]
fn pow_with_table<S: AsRef<[u64]>>(powers_of_2: &[Self], exp: S) -> Option<Self> {
let mut res = Self::one();
for (pow, bit) in BitIteratorLE::without_trailing_zeros(exp).enumerate() {
if bit {
res *= powers_of_2.get(pow)?;
}
}
Some(res)
}
}
pub trait FftParameters: 'static + Send + Sync + Sized {
type BigInt: BigInteger;
const TWO_ADICITY: u32;
const TWO_ADIC_ROOT_OF_UNITY: Self::BigInt;
const SMALL_SUBGROUP_BASE: Option<u32> = None;
const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None;
const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self::BigInt> = None;
}
pub trait FpParameters: FftParameters {
const MODULUS: Self::BigInt;
const MODULUS_BITS: u32;
const REPR_SHAVE_BITS: u32;
const R: Self::BigInt;
const R2: Self::BigInt;
const INV: u64;
const GENERATOR: Self::BigInt;
const CAPACITY: u32;
const T: Self::BigInt;
const T_MINUS_ONE_DIV_TWO: Self::BigInt;
const MODULUS_MINUS_ONE_DIV_TWO: Self::BigInt;
}
pub trait FftField: Field {
type FftParams: FftParameters;
fn two_adic_root_of_unity() -> Self;
fn large_subgroup_root_of_unity() -> Option<Self>;
fn multiplicative_generator() -> Self;
fn get_root_of_unity(n: usize) -> Option<Self> {
let mut omega: Self;
if let Some(large_subgroup_root_of_unity) = Self::large_subgroup_root_of_unity() {
let q = Self::FftParams::SMALL_SUBGROUP_BASE.expect(
"LARGE_SUBGROUP_ROOT_OF_UNITY should only be set in conjunction with SMALL_SUBGROUP_BASE",
) as usize;
let small_subgroup_base_adicity = Self::FftParams::SMALL_SUBGROUP_BASE_ADICITY.expect(
"LARGE_SUBGROUP_ROOT_OF_UNITY should only be set in conjunction with SMALL_SUBGROUP_BASE_ADICITY",
);
let q_adicity = k_adicity(q, n);
let q_part = q.pow(q_adicity);
let two_adicity = k_adicity(2, n);
let two_part = 1 << two_adicity;
if n != two_part * q_part
|| (two_adicity > Self::FftParams::TWO_ADICITY)
|| (q_adicity > small_subgroup_base_adicity)
{
return None;
}
omega = large_subgroup_root_of_unity;
for _ in q_adicity..small_subgroup_base_adicity {
omega = omega.pow(&[q as u64]);
}
for _ in two_adicity..Self::FftParams::TWO_ADICITY {
omega.square_in_place();
}
} else {
use core::convert::TryFrom;
let size = n.next_power_of_two() as u64;
let log_size_of_group = ark_std::log2(usize::try_from(size).expect("too large"));
if n != size as usize || log_size_of_group > Self::FftParams::TWO_ADICITY {
return None;
}
omega = Self::two_adic_root_of_unity();
for _ in log_size_of_group..Self::FftParams::TWO_ADICITY {
omega.square_in_place();
}
}
Some(omega)
}
}
pub trait PrimeField:
Field<BasePrimeField = Self>
+ FftField<FftParams = <Self as PrimeField>::Params>
+ FromStr
+ From<<Self as PrimeField>::BigInt>
+ Into<<Self as PrimeField>::BigInt>
{
type Params: FpParameters<BigInt = Self::BigInt>;
type BigInt: BigInteger;
fn from_repr(repr: Self::BigInt) -> Option<Self>;
fn into_repr(&self) -> Self::BigInt;
fn from_be_bytes_mod_order(bytes: &[u8]) -> Self {
let num_modulus_bytes = ((Self::Params::MODULUS_BITS + 7) / 8) as usize;
let num_bytes_to_directly_convert = min(num_modulus_bytes - 1, bytes.len());
let mut bytes_to_directly_convert = Vec::new();
bytes_to_directly_convert.extend(bytes[..num_bytes_to_directly_convert].iter().rev());
let mut res = Self::from_random_bytes(&bytes_to_directly_convert).unwrap();
let window_size = Self::from(256u64);
for byte in bytes[num_bytes_to_directly_convert..].iter() {
res *= window_size;
res += Self::from(*byte);
}
res
}
fn from_le_bytes_mod_order(bytes: &[u8]) -> Self {
let mut bytes_copy = bytes.to_vec();
bytes_copy.reverse();
Self::from_be_bytes_mod_order(&bytes_copy)
}
fn qnr_to_t() -> Self {
Self::two_adic_root_of_unity()
}
fn size_in_bits() -> usize {
Self::Params::MODULUS_BITS as usize
}
fn trace() -> Self::BigInt {
Self::Params::T
}
fn trace_minus_one_div_two() -> Self::BigInt {
Self::Params::T_MINUS_ONE_DIV_TWO
}
fn modulus_minus_one_div_two() -> Self::BigInt {
Self::Params::MODULUS_MINUS_ONE_DIV_TWO
}
}
pub trait SquareRootField: Field {
fn legendre(&self) -> LegendreSymbol;
#[must_use]
fn sqrt(&self) -> Option<Self>;
fn sqrt_in_place(&mut self) -> Option<&mut Self>;
}
#[derive(Debug, PartialEq)]
pub enum LegendreSymbol {
Zero = 0,
QuadraticResidue = 1,
QuadraticNonResidue = -1,
}
impl LegendreSymbol {
pub fn is_zero(&self) -> bool {
*self == LegendreSymbol::Zero
}
pub fn is_qnr(&self) -> bool {
*self == LegendreSymbol::QuadraticNonResidue
}
pub fn is_qr(&self) -> bool {
*self == LegendreSymbol::QuadraticResidue
}
}
#[derive(Debug)]
pub struct BitIteratorBE<Slice: AsRef<[u64]>> {
s: Slice,
n: usize,
}
impl<Slice: AsRef<[u64]>> BitIteratorBE<Slice> {
pub fn new(s: Slice) -> Self {
let n = s.as_ref().len() * 64;
BitIteratorBE { s, n }
}
pub fn without_leading_zeros(s: Slice) -> impl Iterator<Item = bool> {
Self::new(s).skip_while(|b| !b)
}
}
impl<Slice: AsRef<[u64]>> Iterator for BitIteratorBE<Slice> {
type Item = bool;
fn next(&mut self) -> Option<bool> {
if self.n == 0 {
None
} else {
self.n -= 1;
let part = self.n / 64;
let bit = self.n - (64 * part);
Some(self.s.as_ref()[part] & (1 << bit) > 0)
}
}
}
#[derive(Debug)]
pub struct BitIteratorLE<Slice: AsRef<[u64]>> {
s: Slice,
n: usize,
max_len: usize,
}
impl<Slice: AsRef<[u64]>> BitIteratorLE<Slice> {
pub fn new(s: Slice) -> Self {
let n = 0;
let max_len = s.as_ref().len() * 64;
BitIteratorLE { s, n, max_len }
}
pub fn without_trailing_zeros(s: Slice) -> impl Iterator<Item = bool> {
let mut first_trailing_zero = 0;
for (i, limb) in s.as_ref().iter().enumerate().rev() {
first_trailing_zero = i * 64 + (64 - limb.leading_zeros()) as usize;
if *limb != 0 {
break;
}
}
let mut iter = Self::new(s);
iter.max_len = first_trailing_zero;
iter
}
}
impl<Slice: AsRef<[u64]>> Iterator for BitIteratorLE<Slice> {
type Item = bool;
fn next(&mut self) -> Option<bool> {
if self.n == self.max_len {
None
} else {
let part = self.n / 64;
let bit = self.n - (64 * part);
self.n += 1;
Some(self.s.as_ref()[part] & (1 << bit) > 0)
}
}
}
use crate::biginteger::{
BigInteger256, BigInteger320, BigInteger384, BigInteger64, BigInteger768, BigInteger832,
};
impl_field_bigint_conv!(Fp64, BigInteger64, Fp64Parameters);
impl_field_bigint_conv!(Fp256, BigInteger256, Fp256Parameters);
impl_field_bigint_conv!(Fp320, BigInteger320, Fp320Parameters);
impl_field_bigint_conv!(Fp384, BigInteger384, Fp384Parameters);
impl_field_bigint_conv!(Fp768, BigInteger768, Fp768Parameters);
impl_field_bigint_conv!(Fp832, BigInteger832, Fp832Parameters);
pub fn batch_inversion<F: Field>(v: &mut [F]) {
batch_inversion_and_mul(v, &F::one());
}
#[cfg(not(feature = "parallel"))]
pub fn batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
serial_batch_inversion_and_mul(v, coeff);
}
#[cfg(feature = "parallel")]
pub fn batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
let min_elements_per_thread = 1;
let num_cpus_available = rayon::current_num_threads();
let num_elems = v.len();
let num_elem_per_thread = max(num_elems / num_cpus_available, min_elements_per_thread);
v.par_chunks_mut(num_elem_per_thread).for_each(|mut chunk| {
serial_batch_inversion_and_mul(&mut chunk, coeff);
});
}
fn serial_batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
let mut prod = Vec::with_capacity(v.len());
let mut tmp = F::one();
for f in v.iter().filter(|f| !f.is_zero()) {
tmp.mul_assign(f);
prod.push(tmp);
}
tmp = tmp.inverse().unwrap();
tmp = tmp * coeff;
for (f, s) in v.iter_mut()
.rev()
.filter(|f| !f.is_zero())
.zip(prod.into_iter().rev().skip(1).chain(Some(F::one())))
{
let new_tmp = tmp * *f;
*f = tmp * &s;
tmp = new_tmp;
}
}
#[cfg(all(test, feature = "std"))]
mod std_tests {
use super::BitIteratorLE;
#[test]
fn bit_iterator_le() {
let bits = BitIteratorLE::new(&[0, 1 << 10]).collect::<Vec<_>>();
dbg!(&bits);
assert!(bits[74]);
for (i, bit) in bits.into_iter().enumerate() {
if i != 74 {
assert!(!bit)
} else {
assert!(bit)
}
}
}
}
#[cfg(test)]
mod no_std_tests {
use super::*;
use crate::test_field::Fr;
use ark_std::test_rng;
#[test]
fn test_batch_inversion() {
let mut random_coeffs = Vec::<Fr>::new();
let vec_size = 1000;
for _ in 0..=vec_size {
random_coeffs.push(Fr::rand(&mut test_rng()));
}
let mut random_coeffs_inv = random_coeffs.clone();
batch_inversion::<Fr>(&mut random_coeffs_inv);
for i in 0..=vec_size {
assert_eq!(random_coeffs_inv[i] * random_coeffs[i], Fr::one());
}
let rand_multiplier = Fr::rand(&mut test_rng());
let mut random_coeffs_inv_shifted = random_coeffs.clone();
batch_inversion_and_mul(&mut random_coeffs_inv_shifted, &rand_multiplier);
for i in 0..=vec_size {
assert_eq!(
random_coeffs_inv_shifted[i] * random_coeffs[i],
rand_multiplier
);
}
}
#[test]
fn test_from_be_bytes_mod_order() {
use ark_std::rand::Rng;
use ark_std::string::ToString;
use num_bigint::BigUint;
let ref_modulus =
BigUint::from_bytes_be(&<Fr as PrimeField>::Params::MODULUS.to_bytes_be());
let mut test_vectors = vec![
vec![0u8],
vec![1u8],
vec![255u8],
vec![1u8, 0u8],
vec![1u8, 0u8, 255u8],
vec![
115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
255u8, 255u8, 255u8, 0u8, 0u8, 0u8,
],
vec![
115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
255u8, 255u8, 255u8, 0u8, 0u8, 1u8,
],
vec![
115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 0u8,
],
vec![
115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 1u8,
],
vec![
115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 2u8,
],
vec![
231u8, 219u8, 78u8, 166u8, 83u8, 58u8, 250u8, 144u8, 102u8, 115u8, 176u8, 16u8,
19u8, 67u8, 176u8, 10u8, 167u8, 123u8, 72u8, 5u8, 255u8, 252u8, 183u8, 253u8,
255u8, 255u8, 255u8, 254u8, 0u8, 0u8, 0u8, 2u8,
],
vec![
115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8, 9u8,
161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 1u8, 0u8,
],
vec![
1u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8,
0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8,
17u8,
],
vec![
1u8, 115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8, 8u8,
9u8, 161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8, 255u8,
255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 20u8,
],
vec![
1u8, 0u8, 115u8, 237u8, 167u8, 83u8, 41u8, 157u8, 125u8, 72u8, 51u8, 57u8, 216u8,
8u8, 9u8, 161u8, 216u8, 5u8, 83u8, 189u8, 164u8, 2u8, 255u8, 254u8, 91u8, 254u8,
255u8, 255u8, 255u8, 255u8, 0u8, 0u8, 0u8, 82u8,
],
];
for i in 1..512 {
let mut rng = test_rng();
let data: Vec<u8> = (0..i).map(|_| rng.gen()).collect();
test_vectors.push(data);
}
for i in test_vectors {
let mut expected_biguint = BigUint::from_bytes_be(&i);
expected_biguint =
expected_biguint.modpow(&BigUint::from_bytes_be(&[1u8]), &ref_modulus);
let expected_string = expected_biguint.to_string();
let expected = Fr::from_str(&expected_string).unwrap();
let actual = Fr::from_be_bytes_mod_order(&i);
assert_eq!(expected, actual, "failed on test {:?}", i);
}
}
}