Struct FpExt 

pub struct FpExt<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS>
where
    MOD: ConstPrimeMontyParams<LIMBS>,
    P: IrreduciblePoly<MOD, LIMBS, M>,
    TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,
{
    pub coeffs: [FpElement<MOD, LIMBS>; M],
    /* private fields */
}

An element of the extension field $\mathbb{F}_{p^M} = \mathbb{F}_p[x] / (f(x))$.

P is a zero-size marker type implementing IrreduciblePoly. M is the extension degree (number of base-field coefficients stored). N is the number limbs needed to store p^M

Fields

coeffs: [FpElement<MOD, LIMBS>; M]

Coefficients in ascending degree, that is coeffs[i] is the coefficient of $x^i$ (zero indexed).

Implementations

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

pub fn new(coeffs: [FpElement<MOD, LIMBS>; M]) -> Self

Construct from a coefficient array [a_0, ..., a_{M-1}].

pub fn from_base(a: FpElement<MOD, LIMBS>) -> Self

Embed a base-field element as $a + 0x + … + 0x^{M-1}$.

pub fn coeff(&self, i: usize) -> &FpElement<MOD, LIMBS>

Return the coefficient of $x^i$.

Trait Implementations

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> Add for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

type Output = FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self

Performs the + operation.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> Clone for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> ConditionallySelectable for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self

Select a or b according to choice.

fn conditional_assign(&mut self, other: &Self, choice: Choice)

Conditionally assign other to self, according to choice.

fn conditional_swap(a: &mut Self, b: &mut Self, choice: Choice)

Conditionally swap self and other if choice == 1; otherwise, reassign both unto themselves.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> ConstantTimeEq for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

fn ct_eq(&self, other: &Self) -> Choice

Determine if two items are equal.

fn ct_ne(&self, other: &Self) -> Choice

Determine if two items are NOT equal.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> Debug for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>, FpElement<MOD, LIMBS>: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> Default for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

fn default() -> Self

Returns the “default value” for a type.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> Display for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>, FpElement<MOD, LIMBS>: Display,

Shows the element as $a_0 + a_1 x + a_2 x^2 + …$ with zero coefficients suppressed. The zero element prints as 0.

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> FieldFromRepr for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

type Repr = [FpElement<MOD, LIMBS>; M]

The representation type accepted by this field.

fn from_repr(x: Self::Repr) -> Self

Constructs a field element from the given representation.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> FieldOps for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

fn mul(&self, rhs: &Self) -> Self

Schoolbook multiplication followed by reduction modulo $f(x)$.

Product has degree $\leq 2M−2$, then each high-degree term is replaced using $x^M \equiv −\sum_j \texttt{modulus}[j] x^j$ until all degrees are below $M$.

fn invert(&self) -> CtOption<Self>

Inversion via polynomial extended GCD.

Finds $s$ such that $\texttt{self} \times s \equiv 1 \pmod{f}$ by computing $\gcd(\texttt{self}, f) = g$ (a nonzero constant if self is nonzero) and then returning $s g^{-1} \pmod{f}$.

fn frobenius(&self) -> Self

φ_p(a) = a^p — the p-power Frobenius endomorphism.

Computed via square-and-multiply using the characteristic p retrieved from the base field.

fn norm(&self) -> Self

N_{Fp^M/Fp}(a) = ∏_{i=0}^{M-1} φ_p^i(a) — product of all Galois conjugates.

The result lies in Fp (all higher coefficients are 0), but is returned embedded in Fp^M for uniformity with the FieldOps signature.

fn trace(&self) -> Self

Tr_{Fp^M/Fp}(a) = Σ_{i=0}^{M-1} φ_p^i(a) — sum of all Galois conjugates.

Like norm, the result lies in Fp but is returned embedded in Fp^M.

fn sqrt(&self) -> CtOption<Self>

Tonelli–Shanks squareroot algorithm

Implementation of the Tonelli–Shanks square root algorithm. Requires only a factorisation as $p^M - 1 = 2^K N$ so can compute this at compile time by truncating zeros.

Arguments

• &self - An element of Fp^M (type: &self)

Returns

self^(1/2) a choice of squareroot (type: Self)

fn inverse_and_sqrt(&self) -> (CtOption<Self>, CtOption<Self>)

Inverse and sqrt in one exponentiation

