#![allow(clippy::assign_op_pattern, clippy::op_ref)]
#[cfg_attr(target_pointer_width = "32", path = "field/field32.rs")]
#[cfg_attr(target_pointer_width = "64", path = "field/field64.rs")]
mod field_impl;
use self::field_impl::*;
use crate::{FieldBytes, NistP256};
use core::{
fmt::{self, Debug},
iter::{Product, Sum},
ops::{AddAssign, Mul, MulAssign, Neg, SubAssign},
};
use elliptic_curve::{
bigint::U256,
ff::PrimeField,
subtle::{Choice, ConstantTimeEq, CtOption},
};
const MODULUS_HEX: &str = "ffffffff00000001000000000000000000000000ffffffffffffffffffffffff";
pub const MODULUS: U256 = U256::from_be_hex(MODULUS_HEX);
const R_2: U256 =
U256::from_be_hex("00000004fffffffdfffffffffffffffefffffffbffffffff0000000000000003");
#[derive(Clone, Copy)]
pub struct FieldElement(pub(crate) U256);
primeorder::impl_mont_field_element!(
NistP256,
FieldElement,
FieldBytes,
U256,
MODULUS,
Fe,
fe_from_montgomery,
fe_to_montgomery,
fe_add,
fe_sub,
fe_mul,
fe_neg,
fe_square
);
impl FieldElement {
pub fn invert(&self) -> CtOption<Self> {
CtOption::new(self.invert_unchecked(), !self.is_zero())
}
const fn invert_unchecked(&self) -> Self {
let t111 = self.multiply(&self.multiply(&self.square()).square());
let t111111 = t111.multiply(&t111.sqn(3));
let x15 = t111111.sqn(6).multiply(&t111111).sqn(3).multiply(&t111);
let x16 = x15.square().multiply(self);
let i53 = x16.sqn(16).multiply(&x16).sqn(15);
let x47 = x15.multiply(&i53);
x47.multiply(&i53.sqn(17).multiply(self).sqn(143).multiply(&x47).sqn(47))
.sqn(2)
.multiply(self)
}
pub fn sqrt(&self) -> CtOption<Self> {
let t11 = self.mul(&self.square());
let t1111 = t11.mul(&t11.sqn(2));
let t11111111 = t1111.mul(&t1111.sqn(4));
let x16 = t11111111.sqn(8).mul(&t11111111);
let sqrt = x16
.sqn(16)
.mul(&x16)
.sqn(32)
.mul(self)
.sqn(96)
.mul(self)
.sqn(94);
CtOption::new(
sqrt,
(&sqrt * &sqrt).ct_eq(self), )
}
const fn sqn(&self, n: usize) -> Self {
let mut x = *self;
let mut i = 0;
while i < n {
x = x.square();
i += 1;
}
x
}
}
impl PrimeField for FieldElement {
type Repr = FieldBytes;
const MODULUS: &'static str = MODULUS_HEX;
const NUM_BITS: u32 = 256;
const CAPACITY: u32 = 255;
const TWO_INV: Self = Self::from_u64(2).invert_unchecked();
const MULTIPLICATIVE_GENERATOR: Self = Self::from_u64(6);
const S: u32 = 1;
const ROOT_OF_UNITY: Self =
Self::from_hex("ffffffff00000001000000000000000000000000fffffffffffffffffffffffe");
const ROOT_OF_UNITY_INV: Self = Self::ROOT_OF_UNITY.invert_unchecked();
const DELTA: Self = Self::from_u64(36);
#[inline]
fn from_repr(bytes: FieldBytes) -> CtOption<Self> {
Self::from_bytes(&bytes)
}
#[inline]
fn to_repr(&self) -> FieldBytes {
self.to_bytes()
}
#[inline]
fn is_odd(&self) -> Choice {
self.is_odd()
}
}
impl Debug for FieldElement {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "FieldElement(0x{:X})", &self.0)
}
}
#[cfg(test)]
mod tests {
use super::FieldElement;
use crate::{test_vectors::field::DBL_TEST_VECTORS, FieldBytes};
use elliptic_curve::{bigint::U256, ff::PrimeField};
use primeorder::{
impl_field_identity_tests, impl_field_invert_tests, impl_field_sqrt_tests,
impl_primefield_tests,
};
use proptest::{num, prelude::*};
const T: [u64; 4] = [
0xffffffffffffffff,
0x000000007fffffff,
0x8000000000000000,
0x7fffffff80000000,
];
impl_field_identity_tests!(FieldElement);
impl_field_invert_tests!(FieldElement);
impl_field_sqrt_tests!(FieldElement);
impl_primefield_tests!(FieldElement, T);
#[test]
fn from_bytes() {
assert_eq!(
FieldElement::from_bytes(&FieldBytes::default()).unwrap(),
FieldElement::ZERO
);
assert_eq!(
FieldElement::from_bytes(
&[
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 1
]
.into()
)
.unwrap(),
FieldElement::ONE
);
assert!(bool::from(
FieldElement::from_bytes(&[0xff; 32].into()).is_none()
));
}
#[test]
fn to_bytes() {
assert_eq!(FieldElement::ZERO.to_bytes(), FieldBytes::default());
assert_eq!(
FieldElement::ONE.to_bytes(),
[
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1
]
.into()
);
}
#[test]
fn repeated_add() {
let mut r = FieldElement::ONE;
for i in 0..DBL_TEST_VECTORS.len() {
assert_eq!(r.to_bytes(), DBL_TEST_VECTORS[i].into());
r = r + &r;
}
}
#[test]
fn repeated_double() {
let mut r = FieldElement::ONE;
for i in 0..DBL_TEST_VECTORS.len() {
assert_eq!(r.to_bytes(), DBL_TEST_VECTORS[i].into());
r = r.double();
}
}
#[test]
fn repeated_mul() {
let mut r = FieldElement::ONE;
let two = r + &r;
for i in 0..DBL_TEST_VECTORS.len() {
assert_eq!(r.to_bytes(), DBL_TEST_VECTORS[i].into());
r = r * &two;
}
}
#[test]
fn negation() {
let two = FieldElement::ONE.double();
let neg_two = -two;
assert_eq!(two + &neg_two, FieldElement::ZERO);
assert_eq!(-neg_two, two);
}
#[test]
fn pow_vartime() {
let one = FieldElement::ONE;
let two = one + &one;
let four = two.square();
assert_eq!(two.pow_vartime(&[2, 0, 0, 0]), four);
}
proptest! {
#[cfg(target_pointer_width = "32")]
#[test]
fn add_then_sub(
a0 in num::u32::ANY,
a1 in num::u32::ANY,
a2 in num::u32::ANY,
a3 in num::u32::ANY,
a4 in num::u32::ANY,
a5 in num::u32::ANY,
a6 in num::u32::ANY,
b0 in num::u32::ANY,
b1 in num::u32::ANY,
b2 in num::u32::ANY,
b3 in num::u32::ANY,
b4 in num::u32::ANY,
b5 in num::u32::ANY,
b6 in num::u32::ANY,
) {
let a = FieldElement(U256::from_words([a0, a1, a2, a3, a4, a5, a6, 0]));
let b = FieldElement(U256::from_words([b0, b1, b2, b3, b4, b5, b6, 0]));
assert_eq!(a.add(&b).sub(&a), b);
}
#[cfg(target_pointer_width = "64")]
#[test]
fn add_then_sub(
a0 in num::u64::ANY,
a1 in num::u64::ANY,
a2 in num::u64::ANY,
b0 in num::u64::ANY,
b1 in num::u64::ANY,
b2 in num::u64::ANY,
) {
let a = FieldElement(U256::from_words([a0, a1, a2, 0]));
let b = FieldElement(U256::from_words([b0, b1, b2, 0]));
assert_eq!(a.add(&b).sub(&a), b);
}
}
}