galois¶
A Python 3 numpy extension for Galois fields.
Classes
|
asdf |
|
asdf |
|
asdf |
Class Factory Functions
|
Factory function to construct Galois field array classes of type GF(p^m). |
|
Factory function to construct Galois field array classes of type GF(p). |
Functions
|
Implements the Carmichael function to find the smallest positive integer m such that a^m = 1 (mod n) for 1 <= a < n. |
Implements the Chinese Remainder Theorem (CRT). |
|
|
Implements the Euclidean Algorithm to find the greatest common divisor of two integers. |
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. |
|
Implements the Extended Euclidean Algorithm to find the integer multiplicands of a and b, such that a*x + b*y = gcd(a,b). |
|
|
Computes the positive factors of the integer x. |
|
Determines if x is prime. |
|
Finds the minimal polynomial of a over the specified Galois field. |
|
Returns the closest prime p > x. |
|
Returns the closest prime p <= x. |
Computes the prime factors of the positive integer x. |
|
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
-
-
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)
-
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
-
property
str
¶
-
classmethod
-
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.
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.
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
Moon, “Error Correction Coding”, Section 5.2.2: The Euclidean Algorithm and Euclidean Domains, p. 181
-
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
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._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.
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}]\).