Trait MontConfig

pub trait MontConfig<const N: usize>:
    'static
    + Sync
    + Send
    + Sized {
    const MODULUS: BigInt<N>;
    const GENERATOR: Fp<MontBackend<Self, N>, N>;
    const TWO_ADIC_ROOT_OF_UNITY: Fp<MontBackend<Self, N>, N>;
    const R: BigInt<N> = _;
    const R2: BigInt<N> = _;
    const INV: u64 = _;
    const SMALL_SUBGROUP_BASE: Option<u32> = None;
    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None;
    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Fp<MontBackend<Self, N>, N>> = None;
    const SQRT_PRECOMP: Option<SqrtPrecomputation<Fp<MontBackend<Self, N>, N>>> = _;

    // Provided methods
    fn add_assign(
        a: &mut Fp<MontBackend<Self, N>, N>,
        b: &Fp<MontBackend<Self, N>, N>,
    ) { ... }
    fn sub_assign(
        a: &mut Fp<MontBackend<Self, N>, N>,
        b: &Fp<MontBackend<Self, N>, N>,
    ) { ... }
    fn double_in_place(a: &mut Fp<MontBackend<Self, N>, N>) { ... }
    fn neg_in_place(a: &mut Fp<MontBackend<Self, N>, N>) { ... }
    fn mul_assign(
        a: &mut Fp<MontBackend<Self, N>, N>,
        b: &Fp<MontBackend<Self, N>, N>,
    ) { ... }
    fn square_in_place(a: &mut Fp<MontBackend<Self, N>, N>) { ... }
    fn inverse(
        a: &Fp<MontBackend<Self, N>, N>,
    ) -> Option<Fp<MontBackend<Self, N>, N>> { ... }
    fn from_bigint(r: BigInt<N>) -> Option<Fp<MontBackend<Self, N>, N>> { ... }
    fn into_bigint(a: Fp<MontBackend<Self, N>, N>) -> BigInt<N> { ... }
    fn sum_of_products<const M: usize>(
        a: &[Fp<MontBackend<Self, N>, N>; M],
        b: &[Fp<MontBackend<Self, N>, N>; M],
    ) -> Fp<MontBackend<Self, N>, N> { ... }
}

A trait that specifies the constants and arithmetic procedures for Montgomery arithmetic over the prime field defined by MODULUS.

Note

Manual implementation of this trait is not recommended unless one wishes to specialize arithmetic methods. Instead, the MontConfig derive macro should be used.

Required Associated Constants

const MODULUS: BigInt<N>

The modulus of the field.

const GENERATOR: Fp<MontBackend<Self, N>, N>

A multiplicative generator of the field. Self::GENERATOR is an element having multiplicative order Self::MODULUS - 1.

const TWO_ADIC_ROOT_OF_UNITY: Fp<MontBackend<Self, N>, N>

2^s root of unity computed by GENERATOR^t

Provided Associated Constants

const R: BigInt<N> = _

Let M be the power of 2^64 nearest to Self::MODULUS_BITS. Then R = M % Self::MODULUS.

const R2: BigInt<N> = _

R2 = R^2 % Self::MODULUS

const INV: u64 = _

INV = -MODULUS^{-1} mod 2^64

const SMALL_SUBGROUP_BASE: Option<u32> = None

An integer b such that there exists a multiplicative subgroup of size b^k for some integer k.

const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None

The integer k such that there exists a multiplicative subgroup of size Self::SMALL_SUBGROUP_BASE^k.

const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Fp<MontBackend<Self, N>, N>> = None

GENERATOR^((MODULUS-1) / (2^s * SMALL_SUBGROUP_BASE^SMALL_SUBGROUP_BASE_ADICITY)). Used for mixed-radix FFT.

const SQRT_PRECOMP: Option<SqrtPrecomputation<Fp<MontBackend<Self, N>, N>>> = _

Precomputed material for use when computing square roots. The default is to use the standard Tonelli-Shanks algorithm.

Provided Methods

fn add_assign( a: &mut Fp<MontBackend<Self, N>, N>, b: &Fp<MontBackend<Self, N>, N>, )

Sets a = a + b.

fn sub_assign( a: &mut Fp<MontBackend<Self, N>, N>, b: &Fp<MontBackend<Self, N>, N>, )

Sets a = a - b.

fn double_in_place(a: &mut Fp<MontBackend<Self, N>, N>)

Sets a = 2 * a.

fn neg_in_place(a: &mut Fp<MontBackend<Self, N>, N>)

Sets a = -a.

fn mul_assign( a: &mut Fp<MontBackend<Self, N>, N>, b: &Fp<MontBackend<Self, N>, N>, )

This modular multiplication algorithm uses Montgomery reduction for efficient implementation. It also additionally uses the “no-carry optimization” outlined here if Self::MODULUS has (a) a non-zero MSB, and (b) at least one zero bit in the rest of the modulus.

fn square_in_place(a: &mut Fp<MontBackend<Self, N>, N>)

fn inverse( a: &Fp<MontBackend<Self, N>, N>, ) -> Option<Fp<MontBackend<Self, N>, N>>

fn from_bigint(r: BigInt<N>) -> Option<Fp<MontBackend<Self, N>, N>>

fn into_bigint(a: Fp<MontBackend<Self, N>, N>) -> BigInt<N>

fn sum_of_products<const M: usize>( a: &[Fp<MontBackend<Self, N>, N>; M], b: &[Fp<MontBackend<Self, N>, N>; M], ) -> Fp<MontBackend<Self, N>, N>

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors