Module fp_ext 

Prime-field extension towers and related helper traits. Generic extension field $\mathbb{F}_{p^M} = \mathbb{F}_p[x] / (f(x))$.

Overview

Given a prime $p$ and a monic irreducible polynomial $f$ of degree $M$ over $\mathbb{F}_{p}$, the extension field $\mathbb{F}_{{p^M}} = \mathbb{F}_p[x] / (f(x))$ is the set of polynomials of degree $M$ with coefficients in $\mathbb{F}_p$, where arithmetic is done modulo $f$.

This module provides a single generic type [FpExt<MOD, LIMBS, M, N, P, TSCONTS>] that covers any such extension. The irreducible polynomial is supplied via the zero-size marker trait [IrreduciblePoly].

Example

use crypto_bigint::{const_prime_monty_params, Uint};
use fp::field_ops::FieldOps;
use fp::fp_element::FpElement;
use fp::fp_ext::{FpExt, IrreduciblePoly, TonelliShanksConstants};

/* Setup the underlying prime field */
const_prime_monty_params!(Fp19Mod, Uint<1>, "0000000000000013", 2);
type Fp19 = FpElement<Fp19Mod, 1>;

fn fp(n: u64) -> Fp19 {
   Fp19::from_u64(n)
}

/* Setput the irreducible polynomial */
struct QuadPoly;
impl IrreduciblePoly<Fp19Mod, 1, 2> for QuadPoly {
    fn modulus() -> [Fp19; 2] {
        [Fp19::one(), Fp19::zero()]
    }
}

/* Setup the Tonelli--Shanks constants */
struct TSQuad;
impl TonelliShanksConstants<Fp19Mod, 1, 2, 1> for TSQuad {
    // p^2 - 1
    const ORDER: Uint<1> = Uint::<1>::from_u64(360);
    // (p^2 - 1) / 2
    const HALF_ORDER: Uint<1> = Uint::<1>::from_u64(180);
    // p^2 - 1 = 2^S * T with T odd
    const S: u64 = 3;
    const T: Uint<1> = Uint::<1>::from_u64(45);
    // (T - 1) / 2
    const PROJENATOR_EXP: Uint<1> = Uint::<1>::from_u64(22);
    // 2^(S - 1)
    const TWOSM1: Uint<1> = Uint::<1>::from_u64(4);
    // 2^S root of unity
    fn root_of_unity() -> [FpElement<Fp19Mod, 1>; 2] {
        [Fp19::from_u64(3), Fp19::from_u64(3)]
    }
}

/* Define the extension field */
type F19_2 = FpExt<Fp19Mod, 1, 2, 1, QuadPoly, TSQuad>;

/* Some standard tests */
let a = F19_2::new([fp(3), fp(2)]);
let ainv = F19_2::new([fp(9), fp(13)]);
let asquare = F19_2::new([fp(5), fp(12)]);
assert_eq!(a.invert().unwrap(), ainv);
assert_eq!(a.square(), asquare);
assert_eq!(asquare.sqrt().unwrap().square(), asquare);

Representation

An element $a \in \mathbb{F}_{p^M}$ is stored as exactly $M$ base-field coefficients so that coeffs = [a_0, a_1, ..., a_{M-1}] cooresponds to $$ a_0 + a_1 x + … + a_{M-1}x^{M-1} \pmod{ f(x) } $$

Operations and costs

Operation	Algorithm	Base-field cost
Add / Sub	Coefficient-wise	$M$ adds
Negate	Coefficient-wise	$M$ negs
Double	Coefficient-wise	$M$ doubles
Multiply	Schoolbook + reduction mod f	$M^2$ muls + $M^2$ adds
Square	Same as multiply (self * self)	$M^2$ muls + $M^2$ adds
Invert	Polynomial extended GCD	$O(M^2)$
Frobenius	self^p via square-and-multiply	$O(M^2 \log p)$
Norm	Product of M Galois conjugates	$O(M^3 \log p)$
Trace	Sum of M Galois conjugates	$O(M^2 \log p)$

Structs

FpExt

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

Traits

IrreduciblePoly

Supplies the monic irreducible polynomial $$f(x) = x^M + c_{M-1} x^{M-1} + … + c_1 x + c_0$$ that defines the extension $\mathbb{F}_p^M = \mathbb{F}_p[x] / (f(x))$.

TonelliShanksConstants

Supplies the constants for Tonelli–Shanks algorithm.