Crate p3_field

A framework for finite fields.

Modules

coset

exponentiation

extension

integers

A collection of traits and macros which convert primitive integer types into field elements.

Macros

impl_raw_serializable_primefield32

A simple macro which allows us to implement the RawSerializable trait for any 32-bit field. The field must implement PrimeField32.

impl_raw_serializable_primefield64

A simple macro which allows us to implement the RawSerializable trait for any 64-bit field. The field must implement PrimeField64 (and should not implement PrimeField32).

quotient_map_large_iint

For large signed integer types, a simple method which is usually good enough is to simply check the sign and use this to pass to the equivalent unsigned method.

quotient_map_large_uint

If the unsigned integer type is large enough, there is often no method better for from_int than just doing a modular reduction to a smaller type.

quotient_map_small_int

If the integer type is smaller than the field order all possible inputs are canonical. In such a case we can easily implement QuotientMap<SmallInt> as all three methods will coincide.

quotient_map_small_internals

This allows us to avoid some duplication which arises when working with fields which contain a generic parameter.

Structs

FieldArray

Powers

An iterator which returns the powers of a base element b shifted by current c: c, c * b, c * b^2, ....

Traits

Algebra

A ring R implements Algebra<F> if there is an injective homomorphism from F into R; in particular only F::ZERO maps to R::ZERO.

BasedVectorSpace

A vector space V over F with a fixed basis. Fixing the basis allows elements of V to be converted to and from DIMENSION many elements of F which are interpreted as basis coefficients.

ExtensionField

A field EF which is also an algebra over a field F.

Field

A field F. This permits both modular fields ℤ/p along with their field extensions.

InjectiveMonomial

A ring implements InjectiveMonomial<N> if the algebraic function f(x) = x^N is an injective map on elements of the ring.

Packable

A trait to constrain types that can be packed into a packed value.

PackedField

An array of field elements which can be packed into a vector for SIMD operations.

PackedFieldExtension

Fix a field F a packing width W and an extension field EF of F.

PackedFieldPow2

Safety

PackedValue

A trait for array-like structs made up of multiple scalar elements.

PermutationMonomial

A ring implements PermutationMonomial<N> if the algebraic function f(x) = x^N is invertible and thus acts as a permutation on elements of the ring.

PrimeCharacteristicRing

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

PrimeField

A field isomorphic to ℤ/p for some prime p.

PrimeField32

A prime field ℤ/p with order p < 2^32.

PrimeField64

A prime field ℤ/p with order, p < 2^64.

RawDataSerializable

A collection of methods designed to help hash field elements.

TwoAdicField

A field which supplies information like the two-adicity of its multiplicative group, and methods for obtaining two-adic generators.

Functions

add_scaled_slice_in_place

Adds other, scaled by s, to the mutable slice using packing, or slice += other * s.

batch_multiplicative_inverse

Batch multiplicative inverses with Montgomery’s trick This is Montgomery’s trick. At a high level, we invert the product of the given field elements, then derive the individual inverses from that via multiplication.

cyclic_subgroup_coset_known_order

Computes a coset of a multiplicative subgroup whose order is known in advance.

cyclic_subgroup_known_order

Computes a multiplicative subgroup whose order is known in advance.

dot_product

Maximally generic dot product.

field_to_array

Extend a ring R element x to an array of length D by filling zeros.

halve_u32

Given an element x from a 32 bit field F_P compute x/2.

halve_u64

Given an element x from a 64 bit field F_P compute x/2.

par_add_scaled_slice_in_place

Adds other, scaled by s, to the mutable slice using packing, or slice += other * s.

par_scale_slice_in_place

Scales each element of the slice by s using packing and parallelization.

reduce_32

Reduce a slice of 32-bit field elements into a single element of a larger field.

scale_slice_in_placeDeprecated

This function is deprecated. It is currently a wrapper for par_scale_slice_in_place, which it should be replaced with if parallelization is required.

scale_slice_in_place_single_core

Scales each element of the slice by s using packing.

split_32

Split a large field element into n base-$2^{64}$ chunks and map each into a 32-bit field.