galois

A Python 3 numpy extension for Galois fields.

Classes

GF2(array)

asdf

GFp(*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 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 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_roots(n)

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

class galois.GF2(array)[source]

Bases: galois.gf._GF

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], dtype=uint8)

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

Arithmetic with GF2 arrays

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

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

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

# Element-wise division
In [4]: a / b
Out[4]: GF2([1, 0, 1, 1], dtype=uint8)
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

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.GFp(*args, **kwargs)[source]

Bases: galois.gf._GF

asdf

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.GF2 or galois.GFp

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 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._GF.

Return type

galois.GF2 or galois.GFp

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.GFp.

Return type

galois.GFp

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

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._GF) – 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_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