Releases: mhostetter/galois
galois v0.3.8
Released February 1, 2024
Changes
- Added support for Python 3.12. (#534)
- Added support for NumPy 1.26. (#534)
- Added support for Numba 0.59. (#534)
- Fixed bug in
FieldArray.multiplicative_order()
for large fields. (#533)
Contributors
- Matt Hostetter (@mhostetter)
galois v0.3.7
Released November 30, 2023
Changes
- Added wheel factorization for finding large primes. (#527)
- Improved type annotations. (#510, #511)
- Removed optional
[dev]
extra. If developing, install fromrequirements-dev.txt
. (#521) - Fixed bugs in
prev_prime()
andnext_prime()
for large primes. (#527)
Contributors
- @avadov
- Matt Hostetter (@mhostetter)
galois v0.3.6
Released October 1, 2023
Changes
- Added support for NumPy 1.25. (#507)
- Added support for Numba 0.58. (#507)
- Fixed rare overflow with computing a large modular exponentiation of polynomials. (#488)
- Resolved various deprecations warnings with NumPy 1.25. (#492)
Contributors
- Iyán Méndez Veiga (@iyanmv)
- @Lasagnenator
- Matt Hostetter (@mhostetter)
galois v0.3.5
Released May 9, 2023
Changes
- Added
py.typed
file to indicate tomypy
and other type checkers thatgalois
supports typing. (#481) - Fixed bug with multiple, concurrent BCH and/or Reed Solomon decoders. (#484)
Contributors
- Matt Hostetter (@mhostetter)
Commits
a140a46 Add release notes for v0.3.5
2e49783 Prevent GitHub Release workflow from failing
7418aa5 Make colors easier to read in dark mode
bd0546d Limit right-side TOC depth for release note pages
329aaa6 Move star call to dismissable banner
5bbec50 Store BCH and RS decoders in different namespaces
c3a82df Store BCH/RS decoders for each base/extension field pair
1823440 Add unit test to catch #483
d91f83d Fix unhidden table of contents
214cd52 Display NumPy and Numba versions when testing
7dcd6d0 Make release note pages more succinct
1c5980a Comply with PEP 561
galois v0.3.4
Released May 2, 2023
Changes
- Added support for Python 3.11. (#415)
- Added support for NumPy 1.24. (#415)
- Fixed indexing bug in
FieldArray.plu_decompose()
for certain input arrays. (#477)
Contributors
- Matt Hostetter (@mhostetter)
Commits
a2fa1ac Add release notes for v0.3.4
f94af2a Support NumPy 1.24
95f5b1f Support Python 3.11 with NumPy 1.23.2 and Numba 0.57
1edbb19 Change Twitter badge color to blue
c882d72 Add unit test for #476
09926f2 Use consistent variable names between LU and PLU
43fe231 Fix error message in lu_decompose()
79325b5 Fix array sizing for PLU decomposition
766ba86 Format HTML file
2a27ccd Fix the Twitter badge
galois v0.3.3
Released February 1, 2023
Changes
- Added a
terms
keyword argument toirreducible_poly()
,irreducible_polys()
,primitive_poly()
, andprimitive_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()
whenterms="min"
andmethod="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()
andPoly.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()
andPoly.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)'>
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()
andgalois.Field()
so that keyword argumentsirreducible_poly
,primitive_element
,verify
,compile
, andrepr
may no longer be passed as positional arguments. (#442)
Changes
- Added a
galois.GF(p, m)
call signature in addition togalois.GF(p**m)
. This also applies togalois.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-innp.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 FECencode()
methods and replaced withoutput="codeword"
. -
Removed
bch_valid_codes()
from the API. Instead, usegalois.BCH(n, d=d)
to find and create a BCH code with codeword sizen
and design distanced
. For example, here is how to find various code sizes of primitive BCH codes overGF(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()
, androots_to_parity_check_matrix()
from the API.
-
-
Renamed properties and methods for changing the finite field element representation. (#436)
-
Renamed
display
keyword argument inGF()
torepr
. -
Renamed
FieldArray.display()
classmethod toFieldArray.repr()
. -
Renamed
FieldArray.display_mode
property toFieldArray.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 FECencode()
methods. (#435) - Added
output="message"
keyword argument to FECdecode()
methods. (#435) - Standardized NumPy scalar return types (
np.bool_
andnp.int64
) to Python types (bool
andint
). For example, inFieldArray.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