galois¶

A performant numpy extension for Galois fields.

Classes

`GF2`(array[, dtype])	asdf
`GFBase`(array[, dtype])	asdf
`GFpBase`(args, *kwargs)	asdf
`Poly`(coeffs[, field])	asdf

Class Factory Functions

`GF_factory`(p, m[, prim_poly, rebuild])	Factory function to construct Galois field array classes of type GF(p^m).
`GFp_factory`(p[, rebuild])	Factory function to construct Galois field array classes of type GF(p).

Functions

`carmichael`(n)	Implements the Carmichael function to find the smallest positive integer m such that a^m = 1 (mod n) for 1 <= a < n.
`chinese_remainder_theorem`(a, m)	Implements the Chinese Remainder Theorem (CRT).
`euclidean_algorithm`(a, b)	Implements the Euclidean Algorithm to find the greatest common divisor of two integers.
`euler_totient`(n)	Implements the Euler Totient function to count the positive integers (totatives) in 1 <= k < n that are relatively prime to n, i.e. gcd(n, k) = 1.
`extended_euclidean_algorithm`(a, b)	Implements the Extended Euclidean Algorithm to find the integer multiplicands of a and b, such that ax + by = gcd(a,b).
`factors`(x)	Computes the positive factors of the integer x.
`is_prime`(x)	Determines if x is prime.
`min_poly`(a, field, n)	Finds the minimal polynomial of a over the specified Galois field.
`next_prime`(x)	Returns the closest prime p > x.
`prev_prime`(x)	Returns the closest prime p <= x.
`prime_factors`(x)	Computes the prime factors of the positive integer x.
`primitive_root`(n)	Finds the first, smallest primitive n-th root of unity that satisfy x^k = 1 (mod n).
`primitive_roots`(n)	Finds all primitive n-th roots of unity that satisfy x^k = 1 (mod n).

class galois.GF2(array, dtype=<class 'numpy.int64'>)[source]¶

Bases: galois.gf.GFBase

asdf

Examples

GF2 class properties

In [1]: print(galois.GF2)
<Galois Field: GF(2^1), prim_poly = x + 1 (None decimal)>

In [2]: galois.GF2.characteristic
Out[2]: 2

In [3]: galois.GF2.power
Out[3]: 1

In [4]: galois.GF2.order
Out[4]: 2

In [5]: galois.GF2.prim_poly
Out[5]: Poly(x + 1 , GF2)

Construct arrays in GF2

In [6]: a = galois.GF2([1,0,1,1]); a
Out[6]: GF2([1, 0, 1, 1])

In [7]: b = galois.GF2([1,1,1,1]); b
Out[7]: GF2([1, 1, 1, 1])

Arithmetic with GF2 arrays

# Element-wise addition
In [1]: a + b
Out[1]: GF2([0, 1, 0, 0])

# Element-wise subtraction
In [2]: a - b
Out[2]: GF2([0, 1, 0, 0])

# Element-wise multiplication
In [3]: a * b
Out[3]: GF2([1, 0, 1, 1])

# Element-wise division
In [4]: a / b
Out[4]: GF2([1, 0, 1, 1])

alpha = 1¶

The primitive element of the Galois field GF(p^m). The primitive element is a root of the primitive polynomial, such that prim_poly(alpha) = 0. The primitive element also generates the field GF(p^m) = {0, 1, alpha^1, alpha*2, …, alpha^(p^m - 2)}.

Type: int

characteristic = 2¶

The characteristic p, which must be prime, of the Galois field GF(p^m). Adding p copies of any element will always result in 0.

Type: int

dtypes = [<class 'numpy.uint8'>, <class 'numpy.uint16'>, <class 'numpy.uint32'>, <class 'numpy.int8'>, <class 'numpy.int16'>, <class 'numpy.int32'>, <class 'numpy.int64'>]¶

List of valid integer numpy dtypes that are compatible with this Galois field array class.

Type: list

order = 2¶

The order p^m of the Galois field GF(p^m). The order of the field is also equal to the field’s size.

Type: int

power = 1¶

The power m, which must be non-negative, of the Galois field GF(p^m).

Type: int

prim_poly = Poly(x + 1 , GF2)¶

The primitive polynomial of the Galois field GF(p^m). The primitve polynomial must have coefficients in GF(p).

