Releases · mhostetter/galois

02 Sep 17:44

github-actions

v0.1.1

1b87674

galois v0.1.1

Released September 2, 2022

Changes

Added support for NumPy 1.23. (#414)

Added seed keyword argument to random_prime(). (#409)

>>> galois.random_prime(100, seed=1)
2218840874040723579228056294021
>>> galois.random_prime(100, seed=1)
2218840874040723579228056294021

Deployed documentation to https://mhostetter.github.io/galois/latest/ with GitHub Pages. (#408)

Contributors

Matt Hostetter (@mhostetter)

Commits

1b87674 Add release notes for v0.1.1
ac57fc4 Fix code coverage
36c2413 Support NumPy 1.23 with Numba 0.56.2
8512651 Run CI tests with pytest-xdist
95b2910 Add pytest-xdist to dev dependencies
f5abfac Ensures tests start with known state
498e26f Enable displaying local variables in event of test failure
c58dbab Add seed kwarg to random_prime()
f174134 Fix LaTeX lexer
3cd2c55 Properly lex console output
f67539a Fix lexer for .txt document
b3584a0 Remove unnecessary SPHINX_BUILD flag
93c9a68 Simplify exporting public members of the API
1f63d38 Fix intermediate versions in CI builds
559ae65 Make "latest" first in version dropdown
2591ebb Update package metadata to point to docs on GitHub pages
0341cda Remove imports from public galois.typing module
e1fa463 Update README links to point to GitHub pages deployment
632d85c Avoid duplicate CI runs on master
c89a8ec Show setuptools_scm version during package build
7a4c599 Add deployment to GitHub pages
d0ac1ed Add version dropdown to GitHub Pages docs build
875e069 Modify warning section in README
0603572 Remove extra v in version tag

Assets 2

27 Aug 16:36

github-actions

v0.1.0

58e0078

galois v0.1.0

Released August 27, 2022

Changes

First beta release!
Fixed PyPI package metadata.

Contributors

Matt Hostetter (@mhostetter)

Commits

58e0078 Add release notes for v0.1.0
f5c248e Fix PyPI project metadata
0526f30 Fix wait for wheel action on git pushes
1a6437b Run CI on pushes to master
0ee78ef Fix double v in version specifier

Assets 2

26 Aug 22:45

github-actions

v0.0.33

750cce9

galois v0.0.33

Released August 26, 2022

Breaking changes

Modified FEC encode(), detect(), and decode() methods to always return FieldArray instances, not np.ndarray. (#397)
- Invoke .view(np.ndarray) on the output to convert it back to a NumPy array, if needed.

Changes

Added support for ArrayLike inputs to FEC encode(), detect(), and decode() methods. (#397)
Modified library packaging to use pyproject.toml and a src/ source code folder. (#404)

Contributors

Matt Hostetter (@mhostetter)

Commits

750cce9 Add release notes for v0.0.33
3c099b9 Remove [doc] extra and add docs/requirements.txt
a1ba9f3 Fix GitHub Actions
36b1e70 Revert "Clean up galois.typing namespace"
a17442a Fix coverage of unreachable code
17b09a4 Make all GitHub Actions run independently
7faa30a Rename .yml files to .yaml
fe309c0 Add and center GitHub Actions badges to README
5708261 Update build artifact retention to 30 days
129fa3a Minor cleanup to GitHub Actions
9efa0d1 Make release GitHub Action trigger on tag push
5bd0b69 Sort disabled pylint errors
3aacf4a Remove numpy from docs build requirements
c822914 Fix code coverage not locating source code
60e2eb3 Fix typo in power representation
6beb19b Update GitHub Actions for new packaging
8ac3da3 Update documentation for new packaging
5dbccb8 Move galois/ to src/galois/
a0e29c0 Use setuptools_scm for versioning
d8dde7d Convert from setup.cfg to pyproject.toml
8edc8b4 Use verify_isinstance() and verify_issubclass() throughout library
d2c458a Rename _overrides.py to _helper.py
a20bcfc Clean up galois.typing namespace
c75a080 Fix display of inherited docstring in VS Code tooltips
974f60e Move FieldArrayMeta into _fields/_meta.py
14e6561 Update Sphinx Immaterial version to correctly display inherited docstrings
0ddcbd7 Accept ArrayLike to FEC encode/decode methods
d0495cf Always return FieldArray from FEC encode/decode methods

Assets 2

28 Jul 21:37

github-actions

v0.0.32

bf1275a

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

Assets 2

24 Jul 14:42

github-actions

v0.0.31

d50f88b

galois v0.0.31

Released July 24, 2022

Breaking changes

Renamed FieldArray.Elements() classmethod to FieldArray.elements class property. This naming convention is more consistent with primitive_elements, units, quadratic_residues, and quadratic_non_residues. (#373)

>>> GF = galois.GF(3**2, display="poly")
>>> GF.elements
GF([     0,      1,      2,      α,  α + 1,  α + 2,     2α, 2α + 1,
    2α + 2], order=3^2)

Renamed BCH.systematic to BCH.is_systematic. (#376)
Renamed ReedSolomon.systematic to ReedSolomon.is_systematic. (#376)

Changes

Added support for polynomial composition in Poly.__call__(). (#377)

>>> GF = galois.GF(3**5)
>>> f = galois.Poly([37, 123, 0, 201], field=GF); f
Poly(37x^3 + 123x^2 + 201, GF(3^5))
>>> g = galois.Poly([55, 0, 1], field=GF); g
Poly(55x^2 + 1, GF(3^5))
>>> f(g)
Poly(77x^6 + 5x^4 + 104x^2 + 1, GF(3^5))

Added FieldArray.units class property. (#373)

>>> GF = galois.GF(3**2, display="poly")
>>> GF.units
GF([     1,      2,      α,  α + 1,  α + 2,     2α, 2α + 1, 2α + 2],
   order=3^2)

Documentation

Reworked API reference using Sphinx Immaterial's python-apigen. (#370)
Shortened website URLs to use directories. https://galois.readthedocs.io/en/v0.0.30/getting-started.html is converted to https://galois.readthedocs.io/en/v0.0.31/getting-started/. (#370)

Contributors

Matt Hostetter (@mhostetter)

Commits

d50f88b Version bump to 0.0.31
5a3b484 Add release notes for v0.0.31
4df5d7b Move primitive element functions into _fields/ folder
23337ad Clean up math equations
373a246 Remove math notation from individual numbers
4619383 Include rubrics in docstring in the local TOC
cb25b40 Update hyperlinks to use the new dirhtml style
e6acdfd Add polynomial composition unit test
30aa67e Add support for polynomial composition
0e63b7c Clarify type hint for primitive_element in GF()
5cf9161 Make poly evaluation at a matrix a private function
8d7a8b8 Make operand verification private functions
2f667d8 Make _convert_coeffs a private function
8613f22 Make _root_multiplicity a private function
371d7b1 Rename systematic property to is_systematic
e8f58ce Modify Sphinx Immaterial linkable parameter coloring
cae910d Indicate in docs that the dirhtml builder is used
2b2e5bf Fix search in dirhtml docs builds
eacf60f Add units and quadratic_residues to Array Creation page
9a4366c Remove OBE note on GF2 docstring
9a7ccb9 Add FieldArray.units class property
31ad02b Move FieldArray.Elements() to the FieldArray.elements property
1306f91 Make class property monkey patching for docs more algorithmic
f34038f Remove unnecessary autosummary templates
7a50cc1 Do not use "Tests" sections in classes
dd9476f Add note about polymorphic polynomial functions
9fc2b29 Clean up vector space method docstrings
d9f6fdb Remove unnecessary private methods from FieldArray
649bd10 Add basic docstrings to Array class properties
4635f81 Suppress private base classes from class documentation
ffee1bd Remove pandoc from CI docs build
ecefd5f Remove need for explicit forward references
4a5381c Use Sphinx Immaterial's conversion of type annotations
ce1bdde Use the Sphinx dirhtml builder for cleaner URLs
a0133d3 Use Sphinx Immaterial's python-apigen for API Reference

Assets 2

12 Jul 18:22

github-actions

v0.0.30

84ca4e1

galois v0.0.30

Released July 12, 2022

Changes

Added support for NumPy 1.22 with Numba 0.55.2. This allows users to upgrade NumPy and avoid recently-discovered vulnerabilities CVE-2021-34141, CVE-2021-41496, and CVE-2021-41495. (#366)

Made FieldArray.repr_table() more compact. (#367)

In [2]: GF = galois.GF(3**3)

In [3]: print(GF.repr_table())
 Power     Polynomial      Vector    Integer
------- --------------- ----------- ---------
   0           0         [0, 0, 0]      0
  x^0          1         [0, 0, 1]      1
  x^1          x         [0, 1, 0]      3
  x^2         x^2        [1, 0, 0]      9
  x^3        x + 2       [0, 1, 2]      5
  x^4       x^2 + 2x     [1, 2, 0]      15
  x^5     2x^2 + x + 2   [2, 1, 2]      23
  x^6     x^2 + x + 1    [1, 1, 1]      13
  x^7     x^2 + 2x + 2   [1, 2, 2]      17
  x^8       2x^2 + 2     [2, 0, 2]      20
  x^9        x + 1       [0, 1, 1]      4
  x^10      x^2 + x      [1, 1, 0]      12
  x^11    x^2 + x + 2    [1, 1, 2]      14
  x^12      x^2 + 2      [1, 0, 2]      11
  x^13         2         [0, 0, 2]      2
  x^14         2x        [0, 2, 0]      6
  x^15        2x^2       [2, 0, 0]      18
  x^16       2x + 1      [0, 2, 1]      7
  x^17      2x^2 + x     [2, 1, 0]      21
  x^18    x^2 + 2x + 1   [1, 2, 1]      16
  x^19   2x^2 + 2x + 2   [2, 2, 2]      26
  x^20    2x^2 + x + 1   [2, 1, 1]      22
  x^21      x^2 + 1      [1, 0, 1]      10
  x^22       2x + 2      [0, 2, 2]      8
  x^23     2x^2 + 2x     [2, 2, 0]      24
  x^24   2x^2 + 2x + 1   [2, 2, 1]      25
  x^25      2x^2 + 1     [2, 0, 1]      19

Made FieldArray.arithmetic_table() more compact. (#367)

In [2]: GF = galois.GF(13)

In [3]: print(GF.arithmetic_table("*"))
x * y |  0   1   2   3   4   5   6   7   8   9  10  11  12
------|----------------------------------------------------
    0 |  0   0   0   0   0   0   0   0   0   0   0   0   0
    1 |  0   1   2   3   4   5   6   7   8   9  10  11  12
    2 |  0   2   4   6   8  10  12   1   3   5   7   9  11
    3 |  0   3   6   9  12   2   5   8  11   1   4   7  10
    4 |  0   4   8  12   3   7  11   2   6  10   1   5   9
    5 |  0   5  10   2   7  12   4   9   1   6  11   3   8
    6 |  0   6  12   5  11   4  10   3   9   2   8   1   7
    7 |  0   7   1   8   2   9   3  10   4  11   5  12   6
    8 |  0   8   3  11   6   1   9   4  12   7   2  10   5
    9 |  0   9   5   1  10   6   2  11   7   3  12   8   4
   10 |  0  10   7   4   1  11   8   5   2  12   9   6   3
   11 |  0  11   9   7   5   3   1  12  10   8   6   4   2
   12 |  0  12  11  10   9   8   7   6   5   4   3   2   1

Contributors

Iyán Méndez Veiga (@iyanmv)
Matt Hostetter (@mhostetter)

Commits

84ca4e1 Version bump to 0.0.30
740f888 Add release notes for v0.0.30
1deead9 Pin Sphinx to v4.5 for docs build
ec52ec3 Lower minimum required NumPy versions
6b6a20f Add type hints to ufunc dispatchers
afb5938 Add Python syntax highlighting to inline code
501a323 Use mathjax in GitHub-flavored markdown
0c8e5c8 Update pylint and linter errors
5c1dc7b Make arithmetic_table() output more compact
a05b58a Make repr_table() output more compact
d7d6988 Add support for numpy 1.22

Assets 2

18 May 14:12

github-actions

v0.0.29

efc645e

galois v0.0.29

Released May 18, 2022

Breaking changes

Moved galois.square_free_factorization() function into Poly.square_free_factors() method. (#362)
Moved galois.distinct_degree_factorization() function into Poly.distinct_degree_factors() method. (#362)
Moved galois.equal_degree_factorization() function into Poly.equal_degree_factors() method. (#362)
Moved galois.is_irreducible() function into Poly.is_irreducible() method. This is a method, not property, to indicate it is a computationally-expensive operation. (#362)
Moved galois.is_primitive() function into Poly.is_primitive() method. This is a method, not property, to indicate it is a computationally-expensive operation. (#362)
Moved galois.is_monic() function into Poly.is_monic property. (#362)

Changes

Added galois.set_printoptions() function to modify package-wide printing options. This is the equivalent of np.set_printoptions(). (#363)

In [1]: GF = galois.GF(3**5, display="poly")

In [2]: a = GF([109, 83]); a
Out[2]: GF([α^4 + α^3 + 1,       α^4 + 2], order=3^5)

In [3]: f = galois.Poly([3, 0, 5, 2], field=galois.GF(7)); f
Out[3]: Poly(3x^3 + 5x + 2, GF(7))

In [4]: galois.set_printoptions(coeffs="asc")

In [5]: a
Out[5]: GF([1 + α^3 + α^4,       2 + α^4], order=3^5)

In [6]: f
Out[6]: Poly(2 + 5x + 3x^3, GF(7))

Added galois.get_printoptions() function to return the current package-wide printing options. This is the equivalent of np.get_printoptions(). (#363)
Added galois.printoptions() context manager to modify printing options inside of a with statement. This is the equivalent of np.printoptions(). (#363)
Added a separate Poly.factors() method, in addition to the polymorphic galois.factors(). (#362)
Added a separate Poly.is_square_free() method, in addition to the polymorphic galois.is_square_free(). This is a method, not property, to indicate it is a computationally-expensive operation. (#362)
Fixed a bug (believed to be introduced in v0.0.26) where Poly.degree occasionally returned np.int64 instead of int. This could cause overflow in certain large integer operations (e.g., computing $q^m$ when determining if a degree-$m$ polynomial over $\mathrm{GF}(q)$ is irreducible). When the integer overflowed, this created erroneous results. (#360, #361)
Increased code coverage.

Contributors

Matt Hostetter (@mhostetter)

Commits

efc645e Version bump to 0.0.29
810bca8 Add release notes for v0.0.29
db27b73 Use consistent section capitalization
bb75879 Use decorator for the FieldArray.display() context manager
992c215 Add galois.printoptions() context manager
b77cabf Modify Sphinx explicit references
b2987bc Add set_printoptions() tips in docs
3d72707 Add get/set_printoptions() functions
5c03168 Add index page to docs
7356465 Update documentation prose
a8d5086 Update minimum Sphinx version
cd312a1 Verify factored polynomials are indeed square-free
a64b771 Add Poly.is_square_free()
9f029c1 Move galois.is_primitive() to Poly.is_primitive()
008b971 Move galois.is_irreducible() to Poly.is_irreducible()
89e8ec7 Move galois.is_monic() to the Poly.is_monic property
e0a3e24 Make polynomial factorization functions Poly methods
062a118 Add Poly.factors() method
fe379c3 Add additional unit test
3eeb4ec Always return int from Poly.degree
c5d930d Increase NTT code coverage
eadc6a3 Improve class factory code coverage
94db928 Increase primitive element code coverage
26e91c5 Increase Array code coverage
450fb3e Improve LFSR code coverage

Assets 2

11 May 18:25

github-actions

v0.0.28

4e0a68b

galois v0.0.28

Released May 11, 2022

Changes

Modified JIT-compiled functions to use explicit calculation or lookup tables. Previously, JIT functions only used explicit calculation routines. Now all ufuncs and functions are JIT-compiled once on first invocation, but use the current ufunc_mode to determine the arithmetic used. This provides a significant performance boost for fields which use lookup tables by default. The greatest performance improvement can be seen in $\mathrm{GF}(p^m)$ fields. (#354)

Polynomial multiplication is 210% faster.

In [2]: GF = galois.GF(7**5)

In [3]: f = galois.Poly.Random(10, seed=1, field=GF)

In [4]: g = galois.Poly.Random(5, seed=2, field=GF)

# v0.0.27
In [6]: %timeit f * g
168 µs ± 722 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

# v0.0.28
In [6]: %timeit f * g
54 µs ± 574 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Polynomial modular exponentiation is 5,310% faster.

# v0.0.27
In [8]: %timeit pow(f, 123456789, g)
5.9 ms ± 9.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# v0.0.28
In [8]: %timeit pow(f, 123456789, g)
109 µs ± 527 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Matrix multiplication is 6,690% faster.

In [9]: A = GF.Random((100, 100), seed=1)

In [10]: B = GF.Random((100, 100), seed=2)

# v0.0.27
In [12]: %timeit A @ B
1.1 s ± 4.76 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# v0.0.28
In [12]: %timeit A @ B
16.2 ms ± 50.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Simplified FieldArray subclasses' repr() and str(). Since these classes may be displayed in error logs, a concise representation is necessary. (#350)
```
>>> GF = galois.GF(3**5)
>>> GF
<class 'galois.GF(3^5)'>
```

Added back FieldArray.properties for a detailed description of the finite field's relevant properties. (#350)

>>> GF = galois.GF(3**5)
>>> print(GF.properties)
Galois Field:
  name: GF(3^5)
  characteristic: 3
  degree: 5
  order: 243
  irreducible_poly: x^5 + 2x + 1
  is_primitive_poly: True
  primitive_element: x

Increased code coverage.
Various documentation fixes.

Contributors

Matt Hostetter (@mhostetter)

Commits

4e0a68b Version bump to 0.0.28
ab0163f Add release notes for v0.0.28
7a4b6b2 Ensure GF(2) is compiled by default
d488ceb Add polynomial "right" arithmetic
662e294 Add remainder unit test
0bc0198 Add divmod unit test
0f2c7ea Indicate no test coverage where necessary
c98df85 Fix indentation of code blocks in bulleted lists
8d71f8a Fix hiding dot() method from Array API docs
2078aa9 Provide an additional benchmark example
b5493e9 Adjust benchmark run array lengths
ffae1ae Create and utilize ufunc and function dispatchers
fc9265f Rework polynomial JIT function structure
2ca4d16 Rework FEC code JIT function structure
220a669 Fix Literal defaults in overloaded functions
b8f0839 Rename Ufuncs to UFuncs
25064e9 Always dynamically compile ufuncs
e356fb9 Update sphinx-immaterial version
bcc8cba Fix incorrect reference
f828267 Clean up explicit calculation inheritance
aee74b7 Clean up class str() and repr()
c8372bb Clean up API table of contents
1ddbfeb Prevent "Parameters" sections in docs API
657326f Update API TOC structure
0788cf3 Fix galois.typing module documentation links
c8ab245 Clean up Array default monkey patching
8885574 Improve type hints
6b34647 Rename mixin classes
6aa410a Move polynomial JIT functions into their own file
6d5b872 Restructure linear algebra code
124aeb1 Inherit from ABC for abstract base classes
152366a Move ufunc- and function-overridding code
01cd714 Use public properties instead of internal attributes
e9d6806 Move placeholder factory functions into _factory.py
eefce37 Move all type aliases into typing.py
97a391d Move ArrayMeta to _meta.py
03919da Merge metaclasses into one in _meta.py
39ec643 Additional fix when monkey-patching for docs
55c5d8c Fix missing type signatures

Assets 2

22 Apr 19:51

github-actions

v0.0.27

2284442

galois v0.0.27

Released April 22, 2022

Breaking Changes

Sunsetted support for Python 3.6. This was necessary to support forward references with from __future__ import annotations (available in Python 3.7+). That import is required to support the type aliases in the new galois.typing subpackage. (#339)
Removed the FieldClass metaclass from the public API. It was previously included due to an inability of Sphinx to document class properties. In this release, we monkey patched Sphinx to document all classmethods, class properties, and instance methods in FieldArray itself. (#343)
- Use issubclass(GF, galois.FieldArray) anywhere isinstance(GF, galois.FieldClass) was previously used.
- Annotate with Type[galois.FieldArray] anywhere galois.FieldClass was previously used.

Changes

Added the galois.typing subpackage, similar to np.typing. It contains type hints for common coercible data types used throughout the library, including ElementLike, ArrayLike, and PolyLike. With these type hints, the annotations are simpler and more clear. (#339)
Modified functions to accept coercible data types wherever possible. For example, functions now accept PolyLike objects instead of strictly Poly instances. (#339)
Added Array which is an abstract base class of FieldArray (and RingArray in a future release). (#336)

Added support for the DFT over any finite field using np.fft.fft() and np.fft.ifft(). (#335)

>>> x
GF([127, 191,  69,  35, 221, 242, 193, 108,  72, 102,  80, 163,  13,  74,
    218, 159, 207,  12, 159, 129,  92,  71], order=3^5)
>>> X = np.fft.fft(x); X
GF([ 16,  17,  20, 137,  58, 166, 178,  52,  19, 109, 115,  93,  99, 214,
    187, 235, 195,  96, 232,  45, 241,  24], order=3^5)
>>> np.fft.ifft(X)
GF([127, 191,  69,  35, 221, 242, 193, 108,  72, 102,  80, 163,  13,  74,
    218, 159, 207,  12, 159, 129,  92,  71], order=3^5)

Implemented the Cooley-Tukey radix-2 $O(N\ \textrm{log}(N))$ algorithm for the NTT and JIT compiled it. (#333)

In [2]: x = list(range(1, 1024 + 1))

# v0.0.26
In [4]: %timeit X = galois.ntt(x)
5.2 ms ± 121 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# v0.0.27
In [4]: %timeit X = galois.ntt(x)
695 µs ± 4.56 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Added the FieldArray.primitive_root_of_unity() classmethod. (#333)

>>> GF = galois.GF(3**5)
>>> GF.primitive_root_of_unity(22)
GF(39, order=3^5)

Added the FieldArray.primitive_roots_of_unity() classmethod. (#333)

>>> GF = galois.GF(3**5)
>>> GF.primitive_roots_of_unity(22)
GF([ 14,  39,  44,  59, 109, 114, 136, 200, 206, 226], order=3^5)

Made 0-th degree coefficients more differentiated when using the polynomial element representation. (#328)

# v0.0.26
>>> print(f)
(α^2 + α + 1)x^4 + (α^3)x + α^3 + 2α^2 + 2α + 2
# v0.0.27
>>> print(f)
(α^2 + α + 1)x^4 + (α^3)x + (α^3 + 2α^2 + 2α + 2)

Restructured code base for clarity. (#336)
Fixed display of overloaded functions in API reference. (#337)
Fixed broken "References" sections in API reference. (#281)
Fixed other small bugs.

Contributors

Matt Hostetter (@mhostetter)

Commits

2284442 Version bump to 0.0.27
db5c312 Add release notes for v0.0.27
f5376fd Monkey-patch class properties in conf.py
e3d7029 Clean-up .. math:: directives
d00abbc Hide Array and GF2 inherited methods and properties
98c2272 Update README
d036af6 Remove metaclasses from API
7a3a2e6 Replace recommonmark with myst-parser
429a920 Fix error in ElementLike type hint
1e23c36 Use short object references in docs
96376b9 Add galois.typing subpackage and simplify type hints
f08101e Remove support for Python 3.6
c2766b7 Differentiate Reed-Solomon repr() and str()
6046729 Differentiate BCH repr() and str()
da5c8c9 Remove numba from inter-Sphinx mapping
0c34f4f Fix bug in Poly.degree when poly was zero
a76c9f3 Simplify private function names
2f8c905 Fix improper circular import
4a8f34e Display overloaded signatures in docs
7259161 Move irreducible/primitve poly and primitive element functions into _polys/ folder
de87b1f Rename FieldClass to FieldArrayClass
b2a28fc Restructure polynomial code
630e638 Restructure code and import hierarchy
5d8d29e Update docs to add info about the FFT
1435b22 Add unit tests for the FFT over arbitrary fields
e80d1b3 Support the DFT over any finite field
16544b9 Fix FFT recursion for non-compiled case
fcd7c97 Properly set module for pollard_rho()
42217c8 Do not expose LRU cache wrappers in public API
0719969 Implement the radix-2 Cooley-Tukey FFT algorithm
ab58cde JIT compile the O(N^2) NTT
d5f9e94 Remove pylint pin before v2.13.0
8ae0848 Cached primitive elements are calculation
481b09f Clean-up class private attributes
29281f9 Add FieldClass.primitive_roots_of_unity()
01fe13c Add FieldClass.primitve_root_of_unity()
592da2c Update Google Analytics config of sphinx-immaterial
9587e30 Fix "References" sections in docstrings
05b2e4e Add social links to bottom of webpage
995b76b Add Jupyter notebook checkpoints to gitignore
d4739e3 Add virtual environments to gitignore
303418b Add () around 0-degree coefficient if it has a + separator
5f011ae Fix percentages in release notes for v0.0.26

Assets 2

30 Mar 22:46

github-actions

v0.0.26

53c622e

galois v0.0.26

Released March 30, 2022

Breaking Changes

Removed the Poly.copy() method as it was unnecessary. Polynomial objects are immutable. Use g = f wherever g = f.copy() was previously used. (#320)
Disabled true division f / g on polynomials since true division was not actually being performed. Use floor division f // g moving forward. (#312)
Refactored irreducible_polys() to return an iterator rather than list. Use list(irreducible_polys(...)) to obtain the previous output. (#325)
Refactored primitive_polys() to return an iterator rather than list. Use list(primitive_polys(...)) to obtain the previous output. (#325)
Refactored primitive_root() and primitive_roots(). (#325)
- Added method keyword argument and removed reverse from primitive_root(). Use primitive_root(..., method="max") where primitive_root(..., reverse=True) was previously used.
- Refactored primitive_roots() to now return an iterator rather than list. Use list(primitive_roots(...)) to obtain the previous output.
Refactored primitive_element() and primitive_elements(). (#325)
- Added method keyword argument to primitive_element().
- Removed start, stop, and reverse arguments from both functions.
Search functions now raise RuntimeError instead of returning None when failing to find an answer. This applies to primitive_root(), pollard_p1(), and pollard_rho(). (#312)

Changes

The galois.Poly class no longer returns subclasses BinaryPoly, DensePoly, and SparsePoly. Instead, only Poly classes are returned. The classes otherwise operate the same. (#320)

Made Galois field array creation much more efficient by avoiding redundant element verification. (#317)

Scalar creation is 625% faster.

In [2]: GF = galois.GF(3**5)

# v0.0.25
In [3]: %timeit GF(10)
21.2 µs ± 181 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

# v0.0.26
In [3]: %timeit GF(10)
2.88 µs ± 8.03 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

Nested iterable array creation is 150% faster.

# v0.0.25
In [4]: %timeit GF([[10, 20], [30, 40]])
53.6 µs ± 436 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

# v0.0.26
In [4]: %timeit GF([[10, 20], [30, 40]])
20.9 µs ± 11.2 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Nested iterable (with strings) array creation is 25% faster.

# v0.0.25
In [5]: %timeit GF([[10, "2x^2 + 2"], ["x^3 + x", 40]])
67.9 µs ± 910 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

# v0.0.26
In [5]: %timeit GF([[10, "2x^2 + 2"], ["x^3 + x", 40]])
54.7 µs ± 16.3 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Made array arithmetic 35% faster by avoiding unnecessary element verification of outputs. (#309)

In [2]: GF = galois.GF(3**5)

In [3]: x = GF.Random((10_000), seed=1)

In [4]: y = GF.Random((10_000), seed=2)

# v0.0.25
In [6]: %timeit x * y
39.4 µs ± 237 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

# v0.0.26
In [6]: %timeit x * y
28.8 µs ± 172 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Made polynomial arithmetic over binary fields 10,900% faster by making polynomial creation from integers much more efficient. (#320)

In [5]: f
Out[5]: Poly(x^10 + x^9 + x^6 + x^5 + x^3 + x, GF(2))

In [6]: g
Out[6]: Poly(x^10 + x^7 + x^4 + 1, GF(2))

# v0.0.25
In [7]: %timeit f * g
283 µs ± 6.31 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

# v0.0.26
In [7]: %timeit f * g
2.57 µs ± 54.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

JIT-compiled polynomial modular exponentiation. (#306)

Binary fields are 14,225% faster.

In [5]: f
Out[5]: Poly(x^10 + x^9 + x^6 + x^5 + x^3 + x, GF(2))

In [6]: g
Out[6]: Poly(x^5 + x^2, GF(2))

# v0.0.25
In [7]: %timeit pow(f, 123456789, g)
19.2 ms ± 206 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

# v0.0.26
In [7]: %timeit pow(f, 123456789, g)
134 µs ± 2.21 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Other fields are 325% faster.

In [6]: f
Out[6]: Poly(242x^10 + 216x^9 + 32x^8 + 114x^7 + 230x^6 + 179x^5 + 5x^4 + 124x^3 + 96x^2 + 159x + 77, GF(3^5))

In [7]: g
Out[7]: Poly(183x^5 + 83x^4 + 101x^3 + 203x^2 + 68x + 2, GF(3^5))

# v0.0.25
In [8]: %timeit pow(f, 123456789, g)
17.6 ms ± 61.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# v0.0.26
In [8]: %timeit pow(f, 123456789, g)
4.19 ms ± 11.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Made irreducible and primitive polynomial search routines faster. (#306, #309, #317, #320)

Binary fields are 1,950% faster.

# v0.0.25
In [2]: %time f = galois.primitive_poly(2, 14)
CPU times: user 296 ms, sys: 70.9 ms, total: 367 ms
Wall time: 313 ms

# v0.0.26
In [2]: %time f = galois.primitive_poly(2, 14)
CPU times: user 14.7 ms, sys: 5.53 ms, total: 20.2 ms
Wall time: 15.3 ms

Other fields are 400% faster.

# v0.0.25
In [5]: %time f = galois.primitive_poly(7, 10)
CPU times: user 2.22 s, sys: 0 ns, total: 2.22 s
Wall time: 2.21 s

# v0.0.26
In [4]: %time f = galois.primitive_poly(7, 10)
CPU times: user 442 ms, sys: 0 ns, total: 442 ms
Wall time: 439 ms

Made FieldArray.Vector() 100% faster and FieldArray.vector() 25% faster by making better use of divmod() when converting between integer and vector representations. (#322)

Contributors

Matt Hostetter (@mhostetter)

Commits

53c622e Version bump to 0.0.26
895053a Add release notes for v0.0.26
348c61a Update performance pages with latest speeds
429f0d8 Remove jinja2 pin since it was resolved in sphinx-immaterial upstream
810a3de Add "See Also" sections to docstrings
6ab4a49 Refactor primitive_element() and primitive_elements()
1273d16 Add private constructor Poly._PolyLike()
fc52679 Refactor primitive_roots() to return an iterator
4985853 Memoize euler_phi()
645f755 Refactor primitve_polys() to return an iterator
30d554f Refactor irreducible_polys() to return an iterator
7d9f642 Raise RuntimeError rather than return None for pollard_rho()
7b3711a Raise RuntimeError rather than return None for pollard_p1()
9a38498 Ensure dtype=object arrays always have int objects, even after assignment
1d30fb9 Better use of divmod() in int/poly conversion for GF(p^m) fields
a055e5b Speed-up Vector() and vector() using better use of divmod()
1a81be4 Adjust dense/sparse poly arithmetic threshold
864c977 Refactor Poly inheritance of BinaryPoly, DensePoly, and SparsePoly
cf84272 Remove brackets around the 0-th degree coefficient in poly strings
3ebc562 Make poly/int conversion more efficient
05ec7b4 Remove Poly.copy() method
a454532 Pin pylint before v2.13.0
b734de3 Speed-up array creation, especially 0-D arrays
74305d1 Ignore dtype check with performing an internal "cheap view"
c2e0404 Avoid jinja2 bug until fixed in sphinx-immaterial
1c99193 Fix typo in Getting Started guide
8bbb1ee Disable true division on polynomials
d86609b Fix NumPy capitalization in comments
a9e1f9b Remove function that no longer exists from reference list
5354a1f Enable arbitarily-large exponents to JIT-compiled poly pow()
b6347b6 Avoid array element range verification for internal .view(GF) conversions
9b1849d Cleanup FieldClass.display() context manager
fb20569 Modify CSS rules so sphinx-design tabs match the theme better
5869373 Fix BibTeX label
0999e4e Fix typo in Galois LFSR step docstring
a7624fc JIT compile polynomial modular exponentiation
dc5dca8 JIT compile separate polynomial div and mod functions
fa43cc1 Save 1 unnecessary calculation in poly divmod

Assets 2

Releases: mhostetter/galois

galois v0.1.1

Changes

Contributors

Commits

Uh oh!

galois v0.1.0

Changes

Contributors

Commits

Uh oh!

galois v0.0.33

Breaking changes

Changes

Contributors

Commits

Uh oh!

galois v0.0.32

Breaking changes

Changes

Contributors

Commits

Uh oh!

galois v0.0.31

Breaking changes

Changes

Documentation

Contributors

Commits

Uh oh!

galois v0.0.30

Changes

Contributors

Commits

Uh oh!

galois v0.0.29

Breaking changes

Changes

Contributors

Commits

Uh oh!

galois v0.0.28

Changes

Contributors

Commits

Uh oh!

galois v0.0.27

Breaking Changes

Changes

Contributors

Commits

Uh oh!

galois v0.0.26

Breaking Changes

Changes

Contributors

Commits

Uh oh!