Computes the inverse and squareroot of self in one exponentiation using the tricks in Scott’s article

Arguments

• &self - An element of Fp^M (type: &self)

Returns

(myinv, mysqrt) which is self.invert() and self.sqrt() (type: CtOption<Self>, CtOption<Self>)

fn inv_sqrt(&self) -> CtOption<Self>

Inverse of squareroot of self in 1 exponentiation

Computes 1/sqrt(self) using the trick from Mike Scott’s “Tricks of the trade” article Section 2 https://eprint.iacr.org/2020/1497

Arguments

• &self - Description of &self (type: self)

Returns

The inverse of the squareroot of self (type: CtOption<Self>)

fn invertme_sqrtother(&self, rhs: &Self) -> (CtOption<Self>, CtOption<Self>)

Inverse of self and squareroot of rhs in 1 exponentiation

Computes 1/self and rhs.sqrt() simulaineously using the trick from Mike Scott’s “Tricks of the trade” article Section 2 https://eprint.iacr.org/2020/1497

Returns

The inverse of self and square root fo rhs. Theq former is none if and only if self is nonzero and the latter is not none if and only if there exists a squareroot of rhs in FpM (type: (CtOption<Self>, CtOption<Self>))

fn sqrt_ratio(&self, rhs: &Self) -> CtOption<Self>

Computes the squareroot of a ratio self/rhs

Computes sqrt(self/rhs) in one exponentiation using the trick from Mike Scott’s “Tricks of the trade” article Section 2 https://eprint.iacr.org/2020/1497

Arguments

• &self - Element of FpM (type: self)
• rhs - Element of FpM (type: &Self)

Returns

The squareroot of the ratio self/rhs is not none if and only if rhs is invertible and the ratio has an FpM squareroot (type: CtOption<Self>)

fn legendre(&self) -> i8

a is a QR in Fp^M iff a^{(p^M-1)/2} = 1.

Implements the “Legendre symbol” which is 1 if and only if we have a quadratic residue in FpM WARNING: Not constant time if self is zero

Arguments

• &self - Element of FpM (type: self)

Returns

Either 0 if &self is 0, 1 if &self is a QR or -1 if &self is not a QR. (type: i8)

fn degree() -> u32

Degree of Fp^M over the prime subfield Fp.

fn zero() -> Self

Create the constant zero

fn one() -> Self

Create the constant one

fn from_u64(x: u64) -> Self

Convert u64 to the field.

fn is_zero(&self) -> Choice

Check if element is zero

fn is_one(&self) -> Choice

Check if element is one

fn negate(&self) -> Self

Negate self to -self

fn add(&self, rhs: &Self) -> Self

Add rhs to self

fn sub(&self, rhs: &Self) -> Self

Sub rhs from self

fn square(&self) -> Self

Square self

fn double(&self) -> Self

Double self

fn characteristic() -> Vec<u64>

Returns the characteristic of the field.

fn div(&self, rhs: &Self) -> CtOption<Self>

Divide self by rhs

fn pow_vartime(&self, exp: &[u64]) -> Self

self^exp using square-and multiply (litte-endian bit order)

fn pow(&self, exp: &[u64]) -> Self

self^pow in constant time using a Montgomery ladder

fn frobenius_pow(&self, k: u32) -> Self

Compute self^{p^k} a power of the frobenius

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> FieldRandom for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

fn random(rng: &mut (impl CryptoRng + Rng)) -> Self

Sample a uniformly random element of Fp^M by drawing each coefficient independently from Fp.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> Mul for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

type Output = FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self

Performs the * operation.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> Neg for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

type Output = FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

The resulting type after applying the - operator.

fn neg(self) -> Self

Performs the unary - operation.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> PartialEq for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> Sub for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,

type Output = FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self

Performs the - operation.

impl<MOD, const LIMBS: usize, const M: usize, P, const N: usize, TSCONSTS> Copy for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>, [FpElement<MOD, LIMBS>; M]: Copy,

impl<MOD, const LIMBS: usize, const M: usize, const N: usize, P, TSCONSTS> Eq for FpExt<MOD, LIMBS, M, N, P, TSCONSTS>

where MOD: ConstPrimeMontyParams<LIMBS>, P: IrreduciblePoly<MOD, LIMBS, M>, TSCONSTS: TonelliShanksConstants<MOD, LIMBS, M, N>,