Type: galois.Poly

class galois.GFBase(array, dtype=<class 'numpy.int64'>)[source]¶

Bases: numpy.ndarray

asdf

Note

This is an abstract base class for all Galois fields. It cannot be instantiated directly.

classmethod Elements(dtype=<class 'numpy.int64'>)[source]¶

classmethod Ones(shape, dtype=<class 'numpy.int64'>)[source]¶

classmethod Random(shape=(), low=0, high=None, dtype=<class 'numpy.int64'>)[source]¶

classmethod Zeros(shape, dtype=<class 'numpy.int64'>)[source]¶

astype(dtype, order='K', casting='unsafe', subok=True, copy=True)[source]¶

Copy of the array, cast to a specified type.

Parameters

dtype (str or dtype) – Typecode or data-type to which the array is cast.
order ({'C', 'F', 'A', 'K'}, optional) – Controls the memory layout order of the result. ‘C’ means C order, ‘F’ means Fortran order, ‘A’ means ‘F’ order if all the arrays are Fortran contiguous, ‘C’ order otherwise, and ‘K’ means as close to the order the array elements appear in memory as possible. Default is ‘K’.
casting ({'no', 'equiv', 'safe', 'same_kind', 'unsafe'}, optional) –
Controls what kind of data casting may occur. Defaults to ‘unsafe’ for backwards compatibility.
- ’no’ means the data types should not be cast at all.
- ’equiv’ means only byte-order changes are allowed.
- ’safe’ means only casts which can preserve values are allowed.
- ’same_kind’ means only safe casts or casts within a kind, like float64 to float32, are allowed.
- ’unsafe’ means any data conversions may be done.
subok (bool, optional) – If True, then sub-classes will be passed-through (default), otherwise the returned array will be forced to be a base-class array.
copy (bool, optional) – By default, astype always returns a newly allocated array. If this is set to false, and the dtype, order, and subok requirements are satisfied, the input array is returned instead of a copy.

Returns

arr_t – Unless copy is False and the other conditions for returning the input array are satisfied (see description for copy input parameter), arr_t is a new array of the same shape as the input array, with dtype, order given by dtype, order.

Return type

ndarray

Notes

Changed in version 1.17.0: Casting between a simple data type and a structured one is possible only for “unsafe” casting. Casting to multiple fields is allowed, but casting from multiple fields is not.

Changed in version 1.9.0: Casting from numeric to string types in ‘safe’ casting mode requires that the string dtype length is long enough to store the max integer/float value converted.

Raises: ComplexWarning – When casting from complex to float or int. To avoid this, one should use a.real.astype(t).

Examples

>>> x = np.array([1, 2, 2.5])
>>> x
array([1. ,  2. ,  2.5])

>>> x.astype(int)
array([1, 2, 2])

classmethod target(target)[source]¶

Retarget the just-in-time compiled numba ufuncs.

Parameters: target (str) – Either “cpu”, “parallel”, or “cuda”.

alpha = None¶

The primitive element of the Galois field GF(p^m). The primitive element is a root of the primitive polynomial, such that prim_poly(alpha) = 0. The primitive element also generates the field GF(p^m) = {0, 1, alpha^1, alpha*2, …, alpha^(p^m - 2)}.

Type: int

characteristic = None¶

The characteristic p, which must be prime, of the Galois field GF(p^m). Adding p copies of any element will always result in 0.

Type: int

dtypes = []¶

List of valid integer numpy dtypes that are compatible with this Galois field array class.

Type: list

order = None¶

The order p^m of the Galois field GF(p^m). The order of the field is also equal to the field’s size.

Type: int

power = None¶

The power m, which must be non-negative, of the Galois field GF(p^m).

Type: int

prim_poly = None¶

The primitive polynomial of the Galois field GF(p^m). The primitve polynomial must have coefficients in GF(p).

Type: galois.Poly

class galois.GFpBase(*args, **kwargs)[source]¶

Bases: galois.gf.GFBase

asdf

Note

This is an abstract base class for all GF(p) fields. It cannot be instantiated directly.

class galois.Poly(coeffs, field=<class 'galois.gf2.GF2'>)[source]¶

Bases: object

asdf

Examples

Create polynomials over GF(2)

