primitives.field

primitives.field#

BabyBear field GF(p) and quartic extension GF(p^4).

Uses galois library for base field GF(p) arithmetic. Uses custom FF4 class for fast quartic extension field arithmetic.

Type Discipline#

FF (galois GF(p)):: Base field columns and scalars. Fast jit-compiled numpy operations.
FF4:: Extension field GF(p^4) scalars and columns. Stores coefficients as int64 arrays. Supports operator overloads: +, -, , /, *, negation. Scalars: shape (4,). Columns: shape (N, 4). Coefficients in ascending degree: c0 + c1*x + c2*x^2 + c3*x^3 as [c0, c1, c2, c3].

Attributes#

`BABYBEAR_PRIME`
`FIELD_EXTENSION_DEGREE`
`DIGEST_WIDTH`
`TWO_ADICITY`
`GENERATOR`
`TWO_INV`
`MONTY_R`
`MONTY_RINV`
`FF`	Base field GF(p) - BabyBear prime field.
`GaloisFF4`
`GaloisFF4Poly`
`FFPoly`
`HashOutput`
`Fe`
`FF4Coeffs`
`Digest`
`MerklePath`
`FF4Vec`
`W`
`W_INV`

Classes#

FF4

Extension field GF(p^4) = GF(p)[x]/(x^4 - 11) element or column.

Functions#

