galois

A performant numpy extension for Galois fields.

Classes

GF2(array[, dtype])

asdf

GF2mBase(*args, **kwargs)

asdf

GFBase(array[, dtype])

asdf

GFpBase(*args, **kwargs)

asdf

Poly(coeffs[, field, order])

A polynomial class with coefficients in any Galois field.

Class Factory Functions

GF2m_factory(m[, mode, rebuild])

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

GF_factory(p, m[, prim_poly, rebuild])

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

GFp_factory(p[, mode, 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).

conway_polynomial(p, n)

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 a*x + b*y = 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 nearest prime p > x.

prev_prime(x)

Returns the nearest 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 (3 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])
classmethod target(target)[source]

Retarget the just-in-time compiled numba ufuncs.

Parameters

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

alpha = GF2(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.GF2mBase(*args, **kwargs)[source]

Bases: galois.gf.GFBase

asdf

Note

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

classmethod target(target, mode='lookup', rebuild=False)[source]

Retarget the just-in-time compiled numba ufuncs.

Parameters

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

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.

classmethod target(target, mode='lookup', rebuild=False)[source]

Retarget the just-in-time compiled numba ufuncs.

Parameters

target (str) – The numba JIT target processor, either “cpu”, “parallel”, or “cuda”.

class galois.Poly(coeffs, field=None, order='desc')[source]

Bases: object

A polynomial class with coefficients in any Galois field.

Parameters

  • coeffs (array_like) – List of polynomial coefficients of type Galois field array, np.ndarray, list, or tuple. The first element is the highest-degree element if order=”desc” or the first element is the 0-th degree element if order=”asc”.

  • field (galois.GFBase, optional) – Optionally specify the field to which the coefficients belong. The default field is galois.GF2. If coeffs is a Galois field array, then that field is used and the field parameter is ignored.

  • order (str, optional) – The interpretation of the coefficient degrees, either “desc” (default) or “asc”. For “desc”, the first element of coeffs is the highest degree coefficient (x^(N-1)) and the last element is the 0-th degree element (x^0).

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 Decimal(decimal, field=<class 'galois.gf2.GF2'>, order='desc')[source]
classmethod NonZero(coeffs, degrees, field=<class 'galois.gf2.GF2'>)[source]

Examples

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

The polynomial coefficients as a Galois field array, in descending order if order=”desc” or ascending order if order=”asc”.

Type

GFBase

property coeffs_asc

The polynomial coefficients as a Galois field array in exponent-ascending order, i.e. the first element corresponds to x^0 and the last element corresponds to x^N-1.

Type

GFBase

property coeffs_desc

The polynomial coefficients as a Galois field array in exponent-descending order, i.e. the first element corresponds to x^N-1 and the last element corresponds to x^0.

Type

GFBase

property decimal
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 order

The interpretation of the ordering of the polynomial coefficients. coeffs are in exponent-descending order if order=”desc” and in exponent-ascending order if order=”asc”.

Type

str

property str
galois.GF2m_factory(m, mode='auto', rebuild=False)[source]

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

Parameters

  • p (int) – The prime characteristic of the field GF(2^m).

  • 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.GF2mBase.

Return type

galois.GF2mBase

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, mode='auto', 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.conway_polynomial(p, n)[source]
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

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

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 nearest prime p > x.

Parameters

x (int) – A positive integer.

Returns

The nearest prime p > x.

Return type

int

galois.prev_prime(x)[source]

Returns the nearest prime p <= x.

Parameters

x (int) – A positive integer.

Returns

The nearest 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