galois v0.0.32

Released July 28, 2022

Breaking changes

• Changed "quadratic residue" language in Galois fields to "square". This seems to be more canonical. Quadratic residue connotes quadratic residue modulo $p$, which is a square in $\mathrm{GF}(p)$. However, a quadratic residue modulo $p^m$ is not a square in $\mathrm{GF}(p^m)$. Hopefully the "square" language is more clear. (#392)
  • Renamed FieldArray.is_quadratic_residue to FieldArray.is_square.
  • Renamed FieldArray.quadratic_residues to FieldArray.squares.
  • Renamed FieldArray.quadratic_non_residues to FieldArray.non_squares.

Changes

• Added support for Numba 0.56.x. (#389)
• Added general logarithm base any primitive element in FieldArray.log(). (#385)

  >>> GF = galois.GF(3**5)
  >>> x = GF.Random(10, low=1); x
  GF([215, 176,  52,  20, 236,  48, 217, 131,  13,  57], order=3^5)
  >>> beta = GF.primitive_elements[-1]; beta
  GF(242, order=3^5)
  >>> i = x.log(beta); i
  array([171, 240, 109,  65, 162,  57,  34, 166,  72,  56])
  >>> np.array_equal(beta ** i, x)
  True

• Added Pollard-$\rho$ discrete logarithm for certain $\mathrm{GF}(2^m)$ fields. The algorithm is only applicable to fields whose multiplicative group has prime order. It has complexity $O(\sqrt{n})$ compared to $O(n)$ for the brute-force algorithm. In this example, Pollard-$\rho$ is 1,650% faster than brute force. (#385)

  In [3]: GF = galois.GF(2**19, compile="jit-calculate")
  
  In [4]: galois.is_prime(GF.order - 1)
  Out[4]: True
  
  In [5]: x = GF.Random(100, low=1, seed=1)
  
  # v0.0.31
  In [6]: %timeit np.log(x)
  80.3 ms ± 55.8 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
  
  # v0.0.32
  In [6]: %timeit np.log(x)
  4.59 ms ± 90.5 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

• Added Pohlig-Hellman discrete logarithm to replace the brute-force search. It has complexity $O(\sum e_i(\textrm{lg}\ n + \sqrt{p_i}))$ compared to $O(n)$ for the brute-force algorithm. It is especially efficient for fields whose multiplicative group has smooth order. In this example with $p^m - 1$ smooth, Pohlig-Hellman is ~3,000,000% faster than brute force. (#387)

  In [3]: GF = galois.GF(491954233)
  
  # The multiplicative group's order is smooth
  In [4]: galois.factors(GF.order - 1)
  Out[4]: ([2, 3, 7, 11, 19, 14011], [3, 1, 1, 1, 1, 1])
  
  In [5]: x = GF.Random(1, low=1, seed=1)
  
  # v0.0.31
  In [6]: %timeit np.log(x)
  1.82 s ± 2.95 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  
  # v0.0.32
  In [6]: %timeit np.log(x)
  61.3 µs ± 14.6 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

• Added Itoh-Tsujii inversion algorithm for extension fields, which is 35% faster than inversion with Fermat's Little Theorem. (#383)

  In [3]: GF = galois.GF(109987**4)
  
  In [4]: x = GF.Random(100, low=1, seed=1)
  
  # v0.0.31
  In [5]: %timeit np.reciprocal(x)
  646 ms ± 834 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
  
  # v0.0.32
  In [5]: %timeit np.reciprocal(x)
  479 ms ± 26.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

• Fixed a bug where FieldArray subclasses and instances could not be pickled. (#393)

Contributors

• Matt Hostetter (@mhostetter)

Commits

bf1275a Version bump to 0.0.32
cc89ff1 Add release notes for v0.0.32
4270191 Use LaTeX math in old release notes
9e6fdaf Allow $...$ math notation in .md documents
b0ff7fd Update Sphinx Immaterial to remove rubrics from left TOC
97eb7a2 Add FieldArray class and instance pickling unit tests
3fc1cbb Support pickling FieldArray subclasses and instances
d94c3b6 Rename FieldArray.quadratic_non_residues to FieldArray.non_squares
ea714b3 Rename FieldArray.quadratic_residues to FieldArray.squares
2c33d99 Rename FieldArray.is_quadratic_residue() to FieldArray.is_square()
ce1e4cf Revert minor README edit
80f1e79 Minor README edit (to test --ff-only merge)
5540337 Fix error in --ff-only merge action
61b03be Add fast-forward merge GitHub action for PRs
7781e01 Add support for Numba 0.56.x
a291a0e Move lookup table construction to _lookup.py
7f28770 Add Pohlig-Hellman discrete logarithm
b5d452c Rename variables to be consistent with textbook algorithm
106dc72 Add CRT helper JIT function
198b1b3 Add unit test for Pollard-rho logarithm
1957c25 Add Pollard-rho discrete logarithm for some GF(2^m) fields
7dbe38f Ensure lookup tables were created before compiling lookup ufuncs
ed5b9e4 Add unit test for arbitrary logarithm
e12d3a4 Add arbitrary logarithm in FieldArray.log
036d3eb Raise an arithmetic error is log base non-primitive element
b3fb252 Reorganize default ufunc dispatcher definitions
182a493 Update benchmark stats
7b26bc6 Add square-and-multiply helper ufunc
7878c7a Use Itoh-Tsujii inversion algorithm for reciprocal in extension fields