Trait PrimeCharacteristicRing

pub trait PrimeCharacteristicRing:
    Sized
    + Default
    + Clone
    + Add<Output = Self>
    + AddAssign
    + Sub<Output = Self>
    + SubAssign
    + Neg<Output = Self>
    + Mul<Output = Self>
    + MulAssign
    + Sum
    + Product
    + Debug {
    type PrimeSubfield: PrimeField;

    const ZERO: Self;
    const ONE: Self;
    const TWO: Self;
    const NEG_ONE: Self;
Show 32 methods
    // Required method
    fn from_prime_subfield(f: Self::PrimeSubfield) -> Self;

    // Provided methods
    fn from_bool(b: bool) -> Self { ... }
    fn from_u8(int: u8) -> Self { ... }
    fn from_u16(int: u16) -> Self { ... }
    fn from_u32(int: u32) -> Self { ... }
    fn from_u64(int: u64) -> Self { ... }
    fn from_u128(int: u128) -> Self { ... }
    fn from_usize(int: usize) -> Self { ... }
    fn from_i8(int: i8) -> Self { ... }
    fn from_i16(int: i16) -> Self { ... }
    fn from_i32(int: i32) -> Self { ... }
    fn from_i64(int: i64) -> Self { ... }
    fn from_i128(int: i128) -> Self { ... }
    fn from_isize(int: isize) -> Self { ... }
    fn double(&self) -> Self { ... }
    fn halve(&self) -> Self { ... }
    fn square(&self) -> Self { ... }
    fn cube(&self) -> Self { ... }
    fn xor(&self, y: &Self) -> Self { ... }
    fn xor3(&self, y: &Self, z: &Self) -> Self { ... }
    fn andn(&self, y: &Self) -> Self { ... }
    fn bool_check(&self) -> Self { ... }
    fn exp_u64(&self, power: u64) -> Self { ... }
    fn exp_const_u64<const POWER: u64>(&self) -> Self { ... }
    fn exp_power_of_2(&self, power_log: usize) -> Self { ... }
    fn mul_2exp_u64(&self, exp: u64) -> Self { ... }
    fn div_2exp_u64(&self, exp: u64) -> Self { ... }
    fn powers(&self) -> Powers<Self> ⓘ { ... }
    fn shifted_powers(&self, start: Self) -> Powers<Self> ⓘ { ... }
    fn dot_product<const N: usize>(u: &[Self; N], v: &[Self; N]) -> Self { ... }
    fn sum_array<const N: usize>(input: &[Self]) -> Self { ... }
    fn zero_vec(len: usize) -> Vec<Self> { ... }
}

Expand description

A commutative ring, R, with prime characteristic, p.

This permits elements like:

A single finite field element.
A symbolic expression which would evaluate to a field element.
An array of finite field elements.
A polynomial with coefficients in a finite field.

§Mathematical Description

Mathematically, a commutative ring is a set of objects which supports an addition-like like operation, +, and a multiplication-like operation *.

Let x, y, z denote arbitrary elements of the set.

Then, an operation is addition-like if it satisfies the following properties:

Commutativity => x + y = y + x
Associativity => x + (y + z) = (x + y) + z
Unit => There exists an identity element ZERO satisfying x + ZERO = x.
Inverses => For every x there exists a unique inverse (-x) satisfying x + (-x) = ZERO

Similarly, an operation is multiplication-like if it satisfies the following properties:

Commutativity => x * y = y * x
Associativity => x * (y * z) = (x * y) * z
Unit => There exists an identity element ONE satisfying x * ONE = x.
Distributivity => The two operations + and * must together satisfy x * (y + z) = (x * y) + (x * z)

Unlike in the addition case, we do not require inverses to exist with respect to *.

The simplest examples of commutative rings are the integers (ℤ), and the integers mod N (ℤ/N).

The characteristic of a ring is the smallest positive integer r such that 0 = r . 1 = 1 + 1 + ... + 1 (r times). For example, the characteristic of the modulo ring ℤ/N is N.

Rings with prime characteristic are particularly special due to their close relationship with finite fields.

Required Associated Constants§

const ZERO: Self

The additive identity of the ring.

For every element a in the ring we require the following properties:

a + ZERO = ZERO + a = a,

a + (-a) = (-a) + a = ZERO.

const ONE: Self

The multiplicative identity of the ring.

For every element a in the ring we require the following property:

a*ONE = ONE*a = a.

const TWO: Self

The element in the ring given by ONE + ONE.

This is provided as a convenience as TWO occurs regularly in the proving system. This also is slightly faster than computing it via addition. Note that multiplication by TWO is discouraged. Instead of a * TWO use a.double() which will be faster.

If the field has characteristic 2 this is equal to ZERO.

const NEG_ONE: Self

The element in the ring given by -ONE.

This is provided as a convenience as NEG_ONE occurs regularly in the proving system. This also is slightly faster than computing it via negation. Note that where possible NEG_ONE should be absorbed into mathematical operations. For example a - b will be faster than a + NEG_ONE * b and similarly (-b) is faster than NEG_ONE * b.

If the field has characteristic 2 this is equal to ONE.

Required Associated Types§

type PrimeSubfield: PrimeField

The field ℤ/p where the characteristic of this ring is p.

Required Methods§

fn from_prime_subfield(f: Self::PrimeSubfield) -> Self

Embed an element of the prime field ℤ/p into the ring R.

Given any element [r] ∈ ℤ/p, represented by an integer r between 0 and p - 1 from_prime_subfield([r]) will be equal to:

Self::ONE + ... + Self::ONE (r times)

Provided Methods§

fn from_bool(b: bool) -> Self

Return Self::ONE if b is true and Self::ZERO if b is false.