# Construct a polynominal over GF(2)
In [1]: a = galois.Poly([1,0,1,1]); a
Out[1]: Poly(x^3 + x + 1 , GF2)

# Construct the same polynomial by only specifying its non-zero coefficients
In [2]: b = galois.Poly.NonZero([1,1,1], [3,1,0]); b
Out[2]: Poly(x^3 + x + 1 , GF2)

Create polynomials over GF(7)

# Construct the GF(7) field
In [3]: GF = galois.GF_factory(7, 1)

# Construct a polynominal over GF(7)
In [4]: a = galois.Poly([4,0,3,0,0,2], field=GF); a
Out[4]: Poly(4x^5 + 3x^3 + 2 , GF7)

# Construct the same polynomial by only specifying its non-zero coefficients
In [5]: b = galois.Poly.NonZero([4,3,2], [5,3,0], field=GF); b
Out[5]: Poly(4x^5 + 3x^3 + 2 , GF7)

Polynomial arithmetic

In [1]: a = galois.Poly([1,0,6,3], field=GF); a
Out[1]: Poly(x^3 + 6x + 3 , GF7)

In [2]: b = galois.Poly([2,0,2], field=GF); b
Out[2]: Poly(2x^2 + 2 , GF7)

In [3]: a + b
Out[3]: Poly(x^3 + 2x^2 + 6x + 5 , GF7)

In [4]: a - b
Out[4]: Poly(x^3 + 5x^2 + 6x + 1 , GF7)

# Compute the quotient of the polynomial division
In [5]: a / b
Out[5]: Poly(4x , GF7)

# True division and floor division are equivalent
In [6]: a / b == a // b
Out[6]: True

# Compute the remainder of the polynomial division
In [7]: a % b
Out[7]: Poly(5x + 3 , GF7)

classmethod NonZero(coeffs, degrees, field=<class 'galois.gf2.GF2'>)[source]¶

Examples

# Construct a polynomial over GF2 only specifying the non-zero terms
In [8]: a = galois.Poly.NonZero([1,1,1], [3,1,0]); a
Out[8]: Poly(x^3 + x + 1 , GF2)

static divmod(dividend, divisor)[source]¶

property coeffs¶

property degree¶

The degree of the polynomial, i.e. the highest degree with non-zero coefficient.

Type: int

property field¶

The finite field to which the coefficients belong.

Type: galois.GF2Base or galois.GFpBase

property str¶

galois.GF_factory(p, m, prim_poly=None, rebuild=False)[source]¶

Factory function to construct Galois field array classes of type GF(p^m).

If p = 2 and m = 1, this function will return galois.GF2. If p = 2 and m > 1, this function will invoke galois.GF2m_factory(). If p is prime and m = 1, this function will invoke galois.GFp_factory(). If p is prime and m > 1, this function will invoke galois.GFpm_factory().

Parameters

p (int) – The prime characteristic of the field GF(p^m).
m (int) – The degree of the prime characteristic of the field GF(p^m).
prim_poly (galois.Poly, optional) – The primitive polynomial of the field. Default is None which will auto-determine the primitive polynomial.
rebuild (bool, optional) – A flag to force a rebuild of the class and its lookup tables. Default is False which will return the cached, previously-built class if it exists.

Returns

A new Galois field class that is a sublcass of galois.GFBase.

Return type

galois.GF2Base or galois.GFpBase

galois.GFp_factory(p, rebuild=False)[source]¶

Factory function to construct Galois field array classes of type GF(p).

Parameters

p (int) – The prime characteristic of the field GF(p).
rebuild (bool, optional) – A flag to force a rebuild of the class and its lookup tables. Default is False which will return the cached, previously-built class if it exists.

Returns

A new Galois field class that is a sublcass of galois.GFpBase.

Return type

galois.GFpBase

galois.carmichael(n)[source]¶

Implements the Carmichael function to find the smallest positive integer m such that a^m = 1 (mod n) for 1 <= a < n.

Parameters: n (int) – A positive integer.
Returns: The smallest positive integer m such that a^m = 1 (mod n) for 1 <= a < n.
Return type: int

galois.chinese_remainder_theorem(a, m)[source]¶

Implements the Chinese Remainder Theorem (CRT). The CRT is a method for finding the simultaneous solution to a system of congruences.