`ff4_coeffs`(→ list[int])	Extract ascending-order coefficients [a0, a1, a2, a3] from FF4 element.
`ff4`(→ GaloisFF4)	Construct galois FF4 scalar from ascending-order coefficients [a0, a1, a2, a3].
`ff4_from_base`(→ GaloisFF4)	Embed base field element into galois FF4 as (val, 0, 0, 0).
`ff4_array`(→ GaloisFF4)	Construct galois FF4 array from parallel coefficient lists.
`ff4_from_json`(→ GaloisFF4)	Parse JSON [[c0,c1,c2,c3],...] to galois FF4 array.
`ff4_to_json`(→ list[list[int]])	Convert galois FF4 array to JSON [[c0,c1,c2,c3],...] format.
`ef4_from_json`(→ FF4)	Parse JSON [[c0,c1,c2,c3],...] to FF4 column.
`ef4_to_json`(→ list[list[int]])	Convert FF4 column/scalar to JSON [[c0,c1,c2,c3],...] format.
`ef4_from_base`(→ FF4)	Embed base field element into extension field as (x, 0, 0, 0).
`ef4_mul`(→ FF4)	Multiply two extension field elements.
`ef4_mul_base`(→ FF4)	Multiply extension field element by a base field element.
`ef4_add`(→ FF4)	Add two extension field elements.
`ef4_sub`(→ FF4)	Subtract two extension field elements.
`ef4_neg`(→ FF4)	Negate an extension field element.
`ef4_inv`(→ FF4)	Multiplicative inverse in extension field.
`ef4_div`(→ FF4)	Division in extension field: a / b.
`ef4_pow`(→ FF4)	Exponentiation in extension field.
`ef4_exp_power_of_2`(→ FF4)	Compute x^(2^log_power) by repeated squaring.
`ef4v_add`(→ FF4)	DEPRECATED: Use a + b.
`ef4v_sub`(→ FF4)	DEPRECATED: Use a - b.
`ef4v_neg`(→ FF4)	DEPRECATED: Use -a.
`ef4v_mul`(→ FF4)	DEPRECATED: Use a * b.
`ef4v_mul_base`(→ FF4)	DEPRECATED: Use a.mul_base(b).
`ef4v_from_base`(→ FF4)	DEPRECATED: Use FF4.from_base(b).
`ef4v_from_scalar`(→ FF4)	DEPRECATED: Use FF4.broadcast(scalar, n).
`ef4v_inv`(→ FF4)	DEPRECATED: Use a.inv() or a ** -1.
`ef4v_mul_scalar`(→ FF4)	DEPRECATED: Use a * s.
`ef4v_zeros`(→ FF4)	DEPRECATED: Use FF4.zeros(n).
`ef4v_from_rows`(→ FF4)	DEPRECATED: Use FF4.from_rows(rows).
`ef4v_to_rows`(→ list)	DEPRECATED: Use v.to_rows().
`ef4v_roll`(→ FF4)	DEPRECATED: Use v.roll(shift).
`ef4v_cumsum`(→ FF4)	DEPRECATED: Use v.cumsum().
`ff_column`(→ FF)	DEPRECATED: Use FF(data) directly.
`ff_zeros`(→ FF)	DEPRECATED: Use FF.Zeros(n) directly.
`ff_constant`(→ FF)	DEPRECATED: Use FF(np.full(n, val % BABYBEAR_PRIME)) directly.
`ff_roll`(arr, shift)	DEPRECATED: Use np.roll(arr, shift) directly.
`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.
`inv_mod`(→ int)	Multiplicative inverse of x modulo BABYBEAR_PRIME.
`to_monty`(→ int)	Convert a canonical integer to BabyBear Montgomery form.
`from_monty`(→ int)	Convert a BabyBear Montgomery-form value to canonical form.
`reverse_bits_len`(→ int)	Reverse the lowest bit_len bits of x.
`bit_reverse_list`(→ list)	Reorder list elements by bit-reversing their indices.
`batch_inverse`(values)	Montgomery batch inversion for any galois array.
`ef4_batch_inverse`(→ list)	Montgomery batch inversion for FF4 elements.
`batch_inverse_base`(→ list)	Montgomery batch inversion in the base field.
`eval_poly_ef4_batch`(→ list)	Evaluate multiple polynomials at a single FF4 point using BSGS.

Module Contents#

primitives.field.BABYBEAR_PRIME = 2013265921[source]#

primitives.field.FIELD_EXTENSION_DEGREE = 4[source]#

primitives.field.DIGEST_WIDTH = 8[source]#

primitives.field.TWO_ADICITY = 27[source]#

primitives.field.GENERATOR = 31[source]#

primitives.field.TWO_INV[source]#

primitives.field.MONTY_R[source]#

primitives.field.MONTY_RINV[source]#

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

class primitives.field.FF4(data=None)[source]#

Extension field GF(p^4) = GF(p)[x]/(x^4 - 11) element or column.

Internal storage: int64 ndarray of shape (4,) for scalar or (N, 4) for column. Coefficients in ascending degree: c0 + c1*x + c2*x^2 + c3*x^3 stored as [c0, c1, c2, c3].

Supports operator overloads for clean mathematical notation:: c = a + b # addition c = a - b # subtraction c = a * b # polynomial multiplication c = a / b # division (multiply by inverse) c = a ** n # exponentiation (n can be -1) c = -a # negation

classmethod zeros(n: int) → FF4[source]#: Zero column of length n.

classmethod one() → FF4[source]#: Multiplicative identity scalar.

classmethod zero() → FF4[source]#: Additive identity scalar.

classmethod from_base(base) → FF4[source]#

Lift base field values to FF4 as (val, 0, 0, 0).

Args:: base: int, FF array, list[int], or ndarray of base field elements.

classmethod from_rows(rows: list) → FF4[source]#: Create from list of [c0, c1, c2, c3] coefficient lists.

classmethod broadcast(scalar: FF4, n: int) → FF4[source]#: Broadcast a scalar FF4 to a column of length n.

property is_scalar: bool[source]#

property coeffs: tuple[source]#: Return coefficients as tuple (c0, c1, c2, c3) for a scalar.

property c0: int[source]#: Constant coefficient (base field component).

to_rows() → list[source]#: Convert to list of [c0, c1, c2, c3] coefficient lists.

to_list() → list[source]#: Convert scalar to [c0, c1, c2, c3] list (backward compat with FF4Coeffs).

inv() → FF4[source]#: Multiplicative inverse via tower decomposition.

mul_base(base_vals) → FF4[source]#

Multiply each element by base field values (coefficient-wise scaling).

More efficient than a * FF4.from_base(b) because it avoids the full polynomial multiply (only 4 multiplications vs 16).

roll(shift: int) → FF4[source]#: Circular shift (for columns).

cumsum() → FF4[source]#: Prefix sum (for columns). Safe for height <= 2^27.

primitives.field.GaloisFF4[source]#

primitives.field.GaloisFF4Poly[source]#

primitives.field.FFPoly[source]#

primitives.field.HashOutput[source]#

primitives.field.Fe[source]#

primitives.field.FF4Coeffs[source]#

primitives.field.Digest[source]#

primitives.field.MerklePath[source]#

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

primitives.field.ff4(coeffs) → GaloisFF4[source]#

Construct galois FF4 scalar from ascending-order coefficients [a0, a1, a2, a3].

Also accepts FF4 objects for backward compat.

primitives.field.ff4_from_base(val: int) → GaloisFF4[source]#: Embed base field element into galois FF4 as (val, 0, 0, 0).

primitives.field.ff4_array(c0: list[int], c1: list[int], c2: list[int], c3: list[int]) → GaloisFF4[source]#: Construct galois FF4 array from parallel coefficient lists.

primitives.field.ff4_from_json(json_arr: list[list[int]]) → GaloisFF4[source]#: Parse JSON [[c0,c1,c2,c3],…] to galois FF4 array.

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

primitives.field.ef4_from_json(json_arr: list[list[int]]) → FF4[source]#: Parse JSON [[c0,c1,c2,c3],…] to FF4 column.

primitives.field.ef4_to_json(ef4_col: FF4) → list[list[int]][source]#: Convert FF4 column/scalar to JSON [[c0,c1,c2,c3],…] format.

primitives.field.ef4_from_base(x: int) → FF4[source]#

Embed base field element into extension field as (x, 0, 0, 0).

DEPRECATED: Use FF4(x) or FF4.from_base(x) instead.

primitives.field.ef4_mul(a, b) → FF4[source]#

Multiply two extension field elements.

DEPRECATED: Use a * b instead.

primitives.field.ef4_mul_base(a, b: int) → FF4[source]#

Multiply extension field element by a base field element.

DEPRECATED: Use a.mul_base(b) instead.

primitives.field.ef4_add(a, b) → FF4[source]#

Add two extension field elements.

DEPRECATED: Use a + b instead.

primitives.field.ef4_sub(a, b) → FF4[source]#

Subtract two extension field elements.

DEPRECATED: Use a - b instead.

primitives.field.ef4_neg(a) → FF4[source]#

Negate an extension field element.

DEPRECATED: Use -a instead.

primitives.field.ef4_inv(x) → FF4[source]#

Multiplicative inverse in extension field.

DEPRECATED: Use x ** -1 instead.

primitives.field.ef4_div(a, b) → FF4[source]#

Division in extension field: a / b.

DEPRECATED: Use a / b instead.

primitives.field.ef4_pow(x, n: int) → FF4[source]#

Exponentiation in extension field.

DEPRECATED: Use x ** n instead.

primitives.field.ef4_exp_power_of_2(x, log_power: int) → FF4[source]#

Compute x^(2^log_power) by repeated squaring.

DEPRECATED: Use x ** (2 ** log_power) instead.

primitives.field.FF4Vec[source]#

primitives.field.ef4v_add(a: FF4, b: FF4) → FF4[source]#: DEPRECATED: Use a + b.

primitives.field.ef4v_sub(a: FF4, b: FF4) → FF4[source]#: DEPRECATED: Use a - b.

primitives.field.ef4v_neg(a: FF4) → FF4[source]#: DEPRECATED: Use -a.

primitives.field.ef4v_mul(a: FF4, b: FF4) → FF4[source]#: DEPRECATED: Use a * b.

primitives.field.ef4v_mul_base(a: FF4, b) → FF4[source]#: DEPRECATED: Use a.mul_base(b).

primitives.field.ef4v_from_base(b) → FF4[source]#: DEPRECATED: Use FF4.from_base(b).

primitives.field.ef4v_from_scalar(coeffs, n: int) → FF4[source]#: DEPRECATED: Use FF4.broadcast(scalar, n).

primitives.field.ef4v_inv(a: FF4) → FF4[source]#: DEPRECATED: Use a.inv() or a ** -1.

primitives.field.ef4v_mul_scalar(a: FF4, s) → FF4[source]#: DEPRECATED: Use a * s.

primitives.field.ef4v_zeros(n: int) → FF4[source]#: DEPRECATED: Use FF4.zeros(n).

primitives.field.ef4v_from_rows(rows: list) → FF4[source]#: DEPRECATED: Use FF4.from_rows(rows).

primitives.field.ef4v_to_rows(v: FF4) → list[source]#: DEPRECATED: Use v.to_rows().

primitives.field.ef4v_roll(v: FF4, shift: int) → FF4[source]#: DEPRECATED: Use v.roll(shift).

primitives.field.ef4v_cumsum(v: FF4) → FF4[source]#: DEPRECATED: Use v.cumsum().

primitives.field.ff_column(data) → FF[source]#: DEPRECATED: Use FF(data) directly.

primitives.field.ff_zeros(n: int) → FF[source]#: DEPRECATED: Use FF.Zeros(n) directly.

primitives.field.ff_constant(val: int, n: int) → FF[source]#: DEPRECATED: Use FF(np.full(n, val % BABYBEAR_PRIME)) directly.

primitives.field.ff_roll(arr, shift: int)[source]#: DEPRECATED: Use np.roll(arr, shift) directly.

primitives.field.W: list[int] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0][source]#

primitives.field.W_INV: list[int][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.inv_mod(x: int) → int[source]#: Multiplicative inverse of x modulo BABYBEAR_PRIME.

primitives.field.to_monty(x: int) → int[source]#: Convert a canonical integer to BabyBear Montgomery form.

primitives.field.from_monty(x: int) → int[source]#: Convert a BabyBear Montgomery-form value to canonical form.

primitives.field.reverse_bits_len(x: int, bit_len: int) → int[source]#: Reverse the lowest bit_len bits of x.

primitives.field.bit_reverse_list(lst: list) → list[source]#: Reorder list elements by bit-reversing their indices.

primitives.field.batch_inverse(values)[source]#

Montgomery batch inversion for any galois array.

Converts N field inversions into 3N-3 multiplications + 1 inversion.

primitives.field.ef4_batch_inverse(values: list) → list[source]#

Montgomery batch inversion for FF4 elements.

Converts N extension field inversions into 3N-3 multiplications + 1 inversion. Accepts list of FF4 scalars or list of FF4Coeffs (list[int]).

primitives.field.batch_inverse_base(values: list) → list[source]#: Montgomery batch inversion in the base field.

primitives.field.eval_poly_ef4_batch(coeffs_per_col: list[list[int]], eval_point) → list[source]#

Evaluate multiple polynomials at a single FF4 point using BSGS.

Args:: coeffs_per_col: Polynomial coefficient vectors, all same degree. eval_point: FF4 scalar or [c0,c1,c2,c3] list.
Returns:: List of FF4 scalars, one per polynomial.