NTT
Number Theoretic Transform over a prime field F_p.
The prime p must have sufficient two-adicity for the desired NTT size: p - 1 must be divisible by 2^k where 2^k >= n (the transform size). This ensures primitive n-th roots of unity exist in F_p.
Default configuration uses the BLS12-381 scalar field (two-adicity 32, supporting NTTs up to 2^32 ≈ 4.3 billion elements).
Attributes
- Graph
-
- Supertypes
-
class Objecttrait Matchableclass Any
- Self type
-
NTT.type
Members list
Value members
Concrete methods
Forward NTT (Cooley-Tukey DIT butterfly), in-place.
Forward NTT (Cooley-Tukey DIT butterfly), in-place.
Transforms polynomial coefficients to evaluations at powers of omega.
Value parameters
- a
-
array of coefficients, length must equal n
- n
-
transform size, must be a power of 2
- omega
-
primitive n-th root of unity
- prime
-
the field prime
Attributes
Inverse NTT, in-place, scales by n^{-1}.
Inverse NTT, in-place, scales by n^{-1}.
Transforms evaluations back to polynomial coefficients.
Value parameters
- a
-
array of evaluations, length must equal n
- n
-
transform size, must be a power of 2
- omega
-
primitive n-th root of unity (same as used in forward)
- prime
-
the field prime
Attributes
Multiply two polynomials via NTT: O(n log n).
Multiply two polynomials via NTT: O(n log n).
Coefficients are in ascending degree order. Uses BLS12-381 scalar field by default.
Value parameters
- a
-
first polynomial coefficients
- b
-
second polynomial coefficients
- maxRootOfUnity
-
primitive 2^twoAdicity-th root of unity
- prime
-
the field prime
- twoAdicity
-
two-adicity of the field
Attributes
- Returns
-
product polynomial coefficients
Get primitive n-th root of unity (n must be power of 2).
Get primitive n-th root of unity (n must be power of 2).
Computes omega_n = maxRootOfUnity ^ (2^(twoAdicity - log2(n))) mod prime.
Value parameters
- maxRootOfUnity
-
primitive 2^twoAdicity-th root of unity
- n
-
NTT size, must be a power of 2 and <= 2^twoAdicity
- prime
-
the field prime
- twoAdicity
-
the two-adicity of the field (p-1 = 2^s · t)
Attributes
Concrete fields
BLS12-381 scalar field prime.
BLS12-381 scalar field prime.
Attributes
Primitive 2^32-th root of unity for BLS12-381 scalar field: 7^t mod q where t = (q-1)/2^32.
Primitive 2^32-th root of unity for BLS12-381 scalar field: 7^t mod q where t = (q-1)/2^32.
Attributes
Two-adicity of BLS12-381 scalar field: q - 1 = 2^32 · t, max NTT size = 2^32.
Two-adicity of BLS12-381 scalar field: q - 1 = 2^32 · t, max NTT size = 2^32.