primitives.field

primitives.field#

Goldilocks field GF(p) and cubic extension GF(p^3).

Uses galois library for all field arithmetic. FF and FF3 are the field types.

Type Discipline#

When to use FF (base field): - Domain generators (omega, omega_extended) - Shift values for coset evaluation - Single field element constants - Hash outputs (4 base field elements)

When to use FF3 (extension field): - Polynomial evaluations (prover and verifier) - Challenges (derived from Fiat-Shamir transcript) - Constraint polynomial values - FRI folding values - Polynomial batching coefficients (vf1, vf2)

Interleaved Format (InterleavedFF3): - Used for C++ compatibility and bulk operations - Layout: [c0_0, c1_0, c2_0, c0_1, c1_1, c2_1, …] - Each FF3 element has 3 consecutive coefficients - Convert with: ff3_from_interleaved_numpy(), ff3_to_interleaved_numpy()

FF3 is loaded from a pre-computed cache file (ff3_cache.pkl) to avoid the ~7s initialization cost of galois.GF() for extension fields. To regenerate the cache:

python -c “from primitives.field import _regenerate_ff3_cache; _regenerate_ff3_cache()”

Attributes#

`GOLDILOCKS_PRIME`
`FIELD_EXTENSION_DEGREE`
`FIELD_EXTENSION`
`FF`	Base field GF(p) - Goldilocks prime field.
`FF3`
`FF3Poly`
`FFPoly`
`FF3Array`
`FFArray`
`HashOutput`
`InterleavedFF3`
`ntt`
`intt`
`SHIFT`
`SHIFT_INV`
`W`
`W_INV`

Functions#

`ff3_coeffs`(→ list[int])	Extract ascending-order coefficients [a0, a1, a2] from FF3 element.
`ff3_array`(→ FF3)	Construct FF3 array from parallel coefficient lists.
`ff3_array_from_base`(→ FF3)	Construct FF3 array from base field values (c1=c2=0).
`ff3_from_flat_list`(→ FF3)	Convert flattened [c0,c1,c2,c0,c1,c2,...] to FF3 array.
`ff3_to_flat_list`(→ list[int])	Convert FF3 array to flattened [c0,c1,c2,c0,c1,c2,...].
`ff3_from_json`(→ FF3)	Parse JSON [[c0,c1,c2],...] to FF3 array.
`ff3_to_json`(→ list[list[int]])	Convert FF3 array to JSON [[c0,c1,c2],...] format.
`ff3_from_interleaved_numpy`(→ FF3)	Convert interleaved numpy [c0,c1,c2,c0,c1,c2,...] to FF3 array.
`ff3_to_interleaved_numpy`(→ numpy.ndarray)	Convert FF3 array to interleaved numpy [c0,c1,c2,c0,c1,c2,...].
`ff3`(→ FF3)	Construct FF3 scalar from ascending-order coefficients [c0, c1, c2].
`ff3_from_base`(→ FF3)	Embed base field element into FF3 as (val, 0, 0).
`ff3_from_numpy_coeffs`(→ FF3)	Convert numpy [c0, c1, c2] to FF3 scalar.
`ff3_to_numpy_coeffs`(→ numpy.ndarray)	Convert FF3 scalar to numpy [c0, c1, c2].
`ff3_from_buffer_at`(→ FF3)	Extract FF3 elements from buffer at coefficient indices.
`ff3_store_to_buffer`(→ None)	Store FF3 elements to buffer at coefficient indices.
`get_omega`(→ int)	Return primitive 2^n_bits-th root of unity.
`get_omega_inv`(→ int)	Return inverse of primitive 2^n_bits-th root of unity.
`batch_inverse`(→ galois.Array)	Montgomery batch inversion for any galois array.

Module Contents#

primitives.field.GOLDILOCKS_PRIME = 18446744069414584321[source]#

primitives.field.FIELD_EXTENSION_DEGREE = 3[source]#

primitives.field.FIELD_EXTENSION = 3[source]#

primitives.field.FF[source]#: Base field GF(p) - Goldilocks prime field.

primitives.field.FF3[source]#

primitives.field.FF3Poly[source]#

primitives.field.FFPoly[source]#

primitives.field.FF3Array[source]#

primitives.field.FFArray[source]#

