galois v0.3.3

Released February 1, 2023

Changes

• Added a terms keyword argument to irreducible_poly(), irreducible_polys(), primitive_poly(), and primitive_polys() to find a polynomial with a desired number of non-zero terms. This may be set to an integer or to "min". (#463)

  >>> import galois
  >>> galois.irreducible_poly(7, 9)
  Poly(x^9 + 2, GF(7))
  >>> galois.irreducible_poly(7, 9, terms=3)
  Poly(x^9 + x + 1, GF(7))
  >>> galois.primitive_poly(7, 9)
  Poly(x^9 + x^2 + x + 2, GF(7))
  >>> galois.primitive_poly(7, 9, terms="min")
  Poly(x^9 + 3x^2 + 4, GF(7))

• Added a database of binary irreducible polynomials with degrees less than 10,000. These polynomials are lexicographically-first and have the minimum number of non-zero terms. The database is accessed in irreducible_poly() when terms="min" and method="min". (#462)

  In [1]: import galois
  
  # Manual search
  In [2]: %time galois.irreducible_poly(2, 1001)
  CPU times: user 6.8 s, sys: 0 ns, total: 6.8 s
  Wall time: 6.81 s
  Out[2]: Poly(x^1001 + x^5 + x^3 + x + 1, GF(2))
  
  # With the database
  In [3]: %time galois.irreducible_poly(2, 1001, terms="min")
  CPU times: user 745 µs, sys: 0 ns, total: 745 µs
  Wall time: 1.4 ms
  Out[3]: Poly(x^1001 + x^17 + 1, GF(2))

• Memoized expensive polynomial tests Poly.is_irreducible() and Poly.is_primitive(). Now, the expense of those calculations for a given polynomial is only incurred once. (#470)

  In [1]: import galois
  
  In [2]: f = galois.Poly.Str("x^1001 + x^17 + 1"); f
  Out[2]: Poly(x^1001 + x^17 + 1, GF(2))
  
  In [3]: %time f.is_irreducible()
  CPU times: user 1.05 s, sys: 3.47 ms, total: 1.05 s
  Wall time: 1.06 s
  Out[3]: True
  
  In [4]: %time f.is_irreducible()
  CPU times: user 57 µs, sys: 30 µs, total: 87 µs
  Wall time: 68.2 µs
  Out[4]: True

• Added tests for Conway polynomials Poly.is_conway() and Poly.is_conway_consistent(). (#469)
• Added the ability to manually search for a Conway polynomial if it is not found in Frank Luebeck's database, using conway_poly(p, m, search=True). (#469)
• Various documentation improvements.

Contributors

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

Commits

db0fde5 Add release notes for v0.3.3
1fafb79 Fix formatting
09463a7 Fix pylint errors
bbc4133 Speed up database calls by sharing a connection and cursor
4339f25 Add performance note about the irreducible poly database
0ec2836 Add hyperlink to additional linear algebra methods
f14901b Add hyperlinks in README
be2e401 Make conway_polys.db only contain non-zero coefficients
b61044a Clean up polynomial LUTs
4177128 Simplify database interfaces
f2cb05a Remove use_database kwarg from irreducible_poly()
b5eec8f Update method versus property documentation comment
58dcccb Add slow performance warnings for manual Conway poly search
a4d6a5d Add Conway polynomial manual search unit tests
c3bc7b1 Add manual Conway polynomial test and search functions
ff28d97 Clean up recursive function
77f8316 Add unit tests
89d8086 Use IrreduciblePolyDatabase with terms="min"
bf6010b Add irreducible polynomials for GF(2^m)
9153adb Silence erroneous pylint error
4c61dad Better solution for avoiding circular imports
9485b5d Minor variable name tweak
021ec94 Minor terminology tweak
c2d5d7f Move Lagrange polys to _lagrange.py
e2eee57 Fix type hint
e228261 Preserve intellisense autocompletion and brief docstring of patched Poly methods
289857a Remove unused imports
0dffee7 Memoize Poly.is_primitive()
9392bd4 Memoize Poly.is_irreducible()
460cec5 Simplify Poly hash
b2f33f1 Move polynomial search functions into _search.py
4804c08 Move Conway polys to their own module
f174079 Reorganize poly factors methods
9d846e2 Reorganize irreducibility and primitivity tests
1a863ef Sort keywords
ca97968 Organize class items better in docs
b87dd04 Fix docs links to FieldArray.compile() and FieldArray.repr()
95327a1 Modify slow performance warnings
28a8108 Add performance-related custom admonitions
0068901 Move polynomial deterministic search into _poly.py
534de4e Make search for a random irreducible/primitive polynomial much more efficient
a82c9d0 Move common irreducible/primitive poly functions to _poly.py
4cc9fbc Add a terms="min" option to irreducible/primitive poly functions
a5344cf Make search for polynomials of fixed-term much more efficient
f4b908e Add terms kwarg to primitive poly functions
7ab1c02 Add terms kwarg to irreducible poly functions
44cc214 Parse Google docstring "See Also" sections as if they were NumPy docstring
7b3aed9 Clean up docstrings
100363b Change max line length to 120
41b17f0 Use Google docstrings instead of NumPy docstrings
1c89c5e Add pytest-benchmark back to [dev] dependencies
87c8850 Upgrade to Sphinx Immaterial 0.11.2
1d5ffcf Update copyright
7bb4da3 Fix typo in pollard_p1() docstring

galois v0.3.2

Released December 18, 2022

Changes

• Added a prime factorization database for $n = b^k \pm 1$, with $b \in {2, 3, 5, 6, 7, 10, 11, 12}$. The factorizations are from the Cunningham Book. This speeds up the creation of large finite fields. (#452)

In [1]: import galois

# v0.3.1
In [2]: %time galois.factors(2**256 - 1)
# Took forever...

# v0.3.2
In [2]: %time galois.factors(2**256 - 1)
Wall time: 1 ms
Out[2]:
([3,
  5,
  17,
  257,
  641,
  65537,
  274177,
  6700417,
  67280421310721,
  59649589127497217,
  5704689200685129054721],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

• Added speed-up when factoring powers of small primes. This speeds up the creation of large finite fields. (#454)

In [1]: import galois

# v0.3.1
In [2]: %time galois.factors(2**471)
Wall time: 4.18 s
Out[2]: ([2], [471])

# v0.3.2
In [2]: %time galois.factors(2**471)
Wall time: 2 ms
Out[2]: ([2], [471])

• Added four additional Mersenne primes that were discovered between 2013-2018. (#452)

Contributors

• Matt Hostetter (@mhostetter)

Commits

2a006d1 Add release notes for v0.3.2
5b9d50a Add check in perfect_power() to see if n is a prime power for small primes
3eb1cb6 Add the Cunningham Book to the acknowledgements
50899c6 Add prime factors database
15e4d96 Clean up conway poly script
458f20e Fix typo in pollard_rho docstring
c3bbab8 Update database path for Conway poly database
dabb41e Add newly discovered Mersenne exponents

galois v0.3.1

Released December 12, 2022

Changes

• Fixed a bug in the Pollard $\rho$ factorization algorithm that caused an occasional infinite loop. (#450)

In [1]: import galois

# v0.3.0
In [2]: %time galois.GF(2400610585866217)
# Never returns...

# v0.3.1
In [2]: %time galois.GF(2400610585866217)
Wall time: 96 ms
Out[2]: <class 'galois.GF(2400610585866217)'>

• Formatted the code and unit tests with black and isort. (#446, #449)

Contributors

• Matt Hostetter (@mhostetter)
• @pivis

Commits

638f0aa Add release notes for v0.3.1
deb4c1e Fix a bug in factorization function causing infinite loops in rare cases
bd9e576 Lint unit tests in CI
b8c3a09 Lint tests/ with pylint
6544fb4 Format tests/ with black
0c9133c Skip formatting on occasional long lines
a843fdc Resolve missing-module-docstring pylint errors
37af083 Resolve invalid-unary-operand-type pylint errors
b19b4e7 Resolve not-callable pylint errors
62bf749 Resolve unsubscriptable-object pylint errors
0c7392d Resolve eval-used pylint errors
19de2f5 Resolve unnecessary-lambda-assignment pylint errors
a0a1115 Resolve no-else-return pylint errors
1801189 Resolve consider-using-enumerate pylint errors
55eb55c Use pylint to check for lines that are too long
9019123 Sort imports with isort
82f5fee Run black in the CI
10f8183 Format codebase with black
253ce89 Add GitHub star suggestion
41dcc7d Update performance docs for faster matrix multiplication

galois v0.3.0

Released December 9, 2022

Breaking changes

• Increased minimum NumPy version to 1.21.0. (#441)
• Increased minimum Numba version to 0.55.0 (#441)
• Modified galois.GF() and galois.Field() so that keyword arguments irreducible_poly, primitive_element, verify, compile, and repr may no longer be passed as positional arguments. (#442)

Changes

• Added a galois.GF(p, m) call signature in addition to galois.GF(p**m). This also applies to galois.Field(). Separately specifying $p$ and $m$ eliminates the need to factor the order $p^m$ in very large finite fields. (#442)

>>> import galois
# This is faster than galois.GF(2**409)
>>> GF = galois.GF(2, 409)
>>> print(GF.properties)
Galois Field:
  name: GF(2^409)
  characteristic: 2
  degree: 409
  order: 1322111937580497197903830616065542079656809365928562438569297590548811582472622691650378420879430569695182424050046716608512
  irreducible_poly: x^409 + x^7 + x^5 + x^3 + 1
  is_primitive_poly: True
  primitive_element: x

• Optimized matrix multiplication by parallelizing across multiple cores. (#440)

In [1]: import galois

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

In [3]: A = GF.Random((300, 400), seed=1)

In [4]: B = GF.Random((400, 500), seed=2)

# v0.2.0
In [5]: %timeit A @ B
664 ms ± 3.31 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# v0.3.0
In [5]: %timeit A @ B
79.1 ms ± 7.32 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

• Optimized polynomial evaluation by parallelizing across multiple cores. (#440)

In [1]: import galois

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

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

In [4]: x = GF.Random(100_000, seed=1)

# v0.2.0
In [5]: %timeit f(x)
776 ms ± 2.12 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# v0.3.0
In [5]: %timeit f(x)
13.9 ms ± 2.51 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

• Fixed an occasional arithmetic type error in binary extension fields $\mathrm{GF}(2^m)$ when using the built-in np.bitwise_xor(). (#441)

Contributors

• Matt Hostetter (@mhostetter)

Commits

648aa06 Add release notes for v0.3.0
87ec4fc Fix incorrect GF on Array Classes page
4679e20 JIT parallelize polynomial evaluation
dacc9e4 JIT parallelize matrix multiplication
4c82984 Enable parallel processing of JIT functions
153614a Document ways to speed up large field construction
04e77a2 Add galois.GF(p, m) optional call signature
13770e0 Fix overflow bug with "python-calculate" using native NumPy ufuncs
38f2799 Bump minimum NumPy version to 1.21 and Numba version to 0.55

galois v0.2.0

Released November 17, 2022

Breaking changes

• Refactored FEC classes and usage. (#413, #435)

  • Modified BCH codes to support q-ary, non-primitive, and non narrow-sense codes.

  • Modified ReedSolomon codes to support non-primitive codes.

  • Enabled instantiation of a BCH or ReedSolomon code by specifying (n, k) or (n, d).

  • Removed parity_only=False keyword argument from FEC encode() methods and replaced with output="codeword".

  • Removed bch_valid_codes() from the API. Instead, use galois.BCH(n, d=d) to find and create a BCH code with codeword size n and design distance d. For example, here is how to find various code sizes of primitive BCH codes over GF(5).

    >>> import galois
    >>> GF = galois.GF(5)
    >>> for d in range(3, 10):
    ...     bch = galois.BCH(5**2 - 1, d=d, field=GF)
    ...     print(repr(bch))
    ... 
    <BCH Code: [24, 20, 3] over GF(5)>
    <BCH Code: [24, 18, 4] over GF(5)>
    <BCH Code: [24, 16, 5] over GF(5)>
    <BCH Code: [24, 16, 6] over GF(5)>
    <BCH Code: [24, 15, 7] over GF(5)>
    <BCH Code: [24, 13, 8] over GF(5)>
    <BCH Code: [24, 11, 9] over GF(5)>

  • Removed generator_to_parity_check_matrix(), parity_check_to_generator_matrix(), poly_to_generator_matrix(), and roots_to_parity_check_matrix() from the API.

• Renamed properties and methods for changing the finite field element representation. (#436)

  • Renamed display keyword argument in GF() to repr.

  • Renamed FieldArray.display() classmethod to FieldArray.repr().

  • Renamed FieldArray.display_mode property to FieldArray.element_repr.

    >>> import galois
    >>> GF = galois.GF(3**4, repr="poly")
    >>> x = GF.Random(2, seed=1); x
    GF([2α^3 + 2α^2 + 2α + 2,          2α^3 + 2α^2], order=3^4)
    >>> GF.repr("power"); x
    GF([α^46, α^70], order=3^4)
    >>> GF.element_repr
    'power'

Changes

• Added output="codeword" keyword argument to FEC encode() methods. (#435)
• Added output="message" keyword argument to FEC decode() methods. (#435)
• Standardized NumPy scalar return types (np.bool_ and np.int64) to Python types (bool and int). For example, in FieldArray.multiplicative_order(). (#437)
• Improved documentation and published docs for pre-release versions (e.g., v0.3.x).

Contributors

• Matt Hostetter (@mhostetter)

Commits

a182763 Add release notes for v0.2.0
ba3d3d3 Minor clarifications in docs
6ae4a78 Standardize scalar return types
f0d92b3 Fix typos
07783e2 Fix ValueError messages
475212d Modify admonition types
e876aa7 Conform dropdown admonitions to new Sphinx Immaterial
66e6c1e Change seealso admonition icon
4cbbf30 Fix docs error of mismatched parameter names
4d56903 Add abstract admonitions
ebbb197 Add Galois quote
cfb8f2d Update Sphinx Immaterial to latest
419df85 Fix color of outdated version banner
b933732 Rename display to repr and display_mode to element_repr
5b593b2 Fix CI push to gh-pages
d26b373 Run Python script in CI without custom action
04f0083 Add outdated version banner
7f59231 Create latest symlink when publishing docs to GitHub Pages
3676b4c Remove fast-forward-pr GitHub Action
9696635 Run all CI on release/* branches
61b8016 Clean up docs for optional return argument
f8d63ac Clean up _convert_codeword_to_message()
1b36c35 Add output kwarg to FEC decode() methods
054b480 Add output kwarg to FEC encode() methods
b3c4e6e Set docs page's "Last updated" field with git
e43e396 Add unit tests for generalized BCH and RS codes
fb04257 Clean up TypeError from verify_issubclass()
61f1849 Fix console syntax highlighting in README
f0f35f1 Remove old g(x) to G and H functions
2dd1635 Modify ReedSolomon to support general Reed-Solomon codes over GF(q)
189fa0b Remove bch_valid_codes() from public API
4a91a04 Use binary search when finding BCH d when n and k known
0a5b51e Modify BCH to support general BCH codes over GF(q)
dfe8ee9 Remove unnecessary pytest helper files
1fe55ef Fix the repr of Array and FieldArray when not subclasses
83bf603 Use pyproject.toml pytest settings in VS Code
3e17338 Add --showlocals to pyproject.toml pytest settings
3d47673 Add .coverage to gitignore
3f957da Remove FEC helper functions from public API
b1e4295 Move FEC unit tests into their own folders
11868e4 Run CI on PRs to version branches
676d0dd Fix docs publish on package release

galois v0.1.2

Released November 9, 2022

Changes

• Fixed major inefficiency when dividing an array by a scalar or smaller (broadcasted) array. (#429)

  In [1]: import galois
  
  In [2]: GF = galois.GF(31**5)
  
  In [3]: x = GF.Random(10_000, seed=1); x
  Out[3]:
  GF([13546990, 14653018, 21619804, ..., 15507037, 24669161, 19116362],
     order=31^5)
  
  In [4]: y = GF.Random(1, seed=2); y
  Out[4]: GF([23979074], order=31^5)
  
  # v0.1.1
  In [5]: %timeit x / y
  261 ms ± 5.67 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  
  # v0.1.2
  In [5]: %timeit x / y
  8.23 ms ± 51 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

• Optimized lagrange_poly() by adding a custom JIT-compilable routine. (#432)

  In [1]: import galois
  
  In [2]: GF = galois.GF(13693)
  
  In [3]: x = GF.Random(100, seed=1)
  
  In [4]: y = GF.Random(100, seed=2)
  
  # v0.1.1
  In [5]: %timeit galois.lagrange_poly(x, y)
  2.85 s ± 3.25 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  
  # v0.1.2
  In [5]: %timeit galois.lagrange_poly(x, y)
  4.77 ms ± 190 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

• Added ability in FieldArray.row_reduce() to solve for an identity matrix on the right side of a matrix using the eye keyword argument. (#426)

  >>> import galois
  >>> GF = galois.GF(31)
  >>> A = GF([[16, 12, 1, 25], [1, 10, 27, 29], [1, 0, 3, 19]])
  >>> A.row_reduce()
  GF([[ 1,  0,  0, 11],
      [ 0,  1,  0,  7],
      [ 0,  0,  1, 13]], order=31)
  >>> A.row_reduce(eye="right")
  GF([[ 5,  1,  0,  0],
      [27,  0,  1,  0],
      [17,  0,  0,  1]], order=31)

• Removed comma separators in FieldArray.__str__() to be consistent with NumPy's use of str() and repr(). (#432)

  >>> import galois
  >>> GF = galois.GF(3**5, display="power")
  >>> x = GF.Random((3, 4), seed=1)
  >>> x
  GF([[α^185, α^193,  α^49, α^231],
      [ α^81,  α^60,   α^5,  α^41],
      [ α^50, α^161, α^151, α^171]], order=3^5)
  >>> print(x)
  [[α^185 α^193  α^49 α^231]
   [ α^81  α^60   α^5  α^41]
   [ α^50 α^161 α^151 α^171]]

• Modernized type annotations to use abbreviated notation. For example, a | b instead of Union[a, b]. (#418)
• Added Self type annotation where appropriate. (#420)
• Updated documentation and improved examples. (#424, #430)

Contributors

• Matt Hostetter (@mhostetter)

Commits

e07461b Add release notes for v0.1.2
db88a80 Don't display comma separator in FieldArray.__str__()
81dfe9a JIT compile construction of Lagrange polys
7eed640 JIT compile polynomial subtraction routine
3d090c8 JIT compile polynomial addition routine
7e8a688 Make lagrange_poly() unit tests more robust
8b8a40e Add documentation about NumPy's subok kwarg
b02314f Fix typo in release notes
2a27178 Better support for np.convolve() for prime fields
8a692ff Add unit tests for np.convolve()
b131da1 Add dropdown tips to docs
6e08914 Add polynomial composition example
83cf2fc Add additional ipython-with-reprs usage
01f86f1 Clean up arithmetic examples
6ee9d79 Convert docs to use new ipython-with-reprs directive
670600d Add custom ipython-with-reprs Sphinx directive
c17cd6a Fix inefficiency when dividing by a scalar
0e317c3 Add ability to row_reduce() to solve for I on the right side
f165b02 Add verify_literal helper function
eb007cf Fix typo in array divmod example
a973c5d Change admonition styling
251954e Fix <details> sections for arithmetic examples
abdb71b Upgrade to latest Sphinx Immaterial
85b1b4e Upgrade to Sphinx 5.3
dc49c7c Use built-in Material for Mkdocs linked content tabs instead of sphinx-design tabs
d06d385 Upgrade to latest version of sphinx-immaterial
9e25955 Remove pytest-benchmark from [dev] dependencies until fixed
4fbc26f Add more debug for docs build on package release
954742d Upgrade actions/download-artifact to v3
10aefa1 Upgrade actions/upload-artifact to v3
e3dc09a Upgrade codecov/codecov-action to v3
4f4b4c3 Upgrade tj-action/glob action to v15
6fe28de Upgrade GitHub Actions set-output command
29f2ff5 Upgrade setup-python action to v4
e3af994 Fix NumPy set_printoptions() demo
bc72d18 Fix display of union "short" type annotations in Sphinx
bee9b75 Use PEP 585 type annotations in documentation
bbc06f1 Add SPHINX_BUILD flag back
5991ae2 Use Self type hint throughout library
2a4d945 Require typing_extensions 4.0.0 or greater for Self
46ef7be Minor modification to ValueError messages
8677e90 Fix potentially unbound variable
78ec48c Fix dangerous default value of empty dict
f7b5c8e Convert List[a, b] to list[a, b]
3aefcea Convert Tuple[a, b] to tuple[a, b]
0a4ec79 Convert Optional[a] to a | None
a9a765e Convert Union[a, b] to a | b
79655f2 Move view without verification to Array to fix type hinting
0eacac3 Run unit tests for code coverage on master
05f8c5e Run package build CI on master
76a9822 Run linting CI on master
72ee31d Use v3 of the checkout GitHub action
5e50c81 Add workflow dispatch to build versioned docs on demand

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

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

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

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