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

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

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

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

galois v0.0.25

Released March 21, 2022

Breaking Changes

• Separated LFSR into FLFSR/GLFSR and fixed/redefined terms (feedback poly, characteristic poly, state). (#285)
• Removed galois.pow() and replaced it with the built-in pow(). (#300)

  >>> f = galois.Poly([6, 3, 0, 1], field=galois.GF(7))
  >>> g = galois.Poly([5, 0, 3], field=galois.GF(7))
  >>> pow(f, 123456789, g)
  Poly(6x + 2, GF(7))

• Removed FieldClass.properties and replaced with FieldClass.__str__. (#289)

  >>> GF = galois.GF(3**5)
  >>> print(GF)
  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

• Differentiated repr() and str() for Galois field arrays, like NumPy. repr() displays the finite field's order, but str() does not.

  >>> GF = galois.GF(31, display="power")
  >>> x = GF([1, 23, 0, 15])
  >>> x
  GF([   1, α^27,    0, α^21], order=31)
  >>> print(x)
  [   1, α^27,    0, α^21]

• Renamed Poly.String() to Poly.Str(). Removed Poly.string and replaced it with Poly.__str__. (#300)

  >>> f = galois.Poly.Str("x^3 + x + 1"); f
  Poly(x^3 + x + 1, GF(2))
  >>> str(f)
  'x^3 + x + 1'

• Renamed Poly.Integer() to Poly.Int(). Removed Poly.integer and replaced it with Poly.__int__. (#300)

  >>> f = galois.Poly.Int(11); f
  Poly(x^3 + x + 1, GF(2))
  >>> int(f)
  11

Changes

• Fixed bug in Fibonacci/Galois LFSRs where feedback polynomial wasn't interpreted correctly for fields with characteristic greater than 2. (#299)
• Utilized memoization for expensive search routines (irreducible_poly() and primitive_poly()) to speed-up subsequent calls. (#295)

  In [2]: %time galois.primitive_poly(7, 4)
  CPU times: user 675 ms, sys: 6.24 ms, total: 682 ms
  Wall time: 741 ms
  Out[2]: Poly(x^4 + x^2 + 3x + 5, GF(7))
  
  In [3]: %time galois.primitive_poly(7, 4)
  CPU times: user 30 µs, sys: 0 ns, total: 30 µs
  Wall time: 31.7 µs
  Out[3]: Poly(x^4 + x^2 + 3x + 5, GF(7))

• Added support for bin(), oct(), and hex() on Poly objects. (#300)

  >>> f = galois.Poly.Int(11); f
  Poly(x^3 + x + 1, GF(2))
  >>> bin(f)
  '0b1011'
  >>> oct(f)
  '0o13'
  >>> hex(f)
  '0xb'

• Made Galois field arrays display with fixed-width elements, like NumPy. (#270)
• Achieved speed-up of repr() and str() on Galois field arrays of at least 25x. Achieved a much greater speed-up for large arrays, since now elements converted to ... are no longer needlessly converted to their string representation. (#270)
• Overhauled documentation and website. Type hints are now displayed in the API reference. (#263)
• Various bug fixes.

Contributors

• Matt Hostetter (@mhostetter)

Commits

f9b6cab Version bump to 0.0.25
989657f Add release notes for v0.0.25
c2e3def Update feature list
98b9f3f Make GF() docstring more readable with a tab set
a401abf Document poly arithmetic only on the Basic Usage page
3edc4e9 Remove galois.pow(), instead use built-in pow()
7f8ce52 Define Poly.__index__() to support bin(), oct(), and hex()
6816adc Remove unnecessary __ne__() definition
45db3a5 Rename Poly.Integer to Poly.Int
d05ce1b Replace Poly.integer with int(poly)
4a3ff9d Rename Poly.String() to Poly.Str()
47eb6f5 Replace Poly.string with str(poly)
af3e6ee Remove unused section in API reference
7c2b1f0 Do not fail CI if codecov fails to upload
d3be8ab Complete overhaul of LFSRs and fix bug when p > 2
f691bb5 Memoize slow polynomial search functions
2bd30ef Differentiate str() and repr() for FieldArray
1b102d1 Remove unnecessary tabs in docstring
5b5c65c Replace FieldClass.properties with FieldClass.__str__()
3ec09d3 Separate LFSR into FLFSR and GLFSR
1a2a8e7 Build the docs with Python 3.8 on Read the Docs
b373d45 Fix properties formatting for prime fields in power display mode
3881ea0 Fix typos in finite field tutorials
1aceed0 Display type hints in API documentation
5efd39c Add tabbed sections with different reprs in basic usage
1dd41e1 Add tabbed sections with different reprs for tutorials
c63fecf Modify the CSS rules for tab-set from sphinx-design
1018fd5 Add sphinx-design dependency for tabbed sections
b77e999 Switch light/night mode icons
337ef93 Update BibTeX citation
88487c1 Remove unnecessary doc dependencies
005c493 Revert autosummary table fix since already fixed in upstream
5799874 Separate Poly class and init docstrings
5553d0f Revert use of box drawing glyphs for monospace consistency with more fonts
aaebb3d Remove NumPy reference and use Basic Usage articles instead
2f24414 Remove old basic usage file
7e19eab Fix autosummary strange line wrapping
f28176d Add more detail in the field element representation docs
603c03d Update Getting Started guide with new array repr()
fd9a57c Make repr() more efficient for large arrays
3c4c2d4 Make "poly" display mode use fixed widths
7ffd551 Make "poly" display mode more efficient for prime fields
3a0c668 Use fixed widths in "power" display mode for all array sizes
b506f1b Make __repr__() more efficient
6872b7a Initial docs port to sphinx-immaterial

galois v0.0.24

Breaking Changes

• Move galois.minimal_poly() functionality into FieldArray.minimal_poly().
• Refactor FieldArray.lup_decompose() into FieldArray.plu_decompose().
• Raise ValueError instead of returning None for prev_prime(2).
• Return (n, 1) from perfect_power(n) if n is not a perfect power rather than returning None.

Changes

• Compute a finite field element's square root (if it exists) with np.sqrt().
• List which finite field elements are/aren't quadratic residues (have a square root) with FieldClass.quadratic_residues and FieldClass.quadratic_non_residues.
• Compute standard vector spaces with FieldArray.row_space(), FieldArray.column_space(), FieldArray.left_null_space(), and FieldArray.null_space().
• Compute a finite field element's additive and multiplicative orders with FieldArray.additive_order() and FieldArray.multiplicative_order().
• Evaluate polynomials at square matrix inputs using f(X, elementwise=False).
• Compute the characteristic polynomial of a single element or square matrix with FieldArray.characteristic_poly().
• Compute the minimal polynomial of a single element with FieldArray.minimal_poly().
• Compute a Lagrange interpolating polynomial with lagrange_poly(x, y).
• Support non-square matrix inputs to FieldArray.lu_decompose() and FieldArray.plu_decompose().
• Support polynomial scalar multiplication. Now p * 3 is valid syntax and represents p + p + p.
• Allow polynomial comparison with integers and field scalars. Now galois.Poly([0]) == 0 and galois.Poly([0]) == GF(0) return True rather than raising TypeError.
• Support testing 0-degree polynomials for irreducibility and primitivity.
• Extend crt() to work over non co-prime moduli.
• Extend prev_prime() and next_prime() to work over arbitrarily-large inputs.
• Allow negative integer inputs to primes(), is_prime(), is_composite(), is_prime_power(), is_perfect_power(), is_square_free(), is_smooth(), and is_powersmooth().
• Fix various type hinting errors.
• Various other bug fixes.

Contributors

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

Commits

e35831a Version bump to 0.0.24
0196d7f Add release notes for v0.0.24
48dc549 Fix irreducible and primitive polynomial degree criteria
4083e89 Add () to functions/methods in README
cf97f21 Add unit tests for null_space()
71dd31c Add FieldArray.null_space() method
2669826 Add unit tests for left_null_space()
0a103f6 Add FieldArray.left_null_space() method
839d621 Add unit tests for column_space()
3c8ced9 Add FieldArray.column_space() method
bfbeb31 Add unit tests for row_space()
7c595cc Add FieldArray.row_space() method
134eb7d Fix code coverage exclusion of typing overloads
5d0f353 Update codecov GitHub action version
3aa7d1b Ensure pure-Python ufuncs are performing integer arithmetic
8993630 Add more is_powersmooth() unit tests
9b356cb Add more is_smooth() unit tests
9003ed4 Rearrange prime generation and factoring code
0748408 Add more is_monic() unit tests
e61ba58 Accept non-monic polynomials to is_square_free()
322a962 Add more unit tests for testing square-free integers
0932530 Add is_perfect_power() unit tests
9e5fe69 Make perfect_power() and is_perfect_power() more consistent with Sage
a70d95b Add more is_prime_power() unit tests
2153cef Allow negative integers to is_prime_power()
a8fb8ef Allow negative integers to is_composite()
d77bb3e Add more is_prime() unit tests
4c16712 Allow negative integers to is_prime()
a55e277 Add more next_prime() unit tests
01a4737 Add more prev_prime() unit tests
7eea08a Raise ValueError instead of returning None for invalid previous prime
8b9f23c Add more kth_prime() unit tests
0f0d686 Add more primes() unit tests
19398cc Add more is_cyclic() unit tests
d9dfa2d Add more carmichael_lambda() unit tests
93d486f Add more euler_phi() unit tests
f8a9f24 Add unit tests for polynomial CRT
ff04822 Raise ValueError on polynomial CRT if remainder degrees not less than moduli degrees
91f4651 Make CRT support non-coprime moduli
005d77c Resolve pytest warnings
d68f537 Add unit tests for integer logarithms
d77b1ee Add more unit tests for integer roots
f29b0e8 Add more unit tests for integer square root
f477eae Add more unit tests for integer modular exponentiation
f61bae2 Add unit tests for integer prod()
12f3ca3 Add more unit tests for integer LCM
e90d43e Add more unit tests for integer extended GCD
2d4f210 Remove old poly evaluation at matrices unit tests
1166dbe Add more primitive polynomial unit tests
d3ad835 Add more irreducible polynomial unit tests
d34b654 Add more unit tests for polynomial modular exponentiation
5344660 Add unit tests for galois.prod() with polynomials
a5d9dd2 Add unit tests for polynomial LCM
15b4c7f Add more polynomial GCD unit tests
f1452f6 Clean up test vector generation script
0140a45 Add more Poly.derivative() unit tests
5780e1e Add more Poly.roots() unit tests
8355743 Add unit tests for polynomial reversals
09f984b Add unit tests for poly evaluation at square matrices
e78d46f Increase linear algebra code coverage
53d6b0e Support non-square matrices for LU and PLU decomposition
fccdf0d Instruct code coverage to ignore typing overloads
f27480c Add more np.linalg.solve() unit tests
edd2e0f Add more matrix determinant unit tests
f1561b4 Add unit tests for matrix inverses
991feb7 Refactor lup_decompose() into plu_decompose()
f4a2cc7 Add more lu_decompose() unit tests
84eaaf6 Add unit tests for row_reduce()
a8ac0e6 Add more matrix multiplication unit tests
6f64f2d Add more field_norm() unit tests
95d80ef Add more field_trace() unit tests
51c4362 Add more minimal_poly() unit tests for 0-D scalars
4879587 Add more characteristic_poly() unit tests for matrices
8147946 Add more characteristic_poly() unit tests for 0-D scalars
b6abfc2 Add more multiplicative_order() unit tests
a00e496 Add more additive_order() unit tests
5a002d4 Rename field fixtures for unit tests
767588c Move unit test LUT folders
bf6d120 Make each unit test LUT reproducible with unique seed
a5e6386 Resolve NumbaIRAssumptionWarning
70dc6e2 Support polynomial scalar multiplication
0a37672 Add unit tests for Galois field class properties
2eea839 Add back erroneously-deleted multiplicative_inverse.pkl generation
9904f57 Use poly comparison with 0 and 1 throughout library
51135fd Support Poly equals comparison with scalars
21b2487 Change np.sqrt() error to ArithmeticError
82b938e Add unit tests for np.sqrt()
eaad6da Support np.sqrt() on Galois field arrays
a41cd7c Fix other type hints for shape
14a1547 Add unit tests for quadratic residues
c26143c Add FieldClass.quadratic_non_residues
ef7f9b7 Add FieldClass.quadratic_residues
8c00cb2 Add FieldArray.is_quadratic_residue()
3c49aa7 Fix shape type hint
ce0ad6b Speed up FieldArray.multiplicative_order() when LUTs are available
89ad6a5 Support prev_prime(n) for arbitrarily-large n
a1fc17d Support next_prime(n) for arbitrarily-large n
50eb7e8 Fix bug in field trace/norm tests
1ee3f8e Add unit tests for FieldArray.additive_order()
5cf3082 Add FieldArray.additive_order()
8d989dd Add unit tests for FieldArray.multiplicative_order()
8a247a9 Add FieldArray.multiplicative_order()
04539f7 Fix type hint for NumPy integer types
54e99b7 Move galois.minimal_poly() to FieldArray.minimal_poly()
db133a6 Add unit tests for characteristic poly of finite field elements
f2e5492 Add ability to compute characteristic polynomial of a finite field element
b57d6e9 Add ability to evaluate polynomials at square matrices
0bd8b61 Add __len__ special method to docs
5cc3560 Add __call__ special method to docs
29aa072 Add missing dependency to min-requirements.txt
f3d9984 Add unit tests for lagrange_poly()
1b63538 Add lagrange_poly function
f78cb64 Add non constant-time disclaimer to README

galois v0.0.23

Changes

• Add support for Python 3.10.
• Add support for NumPy 1.21.
• Add support for Numba 0.55.
• Add type hints to library API.
• Add FieldArray.characteristic_poly() method to return the characteristic polynomial of a square matrix.
• Add Poly.coefficients() method to return the coefficient array with fixed size and order.
• Fix bug in Poly.Degrees() when duplicate degrees were present.
• Fix bug in Reed-Solomon decode when c != 1.
• Various other bug fixes.

Contributors

• Matt Hostetter (@mhostetter)

Commits

696315b Version bump to 0.0.23
a828748 Add release notes for v0.0.23
6812dc4 Remove unneeded variable
a3bb6fc Remove unnecessary pytest markers
3a55b36 Add support for NumPy 1.21
e76b77e Support Python 3.10
c7ef695 Add unit tests for FieldArray.characteristic_poly()
b6dc38c Add FieldArray.characteristic_poly()
0105045 Hide type hints from sphinx docs signatures
c44082b Fix bug in Miller-Rabin primality test when n=3
69dc22f Move _polys/ into _fields/ folder for less circular dependence
7ce772f Add type hints to FEC codes
7d5b71f Add type hints for misc functions
9fa4736 Add type hints to polynomial classes
bd28afe Add type hints to field classes
b13980b Add type hints to general functions
4a498ba Add typing_extensions dependency
0548e00 Add unit tests for RS decode with c != 1
302dd69 Fix RS decode when c != 1
f54aef7 Make RS decoding more efficient
280a3e9 Ensures Poly.Degrees has unique degree inputs
a89fd86 Add unit tests for Poly.coefficients()
d3f2974 Add Poly.coefficients() method accessor
8704354 Fix display of logo in README on PyPI
74bd34c Bump allowable Numba version to 0.54.x
28ce919 Add workaround for #178
eb427c3 Delete table of contents in README

galois v0.0.22

Breaking Changes

• Random integer generation is handled using new style random generators. Now each .Random() call will generate a new seed rather than using the NumPy "global" seed used with np.random.randint().

• Add a seed=None keyword argument to FieldArray.Random() and Poly.Random(). A reproducible script can be constructed like this:

  rng = np.random.default_rng(123456789)
  x = GF.Random(10, seed=rng)
  y = GF.Random(10, seed=rng)
  poly = galois.Poly.Random(5, seed=rng, field=GF)

Changes

• Official support for Python 3.9.
• Major performance improvements to "large" finite fields (those with dtype=np.object_).
• Minor performance improvements to all finite fields.
• Add the Number Theoretic Transform (NTT) in ntt() and intt().
• Add the trace of finite field elements in FieldArray.field_trace().
• Add the norm of finite field elements in FieldArray.field_norm().
• Support len() on Poly objects, which returns the length of the coefficient array (polynomial order + 1).
• Support x.dot(y) syntax for the expression np.dot(x, y).
• Minimum NumPy version bumped to 1.18.4 for new style random usage.
• Various bug fixes.

Contributors

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

Commits

63760c3 Version bump to 0.0.22
5ecae0a Make Poly.Random() outputs consistent with GF.Random()
ba779a9 Add release notes for v0.0.22
1d144e2 Minor documentation tweaks
e1b499c Fix typo in docs build instructions
e4618a9 Add seed kwarg to Poly.Random()
ffe78b4 Add unit tests Random constructor with seed
6b00496 Use new numpy.random.default_rng()
7ecf8ec Bump NumPy to 1.18.4
ab0f108 Prevent other x**np.arange() overflow errors with improper dtype
817ad94 Fix #205
158f5ff Support ndarray.dot() usage
3e8ee35 Add tests for ndarray.dot() usage
976d2a4 Allow caching of constants in lambda functions
f1d2f6e Do not re-verify the type/value of FieldArray instances
d79332e Compute FieldClass.dtypes only once
9316409 Add unit test len(galois.Poly)
79f6dc2 Add len method to Poly class
ba217ff Add unit test with example from #194
48a4ad7 Fix #194
4b9c521 Add field_norm() method
e7d0590 Add field_trace() method
74171dc Fix typos
23ab9ed Fix #188
b08920c Fix #186
69d4a56 Support Python 3.9
c294e5c Add initial implementation of the NTT and INTT
e42a0eb Fix linter suggestions
f9ea821 Merge lint and test dependencies into requirements-dev.txt
271882e Move docs requirements file into docs/ folder
2ed51c2 Update VS Code settings for newer versions
4d25b08 Explicitly specify pylint config file for VS Code

galois v0.0.21

Changes

• Fix docstrings and code completion for Python classes that weren't rendering correctly in an IDE.
• Various documentation improvements.

Contributors

• Matt Hostetter (@mhostetter)

Commits

a23bff6 Version bump to 0.0.21
69672c2 Add release notes for v0.0.21
803c872 Clarify warnings in FieldClass and FieldArray docstrings
eff2ce7 Fix FieldClass and FieldArray class docstrings
743a265 Fix LFSR class docstrings
32f0b1f Fix Reed Solomon creation and docstring placement
1f6e582 Fix BCH creation and docstring placement
ded3e3a Update Twitter badge style in README
354f221 Fix display of logo on PyPI's website

galois v0.0.20

Breaking Changes

• Move poly_gcd() functionality into gcd().
• Move poly_egcd() functionality into egcd().
• Move poly_factors() functionality into factors().

Changes

• Fix polynomial factorization algorithms. Previously only parital factorization was implemented.
• Support generating and testing irreducible and primitive polynomials over extension fields.
• Support polynomial input to is_square_free().
• Minor documentation improvements.
• Pin Numba dependency to <0.54

Contributors

• Matt Hostetter (@mhostetter)

Commits

6bf7b2f Version bump to 0.0.20
e32180b Add release notes for v0.0.20
c14f2ca Pin Numba less than 0.54 until warnings resolved
9efc6e5 Clean-up Galois field array JIT functions
60f83fd Add CITATION file
e57e2d3 Add extra PyPI project URLs
e3c8ff2 Add Twitter badge
16645b5 Remove known mirrors from PyPI downloads badge
7571004 Link galois object to API reference in docs
902e6e6 Greatly clean-up Galois field arithmetic functions/classes
5e5c6a8 Fix linter warning
0722d5e Add v2 of logo with smaller Rubik's cube
8d810da Ignore abstract methods in code coverage
575354e Remove lint badge from README
1a459a7 Make is_square_free() work on polynomials
b286baa Add polymorphic functions for ints and polys
41d6784 Add <meta> HTML tag to README
e486eaa Reset display mode to integer representation in docs
dcabb11 Increase code coverage for poly constructors
efcb9a9 Make poly_factors() work over extension fields
ffea5b7 Fix bug in p-th root of polynomial
7688cc2 Support primitive polynomials over extension fields
4f7cbd1 Support irreducible polynomials over extension fields
c5f7056 Fix poly_factors() for prime fields
53f3b37 Fix bug in equal-degree factorization
eb4ed74 Make unit tests require successful lint stage
510864b Restructure fields and polys subpackages
defea3d Restructure code and clean-up circular dependencies
bf0b27a Fix field docstring in Poly.Degrees()
cee6904 Add polynomial equal-degree factorization
c84e09a Add polynomial distinct-degree factorization
5d7ab83 Add polynomial square-free factorization
3ce5fd9 Fix display of logo on PyPI's website