primitives.field.HashOutput[source]#

primitives.field.InterleavedFF3[source]#

primitives.field.ff3_coeffs(elem: FF3) → list[int][source]#: Extract ascending-order coefficients [a0, a1, a2] from FF3 element.

primitives.field.ff3_array(c0: list[int], c1: list[int], c2: list[int]) → FF3[source]#: Construct FF3 array from parallel coefficient lists.

primitives.field.ff3_array_from_base(vals: list[int]) → FF3[source]#: Construct FF3 array from base field values (c1=c2=0).

primitives.field.ff3_from_flat_list(coeffs: list[int]) → FF3[source]#: Convert flattened [c0,c1,c2,c0,c1,c2,…] to FF3 array.

primitives.field.ff3_to_flat_list(arr: FF3) → list[int][source]#: Convert FF3 array to flattened [c0,c1,c2,c0,c1,c2,…].

primitives.field.ff3_from_json(json_arr: list[list[int]]) → FF3[source]#: Parse JSON [[c0,c1,c2],…] to FF3 array.

primitives.field.ff3_to_json(arr: FF3) → list[list[int]][source]#: Convert FF3 array to JSON [[c0,c1,c2],…] format.

primitives.field.ff3_from_interleaved_numpy(arr: numpy.ndarray, n: int) → FF3[source]#: Convert interleaved numpy [c0,c1,c2,c0,c1,c2,…] to FF3 array.

primitives.field.ff3_to_interleaved_numpy(arr: FF3) → numpy.ndarray[source]#: Convert FF3 array to interleaved numpy [c0,c1,c2,c0,c1,c2,…].

primitives.field.ff3(coeffs: list[int]) → FF3[source]#: Construct FF3 scalar from ascending-order coefficients [c0, c1, c2].

primitives.field.ff3_from_base(val: int) → FF3[source]#: Embed base field element into FF3 as (val, 0, 0).

primitives.field.ff3_from_numpy_coeffs(arr: numpy.ndarray) → FF3[source]#: Convert numpy [c0, c1, c2] to FF3 scalar.

primitives.field.ff3_to_numpy_coeffs(elem: FF3) → numpy.ndarray[source]#: Convert FF3 scalar to numpy [c0, c1, c2].

primitives.field.ff3_from_buffer_at(buffer: numpy.ndarray, indices: list[int]) → FF3[source]#

Extract FF3 elements from buffer at coefficient indices.

Each index points to c0, with c1 at index+1, c2 at index+2.

primitives.field.ff3_store_to_buffer(arr: FF3, buffer: numpy.ndarray, indices: list[int]) → None[source]#

Store FF3 elements to buffer at coefficient indices.

Each index points to c0, stores c1 at index+1, c2 at index+2.

primitives.field.ntt[source]#

primitives.field.intt[source]#

primitives.field.SHIFT[source]#

primitives.field.SHIFT_INV[source]#

primitives.field.W: list[int] = [1, 18446744069414584320, 281474976710656, 16777216, 4096, 64, 8, 2198989700608,...[source]#

primitives.field.W_INV: list[int] = [1, 18446744069414584320, 18446462594437873665, 18446742969902956801, 18442240469788262401,...[source]#

primitives.field.get_omega(n_bits: int) → int[source]#: Return primitive 2^n_bits-th root of unity.

primitives.field.get_omega_inv(n_bits: int) → int[source]#: Return inverse of primitive 2^n_bits-th root of unity.

primitives.field.batch_inverse(values: galois.Array) → galois.Array[source]#

Montgomery batch inversion for any galois array.

Converts N field inversions into 3N-3 multiplications + 1 inversion. Works with any galois FieldArray type (FF, FF3, or any GF).

Algorithm: 1. Forward pass: Compute prefix products cumprods[i] = a[0] * a[1] * … * a[i] 2. Single inversion: inv_total = cumprods[N-1]^(-1) 3. Backward pass: Extract individual inverses using cumprods

Args:: values: Galois FieldArray to invert (must all be non-zero)
Returns:: Galois FieldArray where result[i] = values[i]^(-1)
Raises:: ZeroDivisionError: If any element is zero

Reference: pil2-stark/src/goldilocks/src/goldilocks_base_field.hpp::batchInverse