galois

func (*Field) ConvolutionRoot ¶

func (f *Field) ConvolutionRoot(r io.Reader, a, b []*big.Int) (*big.Int, error)

ConvolutionRoot returns a primitive root of unity suitable for convolving a and b with f.Convolve. The Reader is propagated to f.RootOfUnity().

func (*Field) Convolve ¶

func (f *Field) Convolve(a, b []*big.Int, primitiveRoot *big.Int) ([]*big.Int, error)

Convolve returns the convolution a∗b in log-linear time using the convolution theorem: both a and b are transformed to their frequency domain as A and B respectively, and the inverse-FFT of the dot product A•B is returned.

The current FFT implementation only supports 2^k length slices. The primitiveRoot must therefore be an nth root of unity in the Field where n is the smallest power of 2 >= len(a)+len(b)-1; see f.ConvolutionRoot().This remains more efficient than a quadratic-time algorithm even with maximal padding.

func (*Field) Exp ¶

func (f *Field) Exp(x, y *big.Int) *big.Int

Exp returns x**y mod f.Order().

func (*Field) FFT ¶

func (f *Field) FFT(x []*big.Int, primitiveRoot *big.Int) ([]*big.Int, error)

FFT performs a fast Fourier transform of xs. The nth primitiveRoot (of unity) can be obtained with f.RootOfUnity(…, len(xs), true).

func (*Field) FFTInverse ¶

func (f *Field) FFTInverse(X []*big.Int, primitiveRoot *big.Int) ([]*big.Int, error)

FFTInverse inverts f.FFT().

func (*Field) Mul ¶

func (f *Field) Mul(x, y *big.Int) *big.Int

Mul returns x*y mod f.Order().

func (*Field) MultInverse ¶

func (f *Field) MultInverse(x *big.Int) *big.Int

MultInverse returns the multiplicative inverse of x.

func (*Field) Order ¶

func (f *Field) Order() *big.Int

Order returns the order of the Field.

func (*Field) PolynomialFromRoots ¶

func (f *Field) PolynomialFromRoots(roots []*big.Int) ([]*big.Int, error)

func (*Field) Random ¶

func (f *Field) Random(r io.Reader) (*big.Int, error)

Random returns a random field element from [0,q). The Reader is propagated to rand.Int().

func (*Field) RootOfUnity ¶

func (f *Field) RootOfUnity(r io.Reader, n uint64, primitive bool) (*big.Int, error)

RootOfUnity returns a random nth root of unity; n must be even. A primitive root is one that can be used to generate all corresponding roots by raising it to each of [0,n). If n does not divide (q-1), the only root is 1 itself, which is returned (regardless of the value of `primitive`).

The io.Reader is used to choose a random field element from which a root is determined via crypto/rand.Int(). If primitive==false this will only be called once, but primitive roots are determined probabilistically with 50% success rate on each attempt.

As we're in a cyclic group, for any non-zero x: x^q = x, so x^(q-1) = 1. Since x^(y/n)^n = x^y, x^((q-1)/n) is an nth root of 1 mod q. Detection of a primitive root is described in https://crypto.stackexchange.com/a/63616.