\[ \begin{align}\begin{aligned}x &\equiv a_1\ (\textrm{mod}\ m_1)\\x &\equiv a_2\ (\textrm{mod}\ m_2)\\x &\equiv \ldots\\x &\equiv a_n\ (\textrm{mod}\ m_n)\end{aligned}\end{align} \]

Parameters

a (array_like) – The integer remainders \(a_i\).
m (array_like) – The integer modulii \(m_i\).

Returns

The simultaneous solution \(x\) to the system of congruences.

Return type

int

galois.euclidean_algorithm(a, b)[source]¶

Implements the Euclidean Algorithm to find the greatest common divisor of two integers.

Parameters

a (int) – Any integer.
b (int) – Any integer.

Returns

Greatest common divisor of a and b, i.e. gcd(a,b).

Return type

int

References

1. Moon, “Error Correction Coding”, Section 5.2.2: The Euclidean Algorithm and Euclidean Domains, p. 181
https://en.wikipedia.org/wiki/Euclidean_algorithm

galois.euler_totient(n)[source]¶

Implements the Euler Totient function to count the positive integers (totatives) in 1 <= k < n that are relatively prime to n, i.e. gcd(n, k) = 1.

Parameters: n (int) – A positive integer.
Returns: The number of totatives that are relatively prime to n.
Return type: int

galois.extended_euclidean_algorithm(a, b)[source]¶

Implements the Extended Euclidean Algorithm to find the integer multiplicands of a and b, such that a*x + b*y = gcd(a,b).

Parameters

a (int) – Any integer.
b (int) – Any integer.

Returns

int – Integer x, such that a*x + b*y = gcd(a, b).
int – Integer y, such that a*x + b*y = gcd(a, b).
int – Greatest common divisor of a and b.

References

1. Moon, “Error Correction Coding”, Section 5.2.2: The Euclidean Algorithm and Euclidean Domains, p. 181
https://en.wikipedia.org/wiki/Euclidean_algorithm#Extended_Euclidean_algorithm

galois.factors(x)[source]¶

Computes the positive factors of the integer x.

Parameters: x (int) – An integer to be factored.
Returns: Sorted array of factors of x.
Return type: np.ndarray

galois.is_prime(x)[source]¶

Determines if x is prime.

Parameters: x (int) – A positive integer (x > 1).
Returns: True if the integer x is prime. False if it isn’t.
Return type: bool

galois.min_poly(a, field, n)[source]¶

Finds the minimal polynomial of a over the specified Galois field.

Parameters

a (int) – Field element in the extension field GF(q^n).
field (galois.gf.GFBase) – The base field GF(q).
n (int) – The degree of the extension field.

Returns

The minimal polynomial of n-th degree with coefficients in field, i.e. GF(q), for which x in GF(q^n) is a root. p(x) over GF(q) and p(a) = 0 in GF(q^n).

Return type

galois.Poly

galois.next_prime(x)[source]¶

Returns the closest prime p > x.

Parameters: x (int) – A positive integer.
Returns: The closest prime p > x.
Return type: int

galois.prev_prime(x)[source]¶

Returns the closest prime p <= x.

Parameters: x (int) – A positive integer.
Returns: The closest prime p <= x.
Return type: int

galois.prime_factors(x)[source]¶

Computes the prime factors of the positive integer x.

The integer \(x\) can be factored into \(x = p_1^{k_1} p_2^{k_2} ... p_{n-1}^{k_{n-1}}\).

Parameters

x (int) – The positive integer to be factored (x > 1).

Returns

np.ndarray – Sorted array of prime factors \(p = [p_1, p_2, ..., p_{n-1}]\).
np.ndarray – array of corresponding prime powers \(k = [k_1, k_2, ..., k_{n-1}]\).

galois.primitive_root(n)[source]¶

Finds the first, smallest primitive n-th root of unity that satisfy x^k = 1 (mod n).

Parameters: n (int) – A positive integer n > 1.
Returns: The first, smallest primitive root of unity modulo n.
Return type: int

galois.primitive_roots(n)[source]¶

Finds all primitive n-th roots of unity that satisfy x^k = 1 (mod n).

Parameters: n (int) – A positive integer n > 1.
Returns: An array of integer roots of unity modulo n.
Return type: np.ndarray