parseHex reads an hex-formatted number modulo 2^bits+1.

Mul multiplies p and q modulo X^K-1, where K = 1<<p.k. The product is done via a Fourier transform.

Add computes addition mod 2^n+1.

Shift computes (x << k) mod (2^n+1).

func BenchmarkScanFast100M(b *testing.B) { benchmarkScanFast(100e6, b) }

go:linkname addVW math/big.addVW

polyFromNat slices the number x into a polynomial with 1<<k coefficients made of m words.

fourier performs an unnormalized Fourier transform of src, a length 1<<k vector of numbers modulo b^n+1 where b = 1<<_W.

go:linkname subVV math/big.subVV

Int evaluates back a poly to its integer value.

Mul computes the product x*y and returns z. It can be used instead of the Mul method of *big.Int from math/big package.

ShiftHalf shifts x by k/2 bits the left. Shifting by 1/2 bit is multiplication by sqrt(2) mod 2^n+1 which is 2^(3n/4) - 2^(n/4). A temporary buffer mu

Sub computes substraction mod 2^n+1.

cmpFourier computes the Fourier transform of src and compares it to the FFT result.

returns the FFT length k, m the number of words per chunk such that m << k is larger than the number of words in x*y.

Transform evaluates p at θ^i for i = 0...K-1, where θ is a K-th primitive root of unity in Z/(b^n+1)Z.

go:linkname subVW math/big.subVW

valueSize returns the length (in words) to use for polynomial coefficients, to compute a correct product of polynomials P*Q where deg(P*Q) < K (== 1<<

FromDecimalString converts the base 10 string representation of a natural (non-negative) number into a *big.Int. Its asymptotic complexity is less tha

InvTransform reconstructs p (modulo X^K - 1) from its values at θ^i for i = 0..K-1.

go:linkname addVV math/big.addVV

go:linkname addMulVVW math/big.addMulVVW

copied from math/big basicMul multiplies x and y and leaves the result in z. The (non-normalized) result is placed in z[0 : len(x) + len(y)].

A FFT size of K=1<<k is adequate when K is about 2*sqrt(N) where N = x.Bitlen() + y.Bitlen().

measureMul benchmarks math/big versus FFT for a given input size (in bits).

go:linkname shlVU math/big.shlVU

Unbalanced multiplication benchmarks