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.

interleaves

A file containing a collection of architecture-specific interleaving functions. Used for PackedFields to implement interleaving operations.

op_assign_macros

A collection of macros designed to implement simple operations whose implementations are often boilerplate based off some other operation.

Macros

impl_add_assign

Given a struct which implements Add implement AddAssign<T> for any type T which implements Into<Self>.

impl_add_base_field

Given two structs Alg and Field where Alg implements From<Field>, implement Add<Field> for Alg and Add<Alg> for Field.

impl_div_methods

Given two structs Alg and Field where Alg implements From<Field>, implement Div<Field> and DivAssign<Field> for Alg.

impl_mul_base_field

Given two structs Alg and Field where Alg implements From<Field>, implement Mul<Field> for Alg and Mul<Alg> for Field.

impl_mul_methods

Given a struct which implements Mul implement MulAssign<T> for any type T which implements Into<Self>.

impl_packed_field_pow_2

A macro to implement the PackedFieldPow2 trait for PackedFields. The macro assumes that the PackedFields have a to_vector and from_vector method, which convert between the PackedField and a packed vector.

impl_packed_value

Given Field and Algebra structs where Algebra is simply a wrapper around [Field; N] implement PackedValue for Algebra.

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).

impl_rng

Given a struct Alg which is a wrapper over [Field; N] for some N, implement Distribution<Alg> for StandardUniform.

impl_sub_assign

Given a struct which implements Sub implement SubAssign<T> for any type T which implements Into<Self>.

impl_sub_base_field

Given two structs Alg and Field where Alg implements From<Field>, implement Sub<Field> for Alg and Sub<Alg> for Field.

impl_sum_prod_base_field

Given two structs Alg and Field where Alg implements From<Field>, implement Sum<Field> and Product<Field> for Alg.

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.

ring_sum

Given a struct which implements Add implement Sum.

Structs

BoundedPowers

Same as Powers, but returns a bounded number of powers.

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.

Dup

Cheap duplication for prime-characteristic ring elements used in hot paths.

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.

SpongePaddingValue

Values that can act as sponge lanes for delimiter padding.

TwoAdicField

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

Functions

absorb_radix_bits

Bit length of F::ORDER_U32 - 1, i.e. the smallest b with F::ORDER_U32 - 1 < 2^b.

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.

chunked_linear_combination

Linear combination over runtime-length slices, processing in chunks of CHUNK.

chunked_mixed_dot_product

Compute Σ values[i] * coeffs[i] over N pairs.

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.

dispatch_chunked_mixed_dot_product

Lower a runtime chunk size into a const-generic call to the fixed-chunk dot product.

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.

injective_pack_bits

Largest b such that every integer in [0, 2^b) maps injectively into F via [PrimeField32::from_int].

max_absorb_injective_limbs

Maximum limbs per PrimeField rate slot when absorbing with radix $2^{\texttt{absorb_radix_bits::()}}$ (see reduce_packed).

max_packed_injective_limbs

Maximum number of PrimeField32 elements packable into PrimeField injectively via reduce_packed with the given radix_bits (base-$2^{radix_bits}$ digits bounded by F::ORDER_U32 - 1).

max_shifted_absorb_injective_limbs

Maximum shifted limbs per PrimeField rate slot when absorbing with radix $2^{\texttt{absorb_radix_bits::()}}$ (see reduce_packed_shifted).

max_shifted_packed_injective_limbs

Maximum number of shifted PrimeField32 elements packable into PrimeField injectively via reduce_packed_shifted with the given radix_bits.

packed_mod_add

Add two arrays of integers modulo P using packing.

packed_mod_sub

Subtract two arrays of integers modulo P using packing.

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.

pf_packed_limbs_cover_order

Returns true iff every integer in [0, SF::order()) fits in num_limbs little-endian base-2^radix_bits digits without truncation, i.e. 2^{num_limbs · radix_bits} ≥ SF::order().

reduce_32

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

reduce_packed

Horner-evaluate vals as base-$2^{radix_bits}$ digits into TF.

reduce_packed_shifted

Horner-evaluate vals as base-$2^{radix_bits}$ digits into TF, shifting each digit by +1.

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.

split_pf_to_field_order_limbs

Split val into num_limbs little-endian base-|TF| limbs, each mapped into TF.

split_pf_to_packed_limbs

Split val into num_limbs little-endian base-2^radix_bits limbs, each mapped into TF.

squeeze_field_order_num_limbs

Number of TF limbs with statistical bias < 1/|TF| when decomposing a uniformly random PF element in base |TF| (see split_pf_to_field_order_limbs).