galois¶
A performant numpy extension for Galois fields.
Galois Fields¶
|
Factory function to construct a Galois field array class of type \(\mathrm{GF}(p^m)\). |
|
Create an array over \(\mathrm{GF}(p^m)\). |
|
Defines a metaclass for all |
|
A pre-created Galois field array class for \(\mathrm{GF}(2)\). |
Prime Fields¶
|
Factory function to construct a Galois field array class of type \(\mathrm{GF}(p^m)\). |
|
Determines if \(n\) is prime. |
|
Finds the smallest primitive root modulo \(n\). |
|
Finds all primitive roots modulo \(n\). |
|
Determines if \(g\) is a primitive root modulo \(n\). |
Extension Fields¶
|
Factory function to construct a Galois field array class of type \(\mathrm{GF}(p^m)\). |
|
Returns the degree-\(n\) Conway polynomial \(C_{p,n}\) over \(\mathrm{GF}(p)\). |
|
Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is irreducible. |
|
Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is primitive. |
|
Finds the smallest primitive element \(g(x)\) of the Galois field \(\mathrm{GF}(p^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\). |
|
Finds all primitive elements \(g(x)\) of the Galois field \(\mathrm{GF}(p^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\). |
|
Determines if \(g(x)\) is a primitive element of the Galois field \(\mathrm{GF}(p^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\). |
Galois Fields for Cryptography¶
|
Returns the Galois field for the first Oakley group from RFC 2409. |
|
Returns the Galois field for the second Oakley group from RFC 2409. |
|
Returns the Galois field for the third Oakley group from RFC 2409. |
|
Returns the Galois field for the fourth Oakley group from RFC 2409. |
Polynomials over Galois Fields¶
|
Create a polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\). |
|
Finds the greatest common divisor of two polynomials \(a(x)\) and \(b(x)\) over \(\mathrm{GF}(q)\). |
|
Efficiently exponentiates a polynomial \(f(x)\) to the power \(k\) reducing by modulo \(g(x)\), \(f(x)^k\ \textrm{mod}\ g(x)\). |
|
Determines whether the polynomial is monic, i.e. having leading coefficient equal to 1. |
|
Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is irreducible. |
|
Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is primitive. |
Modular Arithmetic¶
|
Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = \mathrm{gcd}(a, b)\). |
|
Computes the least common multiple of the integer arguments. |
|
Solves the simultaneous system of congruences for \(x\). |
|
Computes the integer square root of \(n\) such that \(\textrm{isqrt}(n)^2 \le n\). |
|
Efficiently exponentiates an integer \(a^k (\textrm{mod}\ m)\). |
|
Determines whether the multiplicative group \(\mathbb{Z}{_n^\times}\) is cyclic. |
|
Finds the smallest positive integer \(m\) such that \(a^m \equiv 1\ (\textrm{mod}\ n)\) for every integer \(a\) in \(1 \le a < n\) that is coprime to \(n\). |
Counts the positive integers (totatives) in \(1 \le k < n\) that are relatively prime to \(n\), i.e. \(\mathrm{gcd}(n, k) = 1\). |
|
|
Returns the positive integers (totatives) in \(1 \le k < n\) that are coprime with \(n\), i.e. \(\mathrm{gcd}(n, k) = 1\). |
Discrete Logarithms¶
|
Computes the discrete logarithm \(x = \textrm{log}_{\alpha}(\beta)\ (\textrm{mod}\ m)\). |
Primes¶
|
Returns all primes \(p\) for \(p \le n\). |
|
Returns the \(k\)-th prime. |
|
Returns the nearest prime \(p\), such that \(p \le n\). |
|
Returns the nearest prime \(p\), such that \(p > n\). |
|
Returns a random prime \(p\) with \(b\) bits, such that \(2^b \le p < 2^{b+1}\). |
|
Returns all known Mersenne exponents \(e\) for \(e \le n\). |
|
Returns all known Mersenne primes \(p\) for \(p \le 2^n - 1\). |
Computes the prime factors of the positive integer \(n\). |
|
|
Determines if the positive integer \(n\) is \(B\)-smooth, i.e. all its prime factors satisfy \(p \le B\). |
|
Determines if \(n\) is prime. |
Determines if \(n\) is composite. |
|
|
Determines if \(n\) is composite. |
- class galois.GF2(array, dtype=None, copy=True, order='K', ndmin=0)¶
A pre-created Galois field array class for \(\mathrm{GF}(2)\).
This class is a subclass of
galois.GFArray
and has metaclassgalois.GFMeta
.Examples
This class is equivalent (and, in fact, identical) to the class returned from the Galois field array class constructor.
In [1]: print(galois.GF2) <class 'numpy.ndarray over GF(2)'> In [2]: GF2 = galois.GF(2); print(GF2) <class 'numpy.ndarray over GF(2)'> In [3]: GF2 is galois.GF2 Out[3]: True
The Galois field properties can be viewed by class attributes, see
galois.GFMeta
.# View a summary of the field's properties In [4]: print(galois.GF2.properties) GF(2): structure: Finite Field characteristic: 2 degree: 1 order: 2 irreducible_poly: Poly(x + 1, GF(2)) is_primitive_poly: True primitive_element: GF(1, order=2) # Or access each attribute individually In [5]: galois.GF2.irreducible_poly Out[5]: Poly(x + 1, GF(2)) In [6]: galois.GF2.is_prime_field Out[6]: True
The class’s constructor mimics the call signature of
numpy.array()
.# Construct a Galois field array from an iterable In [7]: galois.GF2([1,0,1,1,0,0,0,1]) Out[7]: GF([1, 0, 1, 1, 0, 0, 0, 1], order=2) # Or an iterable of iterables In [8]: galois.GF2([[1,0],[1,1]]) Out[8]: GF([[1, 0], [1, 1]], order=2) # Or a single integer In [9]: galois.GF2(1) Out[9]: GF(1, order=2)
- classmethod Elements(dtype=None)¶
Creates a Galois field array of the field’s elements \(\{0, \dots, p^m-1\}\).
- Parameters
dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.- Returns
A Galois field array of all the field’s elements.
- Return type
Examples
In [1]: GF = galois.GF(31) In [2]: GF.Elements() Out[2]: GF([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], order=31)
- classmethod Identity(size, dtype=None)¶
Creates an \(n \times n\) Galois field identity matrix.
- Parameters
size (int) – The size \(n\) along one axis of the matrix. The resulting array has shape
(size,size)
.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field identity matrix of shape
(size, size)
.- Return type
Examples
In [1]: GF = galois.GF(31) In [2]: GF.Identity(4) Out[2]: GF([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]], order=31)
- classmethod Ones(shape, dtype=None)¶
Creates a Galois field array with all ones.
- Parameters
shape (tuple) – A numpy-compliant
shape
tuple, seenumpy.ndarray.shape
. An empty tuple()
represents a scalar. A single integer or 1-tuple, e.g.N
or(N,)
, represents the size of a 1-dim array. An n-tuple, e.g.(M,N)
, represents an n-dim array with each element indicating the size in each dimension.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of ones.
- Return type
Examples
In [1]: GF = galois.GF(31) In [2]: GF.Ones((2,5)) Out[2]: GF([[1, 1, 1, 1, 1], [1, 1, 1, 1, 1]], order=31)
- classmethod Random(shape=(), low=0, high=None, dtype=None)¶
Creates a Galois field array with random field elements.
- Parameters
shape (tuple) – A numpy-compliant
shape
tuple, seenumpy.ndarray.shape
. An empty tuple()
represents a scalar. A single integer or 1-tuple, e.g.N
or(N,)
, represents the size of a 1-dim array. An n-tuple, e.g.(M,N)
, represents an n-dim array with each element indicating the size in each dimension.low (int, optional) – The lowest value (inclusive) of a random field element. The default is 0.
high (int, optional) – The highest value (exclusive) of a random field element. The default is
None
which represents the field’s order \(p^m\).dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of random field elements.
- Return type
Examples
In [1]: GF = galois.GF(31) In [2]: GF.Random((2,5)) Out[2]: GF([[23, 28, 27, 9, 19], [ 4, 4, 11, 25, 12]], order=31)
- classmethod Range(start, stop, step=1, dtype=None)¶
Creates a Galois field array with a range of field elements.
- Parameters
start (int) – The starting value (inclusive).
stop (int) – The stopping value (exclusive).
step (int, optional) – The space between values. The default is 1.
dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of a range of field elements.
- Return type
Examples
In [1]: GF = galois.GF(31) In [2]: GF.Range(10,20) Out[2]: GF([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], order=31)
- classmethod Vandermonde(a, m, n, dtype=None)¶
Creates a \(m \times n\) Vandermonde matrix of \(a \in \mathrm{GF}(p^m)\).
- Parameters
a (int, galois.GFArray) – An element of \(\mathrm{GF}(p^m)\).
m (int) – The number of rows in the Vandermonde matrix.
n (int) – The number of columns in the Vandermonde matrix.
dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
The \(m \times n\) Vandermonde matrix.
- Return type
Examples
In [1]: GF = galois.GF(2**3) In [2]: a = GF.primitive_element In [3]: V = GF.Vandermonde(a, 7, 7) In [4]: with GF.display("power"): ...: print(V) ...: GF([[1 , 1 , 1 , 1 , 1 , 1 , 1 ], [1 , α , α^2, α^3, α^4, α^5, α^6], [1 , α^2, α^4, α^6, α , α^3, α^5], [1 , α^3, α^6, α^2, α^5, α , α^4], [1 , α^4, α , α^5, α^2, α^6, α^3], [1 , α^5, α^3, α , α^6, α^4, α^2], [1 , α^6, α^5, α^4, α^3, α^2, α ]], order=2^3)
- classmethod Vector(array, dtype=None)¶
Creates a Galois field array over \(\mathrm{GF}(p^m)\) from length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).
- Parameters
array (array_like) – The input array with field elements in \(\mathrm{GF}(p)\) to be converted to a Galois field array in \(\mathrm{GF}(p^m)\). The last dimension of the input array must be \(m\). An input array with shape
(n1, n2, m)
has output shape(n1, n2)
.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array over \(\mathrm{GF}(p^m)\).
- Return type
Examples
In [1]: GF = galois.GF(2**6) In [2]: vec = galois.GF2.Random((3,6)); vec Out[2]: GF([[1, 0, 0, 1, 0, 1], [1, 0, 0, 1, 1, 1], [1, 0, 0, 1, 1, 0]], order=2) In [3]: a = GF.Vector(vec); a Out[3]: GF([37, 39, 38], order=2^6) In [4]: with GF.display("poly"): ...: print(a) ...: GF([α^5 + α^2 + 1, α^5 + α^2 + α + 1, α^5 + α^2 + α], order=2^6) In [5]: a.vector() Out[5]: GF([[1, 0, 0, 1, 0, 1], [1, 0, 0, 1, 1, 1], [1, 0, 0, 1, 1, 0]], order=2)
- classmethod Zeros(shape, dtype=None)¶
Creates a Galois field array with all zeros.
- Parameters
shape (tuple) – A numpy-compliant
shape
tuple, seenumpy.ndarray.shape
. An empty tuple()
represents a scalar. A single integer or 1-tuple, e.g.N
or(N,)
, represents the size of a 1-dim array. An n-tuple, e.g.(M,N)
, represents an n-dim array with each element indicating the size in each dimension.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of zeros.
- Return type
Examples
In [1]: GF = galois.GF(31) In [2]: GF.Zeros((2,5)) Out[2]: GF([[0, 0, 0, 0, 0], [0, 0, 0, 0, 0]], order=31)
- lu_decompose()¶
Decomposes the input array into the product of lower and upper triangular matrices.
- Returns
galois.GFArray – The lower triangular matrix.
galois.GFArray – The upper triangular matrix.
Examples
In [1]: GF = galois.GF(5) # Not every square matrix has an LU decomposition In [2]: A = GF([[2, 4, 4, 1], [3, 3, 1, 4], [4, 3, 4, 2], [4, 4, 3, 1]]) In [3]: L, U = A.lu_decompose() In [4]: L Out[4]: GF([[1, 0, 0, 0], [4, 1, 0, 0], [2, 0, 1, 0], [2, 3, 0, 1]], order=5) In [5]: U Out[5]: GF([[2, 4, 4, 1], [0, 2, 0, 0], [0, 0, 1, 0], [0, 0, 0, 4]], order=5) # A = L U In [6]: np.array_equal(A, L @ U) Out[6]: True
- lup_decompose()¶
Decomposes the input array into the product of lower and upper triangular matrices using partial pivoting.
- Returns
galois.GFArray – The lower triangular matrix.
galois.GFArray – The upper triangular matrix.
galois.GFArray – The permutation matrix.
Examples
In [1]: GF = galois.GF(5) In [2]: A = GF([[1, 3, 2, 0], [3, 4, 2, 3], [0, 2, 1, 4], [4, 3, 3, 1]]) In [3]: L, U, P = A.lup_decompose() In [4]: L Out[4]: GF([[1, 0, 0, 0], [0, 1, 0, 0], [3, 0, 1, 0], [4, 3, 2, 1]], order=5) In [5]: U Out[5]: GF([[1, 3, 2, 0], [0, 2, 1, 4], [0, 0, 1, 3], [0, 0, 0, 3]], order=5) In [6]: P Out[6]: GF([[1, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1]], order=5) # P A = L U In [7]: np.array_equal(P @ A, L @ U) Out[7]: True
- row_reduce(ncols=None)¶
Performs Gaussian elimination on the matrix to achieve reduced row echelon form.
Row reduction operations
Swap the position of any two rows.
Multiply a row by a non-zero scalar.
Add one row to a scalar multiple of another row.
- Parameters
ncols (int, optional) – The number of columns to perform Gaussian elimination over. The default is
None
which represents the number of columns of the input array.- Returns
The reduced row echelon form of the input array.
- Return type
Examples
In [1]: GF = galois.GF(31) In [2]: A = GF.Random((4,4)); A Out[2]: GF([[ 2, 15, 9, 13], [12, 24, 24, 20], [29, 29, 26, 30], [19, 22, 25, 10]], order=31) In [3]: A.row_reduce() Out[3]: GF([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]], order=31) In [4]: np.linalg.matrix_rank(A) Out[4]: 4
One column is a linear combination of another.
In [5]: GF = galois.GF(31) In [6]: A = GF.Random((4,4)); A Out[6]: GF([[ 7, 1, 29, 14], [27, 22, 25, 15], [ 3, 22, 1, 22], [13, 20, 5, 22]], order=31) In [7]: A[:,2] = A[:,1] * GF(17); A Out[7]: GF([[ 7, 1, 17, 14], [27, 22, 2, 15], [ 3, 22, 2, 22], [13, 20, 30, 22]], order=31) In [8]: A.row_reduce() Out[8]: GF([[ 1, 0, 0, 0], [ 0, 1, 17, 0], [ 0, 0, 0, 1], [ 0, 0, 0, 0]], order=31) In [9]: np.linalg.matrix_rank(A) Out[9]: 3
One row is a linear combination of another.
In [10]: GF = galois.GF(31) In [11]: A = GF.Random((4,4)); A Out[11]: GF([[28, 16, 5, 3], [11, 26, 25, 27], [22, 28, 3, 10], [ 5, 7, 21, 18]], order=31) In [12]: A[3,:] = A[2,:] * GF(8); A Out[12]: GF([[28, 16, 5, 3], [11, 26, 25, 27], [22, 28, 3, 10], [21, 7, 24, 18]], order=31) In [13]: A.row_reduce() Out[13]: GF([[ 1, 0, 0, 20], [ 0, 1, 0, 14], [ 0, 0, 1, 5], [ 0, 0, 0, 0]], order=31) In [14]: np.linalg.matrix_rank(A) Out[14]: 3
- vector(dtype=None)¶
Converts the Galois field array over \(\mathrm{GF}(p^m)\) to length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).
For an input array with shape
(n1, n2)
, the output shape is(n1, n2, m)
.- Parameters
dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.- Returns
A Galois field array of length-\(m\) vectors over \(\mathrm{GF}(p)\).
- Return type
Examples
In [1]: GF = galois.GF(2**6) In [2]: a = GF.Random(3); a Out[2]: GF([59, 32, 11], order=2^6) In [3]: vec = a.vector(); vec Out[3]: GF([[1, 1, 1, 0, 1, 1], [1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 1]], order=2) In [4]: GF.Vector(vec) Out[4]: GF([59, 32, 11], order=2^6)
- class galois.GFArray(array, dtype=None, copy=True, order='K', ndmin=0)¶
Create an array over \(\mathrm{GF}(p^m)\).
The
galois.GFArray
class is a parent class for all Galois field array classes. Any Galois field \(\mathrm{GF}(p^m)\) with prime characteristic \(p\) and positive integer \(m\), can be constructed by calling the class factorygalois.GF(p**m)
.Warning
This is an abstract base class for all Galois field array classes.
galois.GFArray
cannot be instantiated directly. Instead, Galois field array classes are created usinggalois.GF
.For example, one can create the \(\mathrm{GF}(7)\) field array class as follows:
In [1]: GF7 = galois.GF(7) In [2]: print(GF7) <class 'numpy.ndarray over GF(7)'>
This subclass can then be used to instantiate arrays over \(\mathrm{GF}(7)\).
In [3]: GF7([3,5,0,2,1]) Out[3]: GF([3, 5, 0, 2, 1], order=7) In [4]: GF7.Random((2,5)) Out[4]: GF([[2, 0, 0, 0, 0], [5, 6, 5, 2, 6]], order=7)
galois.GFArray
is a subclass ofnumpy.ndarray
. Thegalois.GFArray
constructor has the same syntax asnumpy.array()
. The returnedgalois.GFArray
object is an array that can be acted upon like any other numpy array.- Parameters
array (array_like) – The input array to be converted to a Galois field array. The input array is copied, so the original array is unmodified by changes to the Galois field array. Valid input array types are
numpy.ndarray
,list
ortuple
of int or str,int
, orstr
.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.copy (bool, optional) – The
copy
keyword argument fromnumpy.array()
. The default isTrue
which makes a copy of the input object is it’s an array.order ({
"K"
,"A"
,"C"
,"F"
}, optional) – Theorder
keyword argument fromnumpy.array()
. Valid values are"K"
(default),"A"
,"C"
, or"F"
.ndmin (int, optional) – The
ndmin
keyword argument fromnumpy.array()
. The minimum number of dimensions of the output. The default is 0.
- Returns
The copied input array as a \(\mathrm{GF}(p^m)\) field array.
- Return type
Examples
Construct various kinds of Galois fields using
galois.GF
.# Construct a GF(2^m) class In [5]: GF256 = galois.GF(2**8); print(GF256) <class 'numpy.ndarray over GF(2^8)'> # Construct a GF(p) class In [6]: GF571 = galois.GF(571); print(GF571) <class 'numpy.ndarray over GF(571)'> # Construct a very large GF(2^m) class In [7]: GF2m = galois.GF(2**100); print(GF2m) <class 'numpy.ndarray over GF(2^100)'> # Construct a very large GF(p) class In [8]: GFp = galois.GF(36893488147419103183); print(GFp) <class 'numpy.ndarray over GF(36893488147419103183)'>
Depending on the field’s order (size), only certain
dtype
values will be supported.In [9]: GF256.dtypes Out[9]: [numpy.uint8, numpy.uint16, numpy.uint32, numpy.int16, numpy.int32, numpy.int64] In [10]: GF571.dtypes Out[10]: [numpy.uint16, numpy.uint32, numpy.int16, numpy.int32, numpy.int64]
Very large fields, which can’t be represented using
np.int64
, can only be represented asdtype=np.object_
.In [11]: GF2m.dtypes Out[11]: [numpy.object_] In [12]: GFp.dtypes Out[12]: [numpy.object_]
Newly-created arrays will use the smallest, valid dtype.
In [13]: a = GF256.Random(10); a Out[13]: GF([145, 186, 148, 101, 174, 134, 182, 150, 200, 51], order=2^8) In [14]: a.dtype Out[14]: dtype('uint8')
This can be explicitly set by specifying the
dtype
keyword argument.In [15]: a = GF256.Random(10, dtype=np.uint32); a Out[15]: GF([139, 12, 250, 211, 128, 3, 234, 47, 118, 88], order=2^8) In [16]: a.dtype Out[16]: dtype('uint32')
Arrays can also be created explicitly by converting an “array-like” object.
# Construct a Galois field array from a list In [17]: l = [142, 27, 92, 253, 103]; l Out[17]: [142, 27, 92, 253, 103] In [18]: GF256(l) Out[18]: GF([142, 27, 92, 253, 103], order=2^8) # Construct a Galois field array from an existing numpy array In [19]: x_np = np.array(l, dtype=np.int64); x_np Out[19]: array([142, 27, 92, 253, 103]) In [20]: GF256(l) Out[20]: GF([142, 27, 92, 253, 103], order=2^8)
Arrays can also be created by “view casting” from an existing numpy array. This avoids a copy operation, which is especially useful for large data already brought into memory.
In [21]: a = x_np.view(GF256); a Out[21]: GF([142, 27, 92, 253, 103], order=2^8) # Changing `x_np` will change `a` In [22]: x_np[0] = 0; x_np Out[22]: array([ 0, 27, 92, 253, 103]) In [23]: a Out[23]: GF([ 0, 27, 92, 253, 103], order=2^8)
- classmethod Elements(dtype=None)¶
Creates a Galois field array of the field’s elements \(\{0, \dots, p^m-1\}\).
- Parameters
dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.- Returns
A Galois field array of all the field’s elements.
- Return type
Examples
In [24]: GF = galois.GF(31) In [25]: GF.Elements() Out[25]: GF([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], order=31)
- classmethod Identity(size, dtype=None)[source]¶
Creates an \(n \times n\) Galois field identity matrix.
- Parameters
size (int) – The size \(n\) along one axis of the matrix. The resulting array has shape
(size,size)
.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field identity matrix of shape
(size, size)
.- Return type
Examples
In [26]: GF = galois.GF(31) In [27]: GF.Identity(4) Out[27]: GF([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]], order=31)
- classmethod Ones(shape, dtype=None)¶
Creates a Galois field array with all ones.
- Parameters
shape (tuple) – A numpy-compliant
shape
tuple, seenumpy.ndarray.shape
. An empty tuple()
represents a scalar. A single integer or 1-tuple, e.g.N
or(N,)
, represents the size of a 1-dim array. An n-tuple, e.g.(M,N)
, represents an n-dim array with each element indicating the size in each dimension.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of ones.
- Return type
Examples
In [28]: GF = galois.GF(31) In [29]: GF.Ones((2,5)) Out[29]: GF([[1, 1, 1, 1, 1], [1, 1, 1, 1, 1]], order=31)
- classmethod Random(shape=(), low=0, high=None, dtype=None)¶
Creates a Galois field array with random field elements.
- Parameters
shape (tuple) – A numpy-compliant
shape
tuple, seenumpy.ndarray.shape
. An empty tuple()
represents a scalar. A single integer or 1-tuple, e.g.N
or(N,)
, represents the size of a 1-dim array. An n-tuple, e.g.(M,N)
, represents an n-dim array with each element indicating the size in each dimension.low (int, optional) – The lowest value (inclusive) of a random field element. The default is 0.
high (int, optional) – The highest value (exclusive) of a random field element. The default is
None
which represents the field’s order \(p^m\).dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of random field elements.
- Return type
Examples
In [30]: GF = galois.GF(31) In [31]: GF.Random((2,5)) Out[31]: GF([[11, 25, 4, 30, 27], [17, 16, 6, 30, 14]], order=31)
- classmethod Range(start, stop, step=1, dtype=None)¶
Creates a Galois field array with a range of field elements.
- Parameters
start (int) – The starting value (inclusive).
stop (int) – The stopping value (exclusive).
step (int, optional) – The space between values. The default is 1.
dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of a range of field elements.
- Return type
Examples
In [32]: GF = galois.GF(31) In [33]: GF.Range(10,20) Out[33]: GF([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], order=31)
- classmethod Vandermonde(a, m, n, dtype=None)[source]¶
Creates a \(m \times n\) Vandermonde matrix of \(a \in \mathrm{GF}(p^m)\).
- Parameters
a (int, galois.GFArray) – An element of \(\mathrm{GF}(p^m)\).
m (int) – The number of rows in the Vandermonde matrix.
n (int) – The number of columns in the Vandermonde matrix.
dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
The \(m \times n\) Vandermonde matrix.
- Return type
Examples
In [34]: GF = galois.GF(2**3) In [35]: a = GF.primitive_element In [36]: V = GF.Vandermonde(a, 7, 7) In [37]: with GF.display("power"): ....: print(V) ....: GF([[1 , 1 , 1 , 1 , 1 , 1 , 1 ], [1 , α , α^2, α^3, α^4, α^5, α^6], [1 , α^2, α^4, α^6, α , α^3, α^5], [1 , α^3, α^6, α^2, α^5, α , α^4], [1 , α^4, α , α^5, α^2, α^6, α^3], [1 , α^5, α^3, α , α^6, α^4, α^2], [1 , α^6, α^5, α^4, α^3, α^2, α ]], order=2^3)
- classmethod Vector(array, dtype=None)[source]¶
Creates a Galois field array over \(\mathrm{GF}(p^m)\) from length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).
- Parameters
array (array_like) – The input array with field elements in \(\mathrm{GF}(p)\) to be converted to a Galois field array in \(\mathrm{GF}(p^m)\). The last dimension of the input array must be \(m\). An input array with shape
(n1, n2, m)
has output shape(n1, n2)
.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array over \(\mathrm{GF}(p^m)\).
- Return type
Examples
In [38]: GF = galois.GF(2**6) In [39]: vec = galois.GF2.Random((3,6)); vec Out[39]: GF([[0, 1, 1, 0, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 0, 1, 1, 0]], order=2) In [40]: a = GF.Vector(vec); a Out[40]: GF([25, 32, 54], order=2^6) In [41]: with GF.display("poly"): ....: print(a) ....: GF([α^4 + α^3 + 1, α^5, α^5 + α^4 + α^2 + α], order=2^6) In [42]: a.vector() Out[42]: GF([[0, 1, 1, 0, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 0, 1, 1, 0]], order=2)
- classmethod Zeros(shape, dtype=None)¶
Creates a Galois field array with all zeros.
- Parameters
shape (tuple) – A numpy-compliant
shape
tuple, seenumpy.ndarray.shape
. An empty tuple()
represents a scalar. A single integer or 1-tuple, e.g.N
or(N,)
, represents the size of a 1-dim array. An n-tuple, e.g.(M,N)
, represents an n-dim array with each element indicating the size in each dimension.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of zeros.
- Return type
Examples
In [43]: GF = galois.GF(31) In [44]: GF.Zeros((2,5)) Out[44]: GF([[0, 0, 0, 0, 0], [0, 0, 0, 0, 0]], order=31)
- lu_decompose()[source]¶
Decomposes the input array into the product of lower and upper triangular matrices.
- Returns
galois.GFArray – The lower triangular matrix.
galois.GFArray – The upper triangular matrix.
Examples
In [45]: GF = galois.GF(5) # Not every square matrix has an LU decomposition In [46]: A = GF([[2, 4, 4, 1], [3, 3, 1, 4], [4, 3, 4, 2], [4, 4, 3, 1]]) In [47]: L, U = A.lu_decompose() In [48]: L Out[48]: GF([[1, 0, 0, 0], [4, 1, 0, 0], [2, 0, 1, 0], [2, 3, 0, 1]], order=5) In [49]: U Out[49]: GF([[2, 4, 4, 1], [0, 2, 0, 0], [0, 0, 1, 0], [0, 0, 0, 4]], order=5) # A = L U In [50]: np.array_equal(A, L @ U) Out[50]: True
- lup_decompose()[source]¶
Decomposes the input array into the product of lower and upper triangular matrices using partial pivoting.
- Returns
galois.GFArray – The lower triangular matrix.
galois.GFArray – The upper triangular matrix.
galois.GFArray – The permutation matrix.
Examples
In [51]: GF = galois.GF(5) In [52]: A = GF([[1, 3, 2, 0], [3, 4, 2, 3], [0, 2, 1, 4], [4, 3, 3, 1]]) In [53]: L, U, P = A.lup_decompose() In [54]: L Out[54]: GF([[1, 0, 0, 0], [0, 1, 0, 0], [3, 0, 1, 0], [4, 3, 2, 1]], order=5) In [55]: U Out[55]: GF([[1, 3, 2, 0], [0, 2, 1, 4], [0, 0, 1, 3], [0, 0, 0, 3]], order=5) In [56]: P Out[56]: GF([[1, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1]], order=5) # P A = L U In [57]: np.array_equal(P @ A, L @ U) Out[57]: True
- row_reduce(ncols=None)[source]¶
Performs Gaussian elimination on the matrix to achieve reduced row echelon form.
Row reduction operations
Swap the position of any two rows.
Multiply a row by a non-zero scalar.
Add one row to a scalar multiple of another row.
- Parameters
ncols (int, optional) – The number of columns to perform Gaussian elimination over. The default is
None
which represents the number of columns of the input array.- Returns
The reduced row echelon form of the input array.
- Return type
Examples
In [58]: GF = galois.GF(31) In [59]: A = GF.Random((4,4)); A Out[59]: GF([[ 1, 9, 19, 16], [30, 22, 19, 13], [14, 29, 10, 23], [ 2, 1, 0, 27]], order=31) In [60]: A.row_reduce() Out[60]: GF([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]], order=31) In [61]: np.linalg.matrix_rank(A) Out[61]: 4
One column is a linear combination of another.
In [62]: GF = galois.GF(31) In [63]: A = GF.Random((4,4)); A Out[63]: GF([[ 6, 4, 18, 20], [11, 10, 24, 11], [30, 30, 6, 25], [28, 27, 3, 11]], order=31) In [64]: A[:,2] = A[:,1] * GF(17); A Out[64]: GF([[ 6, 4, 6, 20], [11, 10, 15, 11], [30, 30, 14, 25], [28, 27, 25, 11]], order=31) In [65]: A.row_reduce() Out[65]: GF([[ 1, 0, 0, 0], [ 0, 1, 17, 0], [ 0, 0, 0, 1], [ 0, 0, 0, 0]], order=31) In [66]: np.linalg.matrix_rank(A) Out[66]: 3
One row is a linear combination of another.
In [67]: GF = galois.GF(31) In [68]: A = GF.Random((4,4)); A Out[68]: GF([[ 7, 2, 2, 13], [ 6, 0, 4, 15], [23, 14, 8, 7], [ 3, 24, 30, 8]], order=31) In [69]: A[3,:] = A[2,:] * GF(8); A Out[69]: GF([[ 7, 2, 2, 13], [ 6, 0, 4, 15], [23, 14, 8, 7], [29, 19, 2, 25]], order=31) In [70]: A.row_reduce() Out[70]: GF([[ 1, 0, 0, 10], [ 0, 1, 0, 6], [ 0, 0, 1, 12], [ 0, 0, 0, 0]], order=31) In [71]: np.linalg.matrix_rank(A) Out[71]: 3
- vector(dtype=None)[source]¶
Converts the Galois field array over \(\mathrm{GF}(p^m)\) to length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).
For an input array with shape
(n1, n2)
, the output shape is(n1, n2, m)
.- Parameters
dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.- Returns
A Galois field array of length-\(m\) vectors over \(\mathrm{GF}(p)\).
- Return type
Examples
In [72]: GF = galois.GF(2**6) In [73]: a = GF.Random(3); a Out[73]: GF([10, 49, 20], order=2^6) In [74]: vec = a.vector(); vec Out[74]: GF([[0, 0, 1, 0, 1, 0], [1, 1, 0, 0, 0, 1], [0, 1, 0, 1, 0, 0]], order=2) In [75]: GF.Vector(vec) Out[75]: GF([10, 49, 20], order=2^6)
- class galois.GFMeta(name, bases, namespace, **kwargs)¶
Defines a metaclass for all
galois.GFArray
classes.This metaclass gives
galois.GFArray
classes returned fromgalois.GF()
class methods and properties relating to its Galois field.- compile(mode, target='cpu')¶
Recompile the just-in-time compiled numba ufuncs with a new calculation mode or target.
- Parameters
mode (str) – The method of field computation, either
"jit-lookup"
,"jit-calculate"
,"python-calculate"
. The “jit-lookup” mode will use Zech log, log, and anti-log lookup tables for speed. The “jit-calculate” mode will not store any lookup tables, but perform field arithmetic on the fly. The “jit-calculate” mode is designed for large fields that cannot store lookup tables in RAM. Generally, “jit-calculate” is slower than “jit-lookup”. The “python-calculate” mode is reserved for extremely large fields. In this mode the ufuncs are not JIT-compiled, but are pur python functions operating on python ints. The list of valid modes for this field is ingalois.GFMeta.ufunc_modes
.target (str, optional) – The
target
keyword argument fromnumba.vectorize
, either"cpu"
,"parallel"
, or"cuda"
. The default is"cpu"
. For extremely large fields the only supported target is"cpu"
(which doesn’t use numba it uses pure python to calculate the field arithmetic). The list of valid targets for this field is ingalois.GFMeta.ufunc_targets
.
- display(mode='int')[source]¶
Sets the display mode for all Galois field arrays of this type.
The display mode can be set to either the integer representation, polynomial representation, or power representation. This function updates
display_mode
.For the power representation,
np.log()
is computed on each element. So for large fields without lookup tables, this may take longer than desired.- Parameters
mode (str, optional) – The field element display mode, either
"int"
(default),"poly"
, or"power"
.
Examples
Change the display mode by calling the
display()
method.In [1]: GF = galois.GF(2**8) In [2]: a = GF.Random(); a Out[2]: GF(133, order=2^8) # Change the display mode going forward In [3]: GF.display("poly"); a Out[3]: GF(α^7 + α^2 + 1, order=2^8) In [4]: GF.display("power"); a Out[4]: GF(α^128, order=2^8) # Reset to the default display mode In [5]: GF.display(); a Out[5]: GF(133, order=2^8)
The
display()
method can also be used as a context manager, as shown below.For the polynomial representation, when the primitive element is \(x \in \mathrm{GF}(p)[x]\) the polynomial indeterminate used is
α
.In [6]: GF = galois.GF(2**8) In [7]: print(GF.properties) GF(2^8): structure: Finite Field characteristic: 2 degree: 8 order: 256 irreducible_poly: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2)) is_primitive_poly: True primitive_element: GF(2, order=2^8) In [8]: a = GF.Random(); a Out[8]: GF(47, order=2^8) In [9]: with GF.display("poly"): ...: print(a) ...: GF(α^5 + α^3 + α^2 + α + 1, order=2^8) In [10]: with GF.display("power"): ....: print(a) ....: GF(α^69, order=2^8)
But when the primitive element is not \(x \in \mathrm{GF}(p)[x]\), the polynomial indeterminate used is
x
.In [11]: GF = galois.GF(2**8, irreducible_poly=galois.Poly.Degrees([8,4,3,1,0])) In [12]: print(GF.properties) GF(2^8): structure: Finite Field characteristic: 2 degree: 8 order: 256 irreducible_poly: Poly(x^8 + x^4 + x^3 + x + 1, GF(2)) is_primitive_poly: False primitive_element: GF(3, order=2^8) In [13]: a = GF.Random(); a Out[13]: GF(164, order=2^8) In [14]: with GF.display("poly"): ....: print(a) ....: GF(x^7 + x^5 + x^2, order=2^8) In [15]: with GF.display("power"): ....: print(a) ....: GF(α^23, order=2^8)
- property characteristic¶
The prime characteristic \(p\) of the Galois field \(\mathrm{GF}(p^m)\). Adding \(p\) copies of any element will always result in \(0\).
Examples
In [1]: GF = galois.GF(2**8) In [2]: GF.characteristic Out[2]: 2 In [3]: a = GF.Random(); a Out[3]: GF(32, order=2^8) In [4]: a * GF.characteristic Out[4]: GF(0, order=2^8)
In [5]: GF = galois.GF(31) In [6]: GF.characteristic Out[6]: 31 In [7]: a = GF.Random(); a Out[7]: GF(23, order=31) In [8]: a * GF.characteristic Out[8]: GF(0, order=31)
- Type
- property default_ufunc_mode¶
The default ufunc arithmetic mode for this Galois field.
Examples
In [1]: galois.GF(2).default_ufunc_mode Out[1]: 'jit-calculate' In [2]: galois.GF(2**8).default_ufunc_mode Out[2]: 'jit-lookup' In [3]: galois.GF(31).default_ufunc_mode Out[3]: 'jit-lookup' In [4]: galois.GF(2**100).default_ufunc_mode Out[4]: 'python-calculate'
- Type
- property degree¶
The prime characteristic’s degree \(m\) of the Galois field \(\mathrm{GF}(p^m)\). The degree is a positive integer.
Examples
In [1]: galois.GF(2).degree Out[1]: 1 In [2]: galois.GF(2**8).degree Out[2]: 8 In [3]: galois.GF(31).degree Out[3]: 1 # galois.GF(7**5).degree
- Type
- property display_mode¶
The representation of Galois field elements, either
"int"
,"poly"
, or"power"
. This can be changed withdisplay()
.Examples
For the polynomial representation, when the primitive element is \(x \in \mathrm{GF}(p)[x]\) the polynomial indeterminate used is
α
.In [1]: GF = galois.GF(2**8) In [2]: print(GF.properties) GF(2^8): structure: Finite Field characteristic: 2 degree: 8 order: 256 irreducible_poly: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2)) is_primitive_poly: True primitive_element: GF(2, order=2^8) In [3]: a = GF.Random(); a Out[3]: GF(199, order=2^8) In [4]: with GF.display("poly"): ...: print(a) ...: GF(α^7 + α^6 + α^2 + α + 1, order=2^8) In [5]: with GF.display("power"): ...: print(a) ...: GF(α^118, order=2^8)
But when the primitive element is not \(x \in \mathrm{GF}(p)[x]\), the polynomial indeterminate used is
x
.In [6]: GF = galois.GF(2**8, irreducible_poly=galois.Poly.Degrees([8,4,3,1,0])) In [7]: print(GF.properties) GF(2^8): structure: Finite Field characteristic: 2 degree: 8 order: 256 irreducible_poly: Poly(x^8 + x^4 + x^3 + x + 1, GF(2)) is_primitive_poly: False primitive_element: GF(3, order=2^8) In [8]: a = GF.Random(); a Out[8]: GF(34, order=2^8) In [9]: with GF.display("poly"): ...: print(a) ...: GF(x^5 + x, order=2^8) In [10]: with GF.display("power"): ....: print(a) ....: GF(α^29, order=2^8)
- Type
- property dtypes¶
List of valid integer
numpy.dtype
objects that are compatible with this Galois field. Valid data types are signed and unsinged integers that can represent decimal values in \([0, p^m)\).Examples
In [1]: galois.GF(2).dtypes Out[1]: [numpy.uint8, numpy.uint16, numpy.uint32, numpy.int8, numpy.int16, numpy.int32, numpy.int64] In [2]: galois.GF(2**8).dtypes Out[2]: [numpy.uint8, numpy.uint16, numpy.uint32, numpy.int16, numpy.int32, numpy.int64] In [3]: galois.GF(31).dtypes Out[3]: [numpy.uint8, numpy.uint16, numpy.uint32, numpy.int8, numpy.int16, numpy.int32, numpy.int64] # galois.GF(7**5).dtypes
For field’s with orders that cannot be represented by
numpy.int64
, the only valid dtype isnumpy.object_
.In [4]: galois.GF(2**100).dtypes Out[4]: [numpy.object_] In [5]: galois.GF(36893488147419103183).dtypes Out[5]: [numpy.object_]
- Type
- property irreducible_poly¶
The irreducible polynomial \(f(x)\) of the Galois field \(\mathrm{GF}(p^m)\). The irreducible polynomial is of degree \(m\) over \(\mathrm{GF}(p)\).
Examples
In [1]: galois.GF(2).irreducible_poly Out[1]: Poly(x + 1, GF(2)) In [2]: galois.GF(2**8).irreducible_poly Out[2]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2)) In [3]: galois.GF(31).irreducible_poly Out[3]: Poly(x + 28, GF(31)) # galois.GF(7**5).irreducible_poly
- Type
- property is_extension_field¶
Indicates if the field’s order is a prime power.
Examples
In [1]: galois.GF(2).is_extension_field Out[1]: False In [2]: galois.GF(2**8).is_extension_field Out[2]: True In [3]: galois.GF(31).is_extension_field Out[3]: False # galois.GF(7**5).is_extension_field
- Type
- property is_prime_field¶
Indicates if the field’s order is prime.
Examples
In [1]: galois.GF(2).is_prime_field Out[1]: True In [2]: galois.GF(2**8).is_prime_field Out[2]: False In [3]: galois.GF(31).is_prime_field Out[3]: True # galois.GF(7**5).is_prime_field
- Type
- property is_primitive_poly¶
Indicates whether the
irreducible_poly
is a primitive polynomial.Examples
In [1]: GF = galois.GF(2**8) In [2]: GF.irreducible_poly Out[2]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2)) In [3]: GF.primitive_element Out[3]: GF(2, order=2^8) # The irreducible polynomial is a primitive polynomial is the primitive element is a root In [4]: GF.irreducible_poly(GF.primitive_element, field=GF) Out[4]: GF(0, order=2^8) In [5]: GF.is_primitive_poly Out[5]: True
# Field used in AES In [6]: GF = galois.GF(2**8, irreducible_poly=galois.Poly.Degrees([8,4,3,1,0])) In [7]: GF.irreducible_poly Out[7]: Poly(x^8 + x^4 + x^3 + x + 1, GF(2)) In [8]: GF.primitive_element Out[8]: GF(3, order=2^8) # The irreducible polynomial is a primitive polynomial is the primitive element is a root In [9]: GF.irreducible_poly(GF.primitive_element, field=GF) Out[9]: GF(6, order=2^8) In [10]: GF.is_primitive_poly Out[10]: False
- Type
- property name¶
The Galois field name.
Examples
In [1]: galois.GF(2).name Out[1]: 'GF(2)' In [2]: galois.GF(2**8).name Out[2]: 'GF(2^8)' In [3]: galois.GF(31).name Out[3]: 'GF(31)' # galois.GF(7**5).name
- Type
- property order¶
The order \(p^m\) of the Galois field \(\mathrm{GF}(p^m)\). The order of the field is also equal to the field’s size.
Examples
In [1]: galois.GF(2).order Out[1]: 2 In [2]: galois.GF(2**8).order Out[2]: 256 In [3]: galois.GF(31).order Out[3]: 31 # galois.GF(7**5).order
- Type
- property prime_subfield¶
The prime subfield \(\mathrm{GF}(p)\) of the extension field \(\mathrm{GF}(p^m)\).
Examples
In [1]: print(galois.GF(2).prime_subfield.properties) GF(2): structure: Finite Field characteristic: 2 degree: 1 order: 2 irreducible_poly: Poly(x + 1, GF(2)) is_primitive_poly: True primitive_element: GF(1, order=2) In [2]: print(galois.GF(2**8).prime_subfield.properties) GF(2): structure: Finite Field characteristic: 2 degree: 1 order: 2 irreducible_poly: Poly(x + 1, GF(2)) is_primitive_poly: True primitive_element: GF(1, order=2) In [3]: print(galois.GF(31).prime_subfield.properties) GF(31): structure: Finite Field characteristic: 31 degree: 1 order: 31 irreducible_poly: Poly(x + 28, GF(31)) is_primitive_poly: True primitive_element: GF(3, order=31) # print(galois.GF(7**5).prime_subfield.properties)
- Type
- property primitive_element¶
A primitive element \(\alpha\) of the Galois field \(\mathrm{GF}(p^m)\). A primitive element is a multiplicative generator of the field, such that \(\mathrm{GF}(p^m) = \{0, 1, \alpha^1, \alpha^2, \dots, \alpha^{p^m - 2}\}\).
A primitive element is a root of the primitive polynomial \(f(x)\), such that \(f(\alpha) = 0\) over \(\mathrm{GF}(p^m)\).
Examples
In [1]: galois.GF(2).primitive_element Out[1]: GF(1, order=2) In [2]: galois.GF(2**8).primitive_element Out[2]: GF(2, order=2^8) In [3]: galois.GF(31).primitive_element Out[3]: GF(3, order=31) # galois.GF(7**5).primitive_element
- Type
- property primitive_elements¶
All primitive elements \(\alpha\) of the Galois field \(\mathrm{GF}(p^m)\). A primitive element is a multiplicative generator of the field, such that \(\mathrm{GF}(p^m) = \{0, 1, \alpha^1, \alpha^2, \dots, \alpha^{p^m - 2}\}\).
Examples
In [1]: galois.GF(2).primitive_elements Out[1]: GF([1], order=2) In [2]: galois.GF(2**8).primitive_elements Out[2]: GF([ 2, 4, 6, 9, 13, 14, 16, 18, 19, 20, 22, 24, 25, 27, 29, 30, 31, 34, 35, 40, 42, 43, 48, 49, 50, 52, 57, 60, 63, 65, 66, 67, 71, 72, 73, 74, 75, 76, 81, 82, 83, 84, 88, 90, 91, 92, 93, 95, 98, 99, 104, 105, 109, 111, 112, 113, 118, 119, 121, 122, 123, 126, 128, 129, 131, 133, 135, 136, 137, 140, 141, 142, 144, 148, 149, 151, 154, 155, 157, 158, 159, 162, 163, 164, 165, 170, 171, 175, 176, 177, 178, 183, 187, 188, 189, 192, 194, 198, 199, 200, 201, 202, 203, 204, 209, 210, 211, 212, 213, 216, 218, 222, 224, 225, 227, 229, 232, 234, 236, 238, 240, 243, 246, 247, 248, 249, 250, 254], order=2^8) In [3]: galois.GF(31).primitive_elements Out[3]: GF([ 3, 11, 12, 13, 17, 21, 22, 24], order=31) # galois.GF(7**5).primitive_elements
- Type
- property properties¶
A formmatted string displaying relevant properties of the Galois field.
Examples
In [1]: print(galois.GF(2).properties) GF(2): structure: Finite Field characteristic: 2 degree: 1 order: 2 irreducible_poly: Poly(x + 1, GF(2)) is_primitive_poly: True primitive_element: GF(1, order=2) In [2]: print(galois.GF(2**8).properties) GF(2^8): structure: Finite Field characteristic: 2 degree: 8 order: 256 irreducible_poly: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2)) is_primitive_poly: True primitive_element: GF(2, order=2^8) In [3]: print(galois.GF(31).properties) GF(31): structure: Finite Field characteristic: 31 degree: 1 order: 31 irreducible_poly: Poly(x + 28, GF(31)) is_primitive_poly: True primitive_element: GF(3, order=31) # print(galois.GF(7**5).properties)
- Type
- property short_name¶
- property structure¶
- property ufunc_mode¶
The mode for ufunc compilation, either
"jit-lookup"
,"jit-calculate"
,"python-calculate"
.Examples
In [1]: galois.GF(2).ufunc_mode Out[1]: 'jit-calculate' In [2]: galois.GF(2**8).ufunc_mode Out[2]: 'jit-lookup' In [3]: galois.GF(31).ufunc_mode Out[3]: 'jit-lookup' # galois.GF(7**5).ufunc_mode
- Type
- property ufunc_modes¶
All supported ufunc modes for this Galois field array class.
Examples
In [1]: galois.GF(2).ufunc_modes Out[1]: ['jit-calculate'] In [2]: galois.GF(2**8).ufunc_modes Out[2]: ['jit-lookup', 'jit-calculate'] In [3]: galois.GF(31).ufunc_modes Out[3]: ['jit-lookup', 'jit-calculate'] In [4]: galois.GF(2**100).ufunc_modes Out[4]: ['python-calculate']
- Type
- property ufunc_target¶
The numba target for the JIT-compiled ufuncs, either
"cpu"
,"parallel"
, or"cuda"
.Examples
In [1]: galois.GF(2).ufunc_target Out[1]: 'cpu' In [2]: galois.GF(2**8).ufunc_target Out[2]: 'cpu' In [3]: galois.GF(31).ufunc_target Out[3]: 'cpu' # galois.GF(7**5).ufunc_target
- Type
- property ufunc_targets¶
All supported ufunc targets for this Galois field array class.
Examples
In [1]: galois.GF(2).ufunc_targets Out[1]: ['cpu', 'parallel', 'cuda'] In [2]: galois.GF(2**8).ufunc_targets Out[2]: ['cpu', 'parallel', 'cuda'] In [3]: galois.GF(31).ufunc_targets Out[3]: ['cpu', 'parallel', 'cuda'] In [4]: galois.GF(2**100).ufunc_targets Out[4]: ['cpu']
- Type
- class galois.Poly(coeffs, field=None, order='desc')¶
Create a polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\).
The polynomial \(f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) has coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) in \(\mathrm{GF}(p^m)\).
- Parameters
coeffs (array_like) – List of polynomial coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) with type
galois.GFArray
,numpy.ndarray
,list
, ortuple
. The first element is the highest-degree element iforder="desc"
or the first element is the 0-th degree element iforder="asc"
.field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
None
which representsgalois.GF2
. Ifcoeffs
is a Galois field array, then that field is used and thefield
argument is ignored.order (str, optional) – The interpretation of the coefficient degrees, either
"desc"
(default) or"asc"
. For"desc"
, the first element ofcoeffs
is the highest degree coefficient \(x^{d}\)) and the last element is the 0-th degree element \(x^0\).
- Returns
The polynomial \(f(x)\).
- Return type
Examples
Create a polynomial over \(\mathrm{GF}(2)\).
In [1]: galois.Poly([1,0,1,1]) Out[1]: Poly(x^3 + x + 1, GF(2)) In [2]: galois.Poly.Degrees([3,1,0]) Out[2]: Poly(x^3 + x + 1, GF(2))
Create a polynomial over \(\mathrm{GF}(2^8)\).
In [3]: GF = galois.GF(2**8) In [4]: galois.Poly([124,0,223,0,0,15], field=GF) Out[4]: Poly(124x^5 + 223x^3 + 15, GF(2^8)) # Alternate way of constructing the same polynomial In [5]: galois.Poly.Degrees([5,3,0], coeffs=[124,223,15], field=GF) Out[5]: Poly(124x^5 + 223x^3 + 15, GF(2^8))
Polynomial arithmetic using binary operators.
In [6]: a = galois.Poly([117,0,63,37], field=GF); a Out[6]: Poly(117x^3 + 63x + 37, GF(2^8)) In [7]: b = galois.Poly([224,0,21], field=GF); b Out[7]: Poly(224x^2 + 21, GF(2^8)) In [8]: a + b Out[8]: Poly(117x^3 + 224x^2 + 63x + 48, GF(2^8)) In [9]: a - b Out[9]: Poly(117x^3 + 224x^2 + 63x + 48, GF(2^8)) # Compute the quotient of the polynomial division In [10]: a / b Out[10]: Poly(202x, GF(2^8)) # True division and floor division are equivalent In [11]: a / b == a // b Out[11]: True # Compute the remainder of the polynomial division In [12]: a % b Out[12]: Poly(198x + 37, GF(2^8)) # Compute both the quotient and remainder in one pass In [13]: divmod(a, b) Out[13]: (Poly(202x, GF(2^8)), Poly(198x + 37, GF(2^8)))
- classmethod Degrees(degrees, coeffs=None, field=None)[source]¶
Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its non-zero degrees.
- Parameters
degrees (list) – List of polynomial degrees with non-zero coefficients.
coeffs (array_like, optional) – List of corresponding non-zero coefficients. The default is
None
which corresponds to all one coefficients, i.e.[1,]*len(degrees)
.field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is`None` which represents
galois.GF2
.
- Returns
The polynomial \(f(x)\).
- Return type
Examples
Construct a polynomial over \(\mathrm{GF}(2)\) by specifying the degrees with non-zero coefficients.
In [1]: galois.Poly.Degrees([3,1,0]) Out[1]: Poly(x^3 + x + 1, GF(2))
Construct a polynomial over \(\mathrm{GF}(2^8)\) by specifying the degrees with non-zero coefficients.
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.Degrees([3,1,0], coeffs=[251,73,185], field=GF) Out[3]: Poly(251x^3 + 73x + 185, GF(2^8))
- classmethod Identity(field=<class 'numpy.ndarray over GF(2)'>)[source]¶
Constructs the identity polynomial \(f(x) = x\) over \(\mathrm{GF}(p^m)\).
- Parameters
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
galois.GF2
.- Returns
The polynomial \(f(x)\).
- Return type
Examples
Construct the identity polynomial over \(\mathrm{GF}(2)\).
In [1]: galois.Poly.Identity() Out[1]: Poly(x, GF(2))
Construct the identity polynomial over \(\mathrm{GF}(2^8)\).
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.Identity(field=GF) Out[3]: Poly(x, GF(2^8))
- classmethod Integer(integer, field=<class 'numpy.ndarray over GF(2)'>)[source]¶
Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its integer representation.
The integer value \(i\) represents the polynomial \(f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) over field \(\mathrm{GF}(p^m)\) if \(i = a_{d}(p^m)^{d} + a_{d-1}(p^m)^{d-1} + \dots + a_1(p^m) + a_0\) using integer arithmetic, not finite field arithmetic.
- Parameters
integer (int) – The integer representation of the polynomial \(f(x)\).
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
galois.GF2
.
- Returns
The polynomial \(f(x)\).
- Return type
Examples
Construct a polynomial over \(\mathrm{GF}(2)\) from its integer representation.
In [1]: galois.Poly.Integer(5) Out[1]: Poly(x^2 + 1, GF(2))
Construct a polynomial over \(\mathrm{GF}(2^8)\) from its integer representation.
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.Integer(13*256**3 + 117, field=GF) Out[3]: Poly(13x^3 + 117, GF(2^8))
- classmethod One(field=<class 'numpy.ndarray over GF(2)'>)[source]¶
Constructs the one polynomial \(f(x) = 1\) over \(\mathrm{GF}(p^m)\).
- Parameters
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
galois.GF2
.- Returns
The polynomial \(f(x)\).
- Return type
Examples
Construct the one polynomial over \(\mathrm{GF}(2)\).
In [1]: galois.Poly.One() Out[1]: Poly(1, GF(2))
Construct the one polynomial over \(\mathrm{GF}(2^8)\).
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.One(field=GF) Out[3]: Poly(1, GF(2^8))
- classmethod Random(degree, field=<class 'numpy.ndarray over GF(2)'>)[source]¶
Constructs a random polynomial over \(\mathrm{GF}(p^m)\) with degree \(d\).
- Parameters
degree (int) – The degree of the polynomial.
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
galois.GF2
.
- Returns
The polynomial \(f(x)\).
- Return type
Examples
Construct a random degree-\(5\) polynomial over \(\mathrm{GF}(2)\).
In [1]: galois.Poly.Random(5) Out[1]: Poly(x^5 + x^4 + x^3 + x, GF(2))
Construct a random degree-\(5\) polynomial over \(\mathrm{GF}(2^8)\).
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.Random(5, field=GF) Out[3]: Poly(125x^5 + 108x^4 + 77x^3 + 97x^2 + 43x + 73, GF(2^8))
- classmethod Roots(roots, multiplicities=None, field=None)[source]¶
Constructs a monic polynomial in \(\mathrm{GF}(p^m)[x]\) from its roots.
The polynomial \(f(x)\) with \(d\) roots \(\{r_0, r_1, \dots, r_{d-1}\}\) is:
\[ \begin{align}\begin{aligned}f(x) &= (x - r_0) (x - r_1) \dots (x - r_{d-1})\\f(x) &= a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\end{aligned}\end{align} \]- Parameters
roots (array_like) – List of roots in \(\mathrm{GF}(p^m)\) of the desired polynomial.
multiplicities (array_like, optional) – List of multiplicity of each root. The default is
None
which corresponds to all ones.field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is`None` which represents
galois.GF2
.
- Returns
The polynomial \(f(x)\).
- Return type
Examples
Construct a polynomial over \(\mathrm{GF}(2)\) from a list of its roots.
In [1]: roots = [0, 0, 1] In [2]: p = galois.Poly.Roots(roots); p Out[2]: Poly(x^3 + x^2, GF(2)) In [3]: p(roots) Out[3]: GF([0, 0, 0], order=2)
Construct a polynomial over \(\mathrm{GF}(2^8)\) from a list of its roots.
In [4]: GF = galois.GF(2**8) In [5]: roots = [121, 198, 225] In [6]: p = galois.Poly.Roots(roots, field=GF); p Out[6]: Poly(x^3 + 94x^2 + 174x + 89, GF(2^8)) In [7]: p(roots) Out[7]: GF([0, 0, 0], order=2^8)
- classmethod Zero(field=<class 'numpy.ndarray over GF(2)'>)[source]¶
Constructs the zero polynomial \(f(x) = 0\) over \(\mathrm{GF}(p^m)\).
- Parameters
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
galois.GF2
.- Returns
The polynomial \(f(x)\).
- Return type
Examples
Construct the zero polynomial over \(\mathrm{GF}(2)\).
In [1]: galois.Poly.Zero() Out[1]: Poly(0, GF(2))
Construct the zero polynomial over \(\mathrm{GF}(2^8)\).
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.Zero(field=GF) Out[3]: Poly(0, GF(2^8))
- derivative(k=1)[source]¶
Computes the \(k\)-th formal derivative \(\frac{d^k}{dx^k} f(x)\) of the polynomial \(f(x)\).
For the polynomial
\[f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\]the first formal derivative is defined as
\[p'(x) = (d) \cdot a_{d} x^{d-1} + (d-1) \cdot a_{d-1} x^{d-2} + \dots + (2) \cdot a_{2} x + a_1\]where \(\cdot\) represents scalar multiplication (repeated addition), not finite field multiplication, e.g. \(3 \cdot a = a + a + a\).
- Parameters
k (int, optional) – The number of derivatives to compute. 1 corresponds to \(p'(x)\), 2 corresponds to \(p''(x)\), etc. The default is 1.
- Returns
The \(k\)-th formal derivative of the polynomial \(f(x)\).
- Return type
References
Examples
Compute the derivatives of a polynomial over \(\mathrm{GF}(2)\).
In [1]: p = galois.Poly.Random(7); p Out[1]: Poly(x^7 + x^3 + x, GF(2)) In [2]: p.derivative() Out[2]: Poly(x^6 + x^2 + 1, GF(2)) # k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0 In [3]: p.derivative(2) Out[3]: Poly(0, GF(2))
Compute the derivatives of a polynomial over \(\mathrm{GF}(7)\).
In [4]: GF = galois.GF(7) In [5]: p = galois.Poly.Random(11, field=GF); p Out[5]: Poly(6x^11 + x^10 + 4x^9 + 6x^8 + x^6 + 5x^5 + 4x^4 + 5x^3 + 4x^2 + 5, GF(7)) In [6]: p.derivative() Out[6]: Poly(3x^10 + 3x^9 + x^8 + 6x^7 + 6x^5 + 4x^4 + 2x^3 + x^2 + x, GF(7)) In [7]: p.derivative(2) Out[7]: Poly(2x^9 + 6x^8 + x^7 + 2x^4 + 2x^3 + 6x^2 + 2x + 1, GF(7)) In [8]: p.derivative(3) Out[8]: Poly(4x^8 + 6x^7 + x^3 + 6x^2 + 5x + 2, GF(7)) # k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0 In [9]: p.derivative(7) Out[9]: Poly(0, GF(2))
Compute the derivatives of a polynomial over \(\mathrm{GF}(2^8)\).
In [10]: GF = galois.GF(2**8) In [11]: p = galois.Poly.Random(7, field=GF); p Out[11]: Poly(30x^7 + 194x^6 + 25x^5 + 236x^4 + 179x^3 + 13x^2 + 115x + 57, GF(2^8)) In [12]: p.derivative() Out[12]: Poly(30x^6 + 25x^4 + 179x^2 + 115, GF(2^8)) # k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0 In [13]: p.derivative(2) Out[13]: Poly(0, GF(2^8))
- roots(multiplicity=False)[source]¶
Calculates the roots \(r\) of the polynomial \(f(x)\), such that \(f(r) = 0\).
This implementation uses Chien’s search to find the roots \(\{r_0, r_1, \dots, r_{k-1}\}\) of the degree-\(d\) polynomial
\[f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0,\]where \(k \le d\). Then, \(f(x)\) can be factored as
\[f(x) = (x - r_0)^{m_0} (x - r_1)^{m_1} \dots (x - r_{k-1})^{m_{k-1}},\]where \(m_i\) is the multiplicity of root \(r_i\) and
\[\sum_{i=0}^{k-1} m_i = d.\]The Galois field elements can be represented as \(\mathrm{GF}(p^m) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{p^m-2}\}\), where \(\alpha\) is a primitive element of \(\mathrm{GF}(p^m)\).
\(0\) is a root of \(f(x)\) if:
\[a_0 = 0\]\(1\) is a root of \(f(x)\) if:
\[\sum_{j=0}^{d} a_j = 0\]The remaining elements of \(\mathrm{GF}(p^m)\) are powers of \(\alpha\). The following equations calculate \(p(\alpha^i)\), where \(\alpha^i\) is a root of \(f(x)\) if \(p(\alpha^i) = 0\).
\[ \begin{align}\begin{aligned}p(\alpha^i) &= a_{d}(\alpha^i)^{d} + a_{d-1}(\alpha^i)^{d-1} + \dots + a_1(\alpha^i) + a_0\\p(\alpha^i) &\overset{\Delta}{=} \lambda_{i,d} + \lambda_{i,d-1} + \dots + \lambda_{i,1} + \lambda_{i,0}\\p(\alpha^i) &= \sum_{j=0}^{d} \lambda_{i,j}\end{aligned}\end{align} \]The next power of \(\alpha\) can be easily calculated from the previous calculation.
\[ \begin{align}\begin{aligned}p(\alpha^{i+1}) &= a_{d}(\alpha^{i+1})^{d} + a_{d-1}(\alpha^{i+1})^{d-1} + \dots + a_1(\alpha^{i+1}) + a_0\\p(\alpha^{i+1}) &= a_{d}(\alpha^i)^{d}\alpha^d + a_{d-1}(\alpha^i)^{d-1}\alpha^{d-1} + \dots + a_1(\alpha^i)\alpha + a_0\\p(\alpha^{i+1}) &= \lambda_{i,d}\alpha^d + \lambda_{i,d-1}\alpha^{d-1} + \dots + \lambda_{i,1}\alpha + \lambda_{i,0}\\p(\alpha^{i+1}) &= \sum_{j=0}^{d} \lambda_{i,j}\alpha^j\end{aligned}\end{align} \]- Parameters
multiplicity (bool, optional) – Optionally return the multiplicity of each root. The default is
False
, which only returns the unique roots.- Returns
galois.GFArray – Galois field array of roots of \(f(x)\).
np.ndarray – The multiplicity of each root. Only returned if
multiplicity=True
.
References
Examples
Find the roots of a polynomial over \(\mathrm{GF}(2)\).
In [1]: p = galois.Poly.Roots([0,]*7 + [1,]*13); p Out[1]: Poly(x^20 + x^19 + x^16 + x^15 + x^12 + x^11 + x^8 + x^7, GF(2)) In [2]: p.roots() Out[2]: GF([0, 1], order=2) In [3]: p.roots(multiplicity=True) Out[3]: (GF([0, 1], order=2), array([ 7, 13]))
Find the roots of a polynomial over \(\mathrm{GF}(2^8)\).
In [4]: GF = galois.GF(2**8) In [5]: p = galois.Poly.Roots([18,]*7 + [155,]*13 + [227,]*9, field=GF); p Out[5]: Poly(x^29 + 106x^28 + 27x^27 + 155x^26 + 230x^25 + 38x^24 + 78x^23 + 8x^22 + 46x^21 + 210x^20 + 248x^19 + 214x^18 + 172x^17 + 152x^16 + 82x^15 + 237x^14 + 172x^13 + 230x^12 + 141x^11 + 63x^10 + 103x^9 + 167x^8 + 199x^7 + 127x^6 + 254x^5 + 95x^4 + 93x^3 + 3x^2 + 4x + 208, GF(2^8)) In [6]: p.roots() Out[6]: GF([ 18, 155, 227], order=2^8) In [7]: p.roots(multiplicity=True) Out[7]: (GF([ 18, 155, 227], order=2^8), array([ 7, 13, 9]))
- property coeffs¶
The coefficients of the polynomial in degree-descending order. The entries of
galois.Poly.degrees
are paired withgalois.Poly.coeffs
.Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF) In [3]: p.coeffs Out[3]: GF([3, 0, 5, 2], order=7)
- Type
- property degree¶
The degree of the polynomial, i.e. the highest degree with non-zero coefficient.
Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF) In [3]: p.degree Out[3]: 3
- Type
- property degrees¶
An array of the polynomial degrees in degree-descending order. The entries of
galois.Poly.degrees
are paired withgalois.Poly.coeffs
.Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF) In [3]: p.degrees Out[3]: array([3, 2, 1, 0])
- Type
- property field¶
The Galois field array class to which the coefficients belong.
Examples
In [1]: a = galois.Poly.Random(5); a Out[1]: Poly(x^5 + x^3, GF(2)) In [2]: a.field Out[2]: <class 'numpy.ndarray over GF(2)'> In [3]: b = galois.Poly.Random(5, field=galois.GF(2**8)); b Out[3]: Poly(24x^5 + 200x^4 + 15x^3 + 116x^2 + 14x + 245, GF(2^8)) In [4]: b.field Out[4]: <class 'numpy.ndarray over GF(2^8)'>
- Type
- property integer¶
The integer representation of the polynomial. For polynomial \(f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) with elements in \(a_k \in \mathrm{GF}(p^m)\), the integer representation is \(i = a_{d} (p^m)^{d} + a_{d-1} (p^m)^{d-1} + \dots + a_1 (p^m) + a_0\) (using integer arithmetic, not finite field arithmetic).
Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF) In [3]: p.integer Out[3]: 1066 In [4]: p.integer == 3*7**3 + 5*7**1 + 2*7**0 Out[4]: True
- Type
- property nonzero_coeffs¶
The non-zero coefficients of the polynomial in degree-descending order. The entries of
galois.Poly.nonzero_degrees
are paired withgalois.Poly.nonzero_coeffs
.Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF) In [3]: p.nonzero_coeffs Out[3]: GF([3, 5, 2], order=7)
- Type
- property nonzero_degrees¶
An array of the polynomial degrees that have non-zero coefficients, in degree-descending order. The entries of
galois.Poly.nonzero_degrees
are paired withgalois.Poly.nonzero_coeffs
.Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF) In [3]: p.nonzero_degrees Out[3]: array([3, 1, 0])
- Type
- galois.GF(order, irreducible_poly=None, primitive_element=None, verify_irreducible=True, verify_primitive=True, mode='auto', target='cpu')¶
Factory function to construct a Galois field array class of type \(\mathrm{GF}(p^m)\).
The created class will be a subclass of
galois.GFArray
with metaclassgalois.GFMeta
. Thegalois.GFArray
inheritance provides thenumpy.ndarray
functionality. Thegalois.GFMeta
metaclass provides a variety of class attributes and methods relating to the finite field.- Parameters
order (int) – The order \(p^m\) of the field \(\mathrm{GF}(p^m)\). The order must be a prime power.
irreducible_poly (int, galois.Poly, optional) – Optionally specify an irreducible polynomial of degree \(m\) over \(\mathrm{GF}(p)\) that will define the Galois field arithmetic. An integer may be provided, which is the integer representation of the irreducible polynomial. Default is
None
which uses the Conway polynomial \(C_{p,m}\) obtained fromgalois.conway_poly()
.primitive_element (int, galois.Poly, optional) – Optionally specify a primitive element of the field \(\mathrm{GF}(p^m)\). A primitive element is a generator of the multiplicative group of the field. For prime fields \(\mathrm{GF}(p)\), the primitive element must be an integer and is a primitive root modulo \(p\). For extension fields \(\mathrm{GF}(p^m)\), the primitive element is a polynomial of degree less than \(m\) over \(\mathrm{GF}(p)\) or its integer representation. The default is
None
which usesgalois.primitive_root(p)
for prime fields andgalois.primitive_element(irreducible_poly)
for extension fields.verify_irreducible (bool, optional) – Indicates whether to verify that the specified irreducible polynomial is in fact irreducible. The default is
True
. For large irreducible polynomials that are already known to be irreducible (and may take a long time to verify), this argument can be set toFalse
.verify_primitive (bool, optional) – Indicates whether to verify that the specified primitive element is in fact a generator of the multiplicative group. The default is
True
.mode (str, optional) – The type of field computation, either
"auto"
,"jit-lookup"
, or"jit-calculate"
. The default is"auto"
. The “jit-lookup” mode will use Zech log, log, and anti-log lookup tables for efficient calculation. The “jit-calculate” mode will not store any lookup tables, but instead perform field arithmetic on the fly. The “jit-calculate” mode is designed for large fields that cannot or should not store lookup tables in RAM. Generally, “jit-calculate” mode will be slower than “jit-lookup”. The “auto” mode will determine whether to use “jit-lookup” or “jit-calculate” based on the field’s size. In “auto” mode, field’s withorder <= 2**16
will use the “jit-lookup” mode.target (str, optional) – The
target
keyword argument fromnumba.vectorize()
, either"cpu"
,"parallel"
, or"cuda"
.
- Returns
A new Galois field array class that is a subclass of
galois.GFArray
withgalois.GFMeta
metaclass.- Return type
Examples
Construct a Galois field array class with default irreducible polynomial and primitive element.
# Construct a GF(2^m) class In [1]: GF256 = galois.GF(2**8) # Notice the irreducible polynomial is primitive In [2]: print(GF256.properties) GF(2^8): structure: Finite Field characteristic: 2 degree: 8 order: 256 irreducible_poly: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2)) is_primitive_poly: True primitive_element: GF(2, order=2^8) In [3]: poly = GF256.irreducible_poly
Construct a Galois field specifying a specific irreducible polynomial.
# Field used in AES In [4]: GF256_AES = galois.GF(2**8, irreducible_poly=galois.Poly.Degrees([8,4,3,1,0])) In [5]: print(GF256_AES.properties) GF(2^8): structure: Finite Field characteristic: 2 degree: 8 order: 256 irreducible_poly: Poly(x^8 + x^4 + x^3 + x + 1, GF(2)) is_primitive_poly: False primitive_element: GF(3, order=2^8) # Construct a GF(p) class In [6]: GF571 = galois.GF(571); print(GF571.properties) GF(571): structure: Finite Field characteristic: 571 degree: 1 order: 571 irreducible_poly: Poly(x + 568, GF(571)) is_primitive_poly: True primitive_element: GF(3, order=571) # Construct a very large GF(2^m) class In [7]: GF2m = galois.GF(2**100); print(GF2m.properties) GF(2^100): structure: Finite Field characteristic: 2 degree: 100 order: 1267650600228229401496703205376 irreducible_poly: Poly(x^100 + x^57 + x^56 + x^55 + x^52 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^41 + x^37 + x^36 + x^35 + x^34 + x^31 + x^30 + x^27 + x^25 + x^24 + x^22 + x^20 + x^19 + x^16 + x^15 + x^11 + x^9 + x^8 + x^6 + x^5 + x^3 + 1, GF(2)) is_primitive_poly: True primitive_element: GF(2, order=2^100) # Construct a very large GF(p) class In [8]: GFp = galois.GF(36893488147419103183); print(GFp.properties) GF(36893488147419103183): structure: Finite Field characteristic: 36893488147419103183 degree: 1 order: 36893488147419103183 irreducible_poly: Poly(x + 36893488147419103180, GF(36893488147419103183)) is_primitive_poly: True primitive_element: GF(3, order=36893488147419103183)
See
galois.GFArray
for more examples of what Galois field arrays can do.
- galois.Oakley1()¶
Returns the Galois field for the first Oakley group from RFC 2409.
References
Examples
In [1]: GF = galois.Oakley1() In [2]: print(GF.properties) GF(1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919): structure: Finite Field characteristic: 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919 degree: 1 order: 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919 irreducible_poly: Poly(x + 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577917, GF(1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919)) is_primitive_poly: True primitive_element: GF(2, order=1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919)
- galois.Oakley2()¶
Returns the Galois field for the second Oakley group from RFC 2409.
References
Examples
In [1]: GF = galois.Oakley2() In [2]: print(GF.properties) GF(179769313486231590770839156793787453197860296048756011706444423684197180216158519368947833795864925541502180565485980503646440548199239100050792877003355816639229553136239076508735759914822574862575007425302077447712589550957937778424442426617334727629299387668709205606050270810842907692932019128194467627007): structure: Finite Field characteristic: 179769313486231590770839156793787453197860296048756011706444423684197180216158519368947833795864925541502180565485980503646440548199239100050792877003355816639229553136239076508735759914822574862575007425302077447712589550957937778424442426617334727629299387668709205606050270810842907692932019128194467627007 degree: 1 order: 179769313486231590770839156793787453197860296048756011706444423684197180216158519368947833795864925541502180565485980503646440548199239100050792877003355816639229553136239076508735759914822574862575007425302077447712589550957937778424442426617334727629299387668709205606050270810842907692932019128194467627007 irreducible_poly: Poly(x + 179769313486231590770839156793787453197860296048756011706444423684197180216158519368947833795864925541502180565485980503646440548199239100050792877003355816639229553136239076508735759914822574862575007425302077447712589550957937778424442426617334727629299387668709205606050270810842907692932019128194467627005, GF(179769313486231590770839156793787453197860296048756011706444423684197180216158519368947833795864925541502180565485980503646440548199239100050792877003355816639229553136239076508735759914822574862575007425302077447712589550957937778424442426617334727629299387668709205606050270810842907692932019128194467627007)) is_primitive_poly: True primitive_element: GF(2, order=179769313486231590770839156793787453197860296048756011706444423684197180216158519368947833795864925541502180565485980503646440548199239100050792877003355816639229553136239076508735759914822574862575007425302077447712589550957937778424442426617334727629299387668709205606050270810842907692932019128194467627007)
- galois.Oakley3()¶
Returns the Galois field for the third Oakley group from RFC 2409.
References
Examples
In [1]: GF = galois.Oakley3() In [2]: print(GF.properties) GF(2^155): structure: Finite Field characteristic: 2 degree: 155 order: 45671926166590716193865151022383844364247891968 irreducible_poly: Poly(x^155 + x^62 + 1, GF(2)) is_primitive_poly: False primitive_element: GF(123, order=2^155)
- galois.Oakley4()¶
Returns the Galois field for the fourth Oakley group from RFC 2409.
References
Examples
In [1]: GF = galois.Oakley4() In [2]: print(GF.properties) GF(2^185): structure: Finite Field characteristic: 2 degree: 185 order: 49039857307708443467467104868809893875799651909875269632 irreducible_poly: Poly(x^185 + x^69 + 1, GF(2)) is_primitive_poly: False primitive_element: GF(24, order=2^185)
- galois.carmichael(n)¶
Finds the smallest positive integer \(m\) such that \(a^m \equiv 1\ (\textrm{mod}\ n)\) for every integer \(a\) in \(1 \le a < n\) that is coprime to \(n\).
Implements the Carmichael function \(\lambda(n)\).
- Parameters
n (int) – A positive integer.
- Returns
The smallest positive integer \(m\) such that \(a^m \equiv 1 (\textrm{mod}\ n)\) for every \(a\) in \(1 \le a < n\) that is coprime to \(n\).
- Return type
References
Examples
In [1]: n = 20 In [2]: lambda_ = galois.carmichael(n); lambda_ Out[2]: 4 # Find the totatives that are relatively coprime with n In [3]: totatives = [i for i in range(n) if math.gcd(i, n) == 1]; totatives Out[3]: [1, 3, 7, 9, 11, 13, 17, 19] In [4]: for a in totatives: ...: result = pow(a, lambda_, n) ...: print("{:2d}^{} = {} (mod {})".format(a, lambda_, result, n)) ...: 1^4 = 1 (mod 20) 3^4 = 1 (mod 20) 7^4 = 1 (mod 20) 9^4 = 1 (mod 20) 11^4 = 1 (mod 20) 13^4 = 1 (mod 20) 17^4 = 1 (mod 20) 19^4 = 1 (mod 20) # For prime n, phi and lambda are always n-1 In [5]: galois.euler_totient(13), galois.carmichael(13) Out[5]: (12, 12)
- galois.conway_poly(p, n)¶
Returns the degree-\(n\) Conway polynomial \(C_{p,n}\) over \(\mathrm{GF}(p)\).
A Conway polynomial is a an irreducible and primitive polynomial over \(\mathrm{GF}(p)\) that provides a standard representation of \(\mathrm{GF}(p^n)\) as a splitting field of \(C_{p,n}\). Conway polynomials provide compatability between fields and their subfields, and hence are the common way to represent extension fields.
The Conway polynomial \(C_{p,n}\) is defined as the lexicographically-minimal monic irreducible polynomial of degree \(n\) over \(\mathrm{GF}(p)\) that is compatible with all \(C_{p,m}\) for \(m\) dividing \(n\).
This function uses Frank Luebeck’s Conway polynomial database for fast lookup, not construction.
- Parameters
- Returns
The degree-\(n\) Conway polynomial \(C_{p,n}\) over \(\mathrm{GF}(p)\).
- Return type
- Raises
LookupError – If the Conway polynomial \(C_{p,n}\) is not found in Frank Luebeck’s database.
Warning
If the \(\mathrm{GF}(p)\) field hasn’t previously been created, it will be created in this function since it’s needed for the construction of the return polynomial.
Examples
In [1]: galois.conway_poly(2, 100) Out[1]: Poly(x^100 + x^57 + x^56 + x^55 + x^52 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^41 + x^37 + x^36 + x^35 + x^34 + x^31 + x^30 + x^27 + x^25 + x^24 + x^22 + x^20 + x^19 + x^16 + x^15 + x^11 + x^9 + x^8 + x^6 + x^5 + x^3 + 1, GF(2)) In [2]: galois.conway_poly(7, 13) Out[2]: Poly(x^13 + 6x^2 + 4, GF(7))
- galois.crt(a, m)¶
Solves the simultaneous system of congruences for \(x\).
This function implements the Chinese Remainder Theorem.
\[ \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
Examples
In [1]: a = [0, 3, 4] In [2]: m = [3, 4, 5] In [3]: x = galois.crt(a, m); x Out[3]: 39 In [4]: for i in range(len(a)): ...: ai = x % m[i] ...: print(f"{x} = {ai} (mod {m[i]}), Valid congruence: {ai == a[i]}") ...: 39 = 0 (mod 3), Valid congruence: True 39 = 3 (mod 4), Valid congruence: True 39 = 4 (mod 5), Valid congruence: True
- galois.euler_totient(n)¶
Counts the positive integers (totatives) in \(1 \le k < n\) that are relatively prime to \(n\), i.e. \(\mathrm{gcd}(n, k) = 1\).
Implements the Euler Totient function \(\phi(n)\).
- Parameters
n (int) – A positive integer.
- Returns
The number of totatives that are relatively prime to \(n\).
- Return type
References
Examples
In [1]: n = 20 In [2]: phi = galois.euler_totient(n); phi Out[2]: 8 # Find the totatives that are coprime with n In [3]: totatives = [k for k in range(n) if math.gcd(k, n) == 1]; totatives Out[3]: [1, 3, 7, 9, 11, 13, 17, 19] # The number of totatives is phi In [4]: len(totatives) == phi Out[4]: True # For prime n, phi is always n-1 In [5]: galois.euler_totient(13) Out[5]: 12
- galois.gcd(a, b)¶
Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = \mathrm{gcd}(a, b)\).
This function implements the Extended Euclidean Algorithm.
- Parameters
- Returns
int – Greatest common divisor of \(a\) and \(b\).
int – Integer \(x\), such that \(a x + b y = \mathrm{gcd}(a, b)\).
int – Integer \(y\), such that \(a x + b y = \mathrm{gcd}(a, 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
Examples
In [1]: a = 2 In [2]: b = 13 In [3]: gcd, x, y = galois.gcd(a, b) In [4]: gcd, x, y Out[4]: (1, -6, 1) In [5]: a*x + b*y == gcd Out[5]: True
- galois.is_cyclic(n)¶
Determines whether the multiplicative group \(\mathbb{Z}{_n^\times}\) is cyclic.
The multiplicative group \(\mathbb{Z}{_n^\times}\) is the set of positive integers \(1 \le a < n\) that are coprime with \(n\). \(\mathbb{Z}{_n^\times}\) being cyclic means that some primitive root (or generator) \(g\) can generate the group \(\mathbb{Z}{_n^\times} = \{g, g^2, \dots, g^k\}\), where \(k\) is order of the group. The order of the group is defined by Euler’s totient function, \(\phi(n) = k\). If \(\mathbb{Z}{_n^\times}\) is cyclic, the number of primitive roots is found by \(\phi(k)\) or \(\phi(\phi(n))\).
\(\mathbb{Z}{_n^\times}\) is cyclic if and only if \(n\) is \(2\), \(4\), \(p^k\), or \(2p^k\), where \(p\) is an odd prime and \(k\) is a positive integer.
- Parameters
n (int) – A positive integer.
- Returns
True
if the multiplicative group \(\mathbb{Z}{_n^\times}\) is cyclic.- Return type
References
Examples
The elements of \(\mathbb{Z}{_n^\times}\) are the positive integers less than \(n\) that are coprime with \(n\). For example when \(n = 14\), then \(\mathbb{Z}{_{14}^\times} = \{1, 3, 5, 9, 11, 13\}\).
# n is of type 2*p^k, which is cyclic In [1]: n = 14 In [2]: galois.is_cyclic(n) Out[2]: True # The congruence class coprime with n In [3]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[3]: {1, 3, 5, 9, 11, 13} # Euler's totient function counts the "totatives", positive integers coprime with n In [4]: phi = galois.euler_totient(n); phi Out[4]: 6 In [5]: len(Znx) == phi Out[5]: True # The primitive roots are the elements in Znx that multiplicatively generate the group In [6]: for a in Znx: ...: span = set([pow(a, i, n) for i in range(1, phi + 1)]) ...: primitive_root = span == Znx ...: print("Element: {:2d}, Span: {:<20}, Primitive root: {}".format(a, str(span), primitive_root)) ...: Element: 1, Span: {1} , Primitive root: False Element: 3, Span: {1, 3, 5, 9, 11, 13}, Primitive root: True Element: 5, Span: {1, 3, 5, 9, 11, 13}, Primitive root: True Element: 9, Span: {9, 11, 1} , Primitive root: False Element: 11, Span: {9, 11, 1} , Primitive root: False Element: 13, Span: {1, 13} , Primitive root: False In [7]: roots = galois.primitive_roots(n); roots Out[7]: [3, 5] # Euler's totient function phi(phi(n)) counts the primitive roots of n In [8]: len(roots) == galois.euler_totient(phi) Out[8]: True
A counterexample is \(n = 15 = 3*5\), which doesn’t fit the condition for cyclicness. \(\mathbb{Z}{_{15}^\times} = \{1, 2, 4, 7, 8, 11, 13, 14\}\).
# n is of type p1^k1 * p2^k2, which is not cyclic In [9]: n = 15 In [10]: galois.is_cyclic(n) Out[10]: False # The congruence class coprime with n In [11]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[11]: {1, 2, 4, 7, 8, 11, 13, 14} # Euler's totient function counts the "totatives", positive integers coprime with n In [12]: phi = galois.euler_totient(n); phi Out[12]: 8 In [13]: len(Znx) == phi Out[13]: True # The primitive roots are the elements in Znx that multiplicatively generate the group In [14]: for a in Znx: ....: span = set([pow(a, i, n) for i in range(1, phi + 1)]) ....: primitive_root = span == Znx ....: print("Element: {:2d}, Span: {:<13}, Primitive root: {}".format(a, str(span), primitive_root)) ....: Element: 1, Span: {1} , Primitive root: False Element: 2, Span: {8, 1, 2, 4} , Primitive root: False Element: 4, Span: {1, 4} , Primitive root: False Element: 7, Span: {1, 4, 13, 7}, Primitive root: False Element: 8, Span: {8, 1, 2, 4} , Primitive root: False Element: 11, Span: {1, 11} , Primitive root: False Element: 13, Span: {1, 4, 13, 7}, Primitive root: False Element: 14, Span: {1, 14} , Primitive root: False In [15]: roots = galois.primitive_roots(n); roots Out[15]: [] # Note the max order of any element is 4, not 8, which is Carmichael's lambda function In [16]: galois.carmichael(n) Out[16]: 4
- galois.is_irreducible(poly)¶
Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is irreducible.
A polynomial \(f(x) \in \mathrm{GF}(p)[x]\) is reducible over \(\mathrm{GF}(p)\) if it can be represented as \(f(x) = g(x) h(x)\) for some \(g(x), h(x) \in \mathrm{GF}(p)[x]\) of strictly lower degree. If \(f(x)\) is not reducible, it is said to be irreducible. Since Galois fields are not algebraically closed, such irreducible polynomials exist.
This function implements Rabin’s irreducibility test. It says a degree-\(n\) polynomial \(f(x)\) over \(\mathrm{GF}(p)\) for prime \(p\) is irreducible if and only if \(f(x)\ |\ (x^{p^n} - x)\) and \(\textrm{gcd}(f(x),\ x^{p^{m_i}} - x) = 1\) for \(1 \le i \le k\), where \(m_i = n/p_i\) for the \(k\) prime divisors \(p_i\) of \(n\).
- Parameters
poly (galois.Poly) – A polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
- Returns
True
if the polynomial is irreducible.- Return type
References
Rabin. Probabilistic algorithms in finite fields. SIAM Journal on Computing (1980), 273–280. https://apps.dtic.mil/sti/pdfs/ADA078416.pdf
Gao and D. Panarino. Tests and constructions of irreducible polynomials over finite fields. https://www.math.clemson.edu/~sgao/papers/GP97a.pdf
https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields
Examples
# Conway polynomials are always irreducible (and primitive) In [1]: f = galois.conway_poly(2, 5); f Out[1]: Poly(x^5 + x^2 + 1, GF(2)) # f(x) has no roots in GF(2), a requirement of being irreducible In [2]: f.roots() Out[2]: GF([], order=2) In [3]: galois.is_irreducible(f) Out[3]: True
In [4]: g = galois.conway_poly(2, 4); g Out[4]: Poly(x^4 + x + 1, GF(2)) In [5]: h = galois.conway_poly(2, 5); h Out[5]: Poly(x^5 + x^2 + 1, GF(2)) In [6]: f = g * h; f Out[6]: Poly(x^9 + x^5 + x^4 + x^3 + x^2 + x + 1, GF(2)) # Even though f(x) has no roots in GF(2), it is still reducible In [7]: f.roots() Out[7]: GF([], order=2) In [8]: galois.is_irreducible(f) Out[8]: False
- galois.is_monic(poly)¶
Determines whether the polynomial is monic, i.e. having leading coefficient equal to 1.
- Parameters
poly (galois.Poly) – A polynomial over a Galois field.
- Returns
True
if the polynomial is monic.- Return type
Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([1,0,4,5], field=GF); p Out[2]: Poly(x^3 + 4x + 5, GF(7)) In [3]: galois.is_monic(p) Out[3]: True
In [4]: p = galois.Poly([3,0,4,5], field=GF); p Out[4]: Poly(3x^3 + 4x + 5, GF(7)) In [5]: galois.is_monic(p) Out[5]: False
- galois.is_prime(n)¶
Determines if \(n\) is prime.
This algorithm will first run Fermat’s primality test to check \(n\) for compositeness, see
galois.is_prime_fermat
. If it determines \(n\) is composite, the function will quickly return. If Fermat’s primality test returnsTrue
, then \(n\) could be prime or pseudoprime. If so, then the algorithm will run seven rounds of Miller-Rabin’s primality test, seegalois.is_prime_miller_rabin
. With this many rounds, a result ofTrue
should have high probability of \(n\) being a true prime, not a pseudoprime.- Parameters
n (int) – A positive integer.
- Returns
True
if the integer \(n\) is prime.- Return type
Examples
In [1]: galois.is_prime(13) Out[1]: True In [2]: galois.is_prime(15) Out[2]: False
The algorithm is also efficient on very large \(n\).
In [3]: galois.is_prime(1000000000000000035000061) Out[3]: True
- galois.is_prime_fermat(n)¶
Determines if \(n\) is composite.
This function implements Fermat’s primality test. The test says that for an integer \(n\), select an integer \(a\) coprime with \(n\). If \(a^{n-1} \equiv 1 (\textrm{mod}\ n)\), then \(n\) is prime or pseudoprime.
- Parameters
n (int) – A positive integer.
- Returns
False
if \(n\) is known to be composite.True
if \(n\) is prime or pseudoprime.- Return type
References
Examples
# List of some primes In [1]: primes = [257, 24841, 65497] In [2]: for prime in primes: ...: is_prime = galois.is_prime_fermat(prime) ...: p, k = galois.prime_factors(prime) ...: print("Prime = {:5d}, Fermat's Prime Test = {}, Prime factors = {}".format(prime, is_prime, list(p))) ...: Prime = 257, Fermat's Prime Test = True, Prime factors = [257] Prime = 24841, Fermat's Prime Test = True, Prime factors = [24841] Prime = 65497, Fermat's Prime Test = True, Prime factors = [65497] # List of some strong pseudoprimes with base 2 In [3]: pseudoprimes = [2047, 29341, 65281] In [4]: for pseudoprime in pseudoprimes: ...: is_prime = galois.is_prime_fermat(pseudoprime) ...: p, k = galois.prime_factors(pseudoprime) ...: print("Pseudoprime = {:5d}, Fermat's Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p))) ...: Pseudoprime = 2047, Fermat's Prime Test = True, Prime factors = [23, 89] Pseudoprime = 29341, Fermat's Prime Test = True, Prime factors = [13, 37, 61] Pseudoprime = 65281, Fermat's Prime Test = True, Prime factors = [97, 673]
- galois.is_prime_miller_rabin(n, a=None, rounds=1)¶
Determines if \(n\) is composite.
This function implements the Miller-Rabin primality test. The test says that for an integer \(n\), select an integer \(a\) such that \(a < n\). Factor \(n - 1\) such that \(2^s d = n - 1\). Then, \(n\) is composite, if \(a^d \not\equiv 1 (\textrm{mod}\ n)\) and \(a^{2^r d} \not\equiv n - 1 (\textrm{mod}\ n)\) for \(1 \le r < s\).
- Parameters
n (int) – A positive integer.
a (int, optional) – Initial composite witness value, \(1 \le a < n\). On subsequent rounds, \(a\) will be a different value. The default is a random value.
rounds (int, optional) – The number of iterations attempting to detect \(n\) as composite. Additional rounds will choose new \(a\). Sufficient rounds have arbitrarily-high probability of detecting a composite.
- Returns
False
if \(n\) is known to be composite.True
if \(n\) is prime or pseudoprime.- Return type
References
Examples
# List of some primes In [1]: primes = [257, 24841, 65497] In [2]: for prime in primes: ...: is_prime = galois.is_prime_miller_rabin(prime) ...: p, k = galois.prime_factors(prime) ...: print("Prime = {:5d}, Miller-Rabin Prime Test = {}, Prime factors = {}".format(prime, is_prime, list(p))) ...: Prime = 257, Miller-Rabin Prime Test = True, Prime factors = [257] Prime = 24841, Miller-Rabin Prime Test = True, Prime factors = [24841] Prime = 65497, Miller-Rabin Prime Test = True, Prime factors = [65497] # List of some strong pseudoprimes with base 2 In [3]: pseudoprimes = [2047, 29341, 65281] # Single round of Miller-Rabin, sometimes fooled by pseudoprimes In [4]: for pseudoprime in pseudoprimes: ...: is_prime = galois.is_prime_miller_rabin(pseudoprime) ...: p, k = galois.prime_factors(pseudoprime) ...: print("Pseudoprime = {:5d}, Miller-Rabin Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p))) ...: Pseudoprime = 2047, Miller-Rabin Prime Test = False, Prime factors = [23, 89] Pseudoprime = 29341, Miller-Rabin Prime Test = False, Prime factors = [13, 37, 61] Pseudoprime = 65281, Miller-Rabin Prime Test = False, Prime factors = [97, 673] # 7 rounds of Miller-Rabin, never fooled by pseudoprimes In [5]: for pseudoprime in pseudoprimes: ...: is_prime = galois.is_prime_miller_rabin(pseudoprime, rounds=7) ...: p, k = galois.prime_factors(pseudoprime) ...: print("Pseudoprime = {:5d}, Miller-Rabin Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p))) ...: Pseudoprime = 2047, Miller-Rabin Prime Test = False, Prime factors = [23, 89] Pseudoprime = 29341, Miller-Rabin Prime Test = False, Prime factors = [13, 37, 61] Pseudoprime = 65281, Miller-Rabin Prime Test = False, Prime factors = [97, 673]
- galois.is_primitive(poly)¶
Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is primitive.
A degree-\(n\) polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is primitive if \(f(x)\ |\ (x^k - 1)\) for \(k = p^n - 1\) and no \(k\) less than \(p^n - 1\).
- Parameters
poly (galois.Poly) – A polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
- Returns
True
if the polynomial is primitive.- Return type
References
Algorithm 4.77 from https://cacr.uwaterloo.ca/hac/about/chap4.pdf
Examples
All Conway polynomials are primitive.
In [1]: f = galois.conway_poly(2, 8); f Out[1]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2)) In [2]: galois.is_primitive(f) Out[2]: True In [3]: f = galois.conway_poly(3, 5); f Out[3]: Poly(x^5 + 2x + 1, GF(3)) In [4]: galois.is_primitive(f) Out[4]: True
The irreducible polynomial of \(\mathrm{GF}(2^8)\) for AES is not primitive.
In [5]: f = galois.Poly.Degrees([8,4,3,1,0]); f Out[5]: Poly(x^8 + x^4 + x^3 + x + 1, GF(2)) In [6]: galois.is_primitive(f) Out[6]: False
- galois.is_primitive_element(element, irreducible_poly)¶
Determines if \(g(x)\) is a primitive element of the Galois field \(\mathrm{GF}(p^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
The number of primitive elements of \(\mathrm{GF}(p^m)\) is \(\phi(p^m - 1)\), where \(\phi(n)\) is the Euler totient function, see
galois.euler_totient
.- Parameters
element (galois.Poly) – An element \(g(x)\) of \(\mathrm{GF}(p^m)\) as a polynomial over \(\mathrm{GF}(p)\) with degree less than \(m\).
irreducible_poly (galois.Poly) – The degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\) that defines the extension field \(\mathrm{GF}(p^m)\).
- Returns
True
if \(g(x)\) is a primitive element of \(\mathrm{GF}(p^m)\) with irreducible polynomial \(f(x)\).- Return type
Examples
In [1]: GF = galois.GF(3) In [2]: f = galois.Poly([1,1,2], field=GF); f Out[2]: Poly(x^2 + x + 2, GF(3)) In [3]: galois.is_irreducible(f) Out[3]: True In [4]: galois.is_primitive(f) Out[4]: True In [5]: g = galois.Poly.Identity(GF); g Out[5]: Poly(x, GF(3)) In [6]: galois.is_primitive_element(g, f) Out[6]: True
In [7]: GF = galois.GF(3) In [8]: f = galois.Poly([1,0,1], field=GF); f Out[8]: Poly(x^2 + 1, GF(3)) In [9]: galois.is_irreducible(f) Out[9]: True In [10]: galois.is_primitive(f) Out[10]: False In [11]: g = galois.Poly.Identity(GF); g Out[11]: Poly(x, GF(3)) In [12]: galois.is_primitive_element(g, f) Out[12]: False
- galois.is_primitive_root(g, n)¶
Determines if \(g\) is a primitive root modulo \(n\).
\(g\) is a primitive root if the totatives of \(n\), the positive integers \(1 \le a < n\) that are coprime with \(n\), can be generated by powers of \(g\).
- Parameters
- Returns
True
if \(g\) is a primitive root modulo \(n\).- Return type
Examples
In [1]: galois.is_primitive_root(2, 7) Out[1]: False In [2]: galois.is_primitive_root(3, 7) Out[2]: True In [3]: galois.primitive_roots(7) Out[3]: [3, 5]
- galois.is_smooth(n, B)¶
Determines if the positive integer \(n\) is \(B\)-smooth, i.e. all its prime factors satisfy \(p \le B\).
The \(2\)-smooth numbers are the powers of \(2\). The \(5\)-smooth numbers are known as regular numbers. The \(7\)-smooth numbers are known as humble numbers or highly composite numbers.
- Parameters
- Returns
True
if \(n\) is \(B\)-smooth.- Return type
Examples
In [1]: galois.is_smooth(2**10, 2) Out[1]: True In [2]: galois.is_smooth(10, 5) Out[2]: True In [3]: galois.is_smooth(12, 5) Out[3]: True In [4]: galois.is_smooth(60**2, 5) Out[4]: True
- galois.isqrt(n)¶
Computes the integer square root of \(n\) such that \(\textrm{isqrt}(n)^2 \le n\).
Note
This function is included for Python versions before 3.8. For Python 3.8 and later, this function calls
math.isqrt()
from the standard library.- Parameters
n (int) – A non-negative integer.
- Returns
The integer square root of \(n\) such that \(\textrm{isqrt}(n)^2 \le n\).
- Return type
Examples
# Use a large Mersenne prime In [1]: p = galois.mersenne_primes(2000)[-1]; p Out[1]: 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087 In [2]: sqrt_p = galois.isqrt(p); sqrt_p Out[2]: 3226132699481594337650229932669505772017441235628244885631123722785761803162998767122846394796285964908262519578341713326387400858087872534573955058079614218029097609909460991319304989482693499 In [3]: sqrt_p**2 <= p Out[3]: True In [4]: (sqrt_p + 1)**2 <= p Out[4]: False
- galois.kth_prime(k)¶
Returns the \(k\)-th prime.
- Parameters
k (int) – The prime index, where \(k = \{1,2,3,4,\dots\}\) for primes \(p = \{2,3,5,7,\dots\}\).
- Returns
The \(k\)-th prime.
- Return type
Examples
In [1]: galois.kth_prime(1) Out[1]: 2 In [2]: galois.kth_prime(3) Out[2]: 5 In [3]: galois.kth_prime(1000) Out[3]: 7919
- galois.lcm(*integers)¶
Computes the least common multiple of the integer arguments.
Note
This function is included for Python versions before 3.9. For Python 3.9 and later, this function calls
math.lcm()
from the standard library.- Returns
The least common multiple of the integer arguments. If any argument is 0, the LCM is 0. If no arguments are provided, 1 is returned.
- Return type
Examples
In [1]: galois.lcm() Out[1]: 1 In [2]: galois.lcm(2, 4, 14) Out[2]: 28 In [3]: galois.lcm(3, 0, 9) Out[3]: 0
This function also works on arbitrarily-large integers.
In [4]: prime1, prime2 = galois.mersenne_primes(100)[-2:] In [5]: prime1, prime2 Out[5]: (2305843009213693951, 618970019642690137449562111) In [6]: lcm = galois.lcm(prime1, prime2); lcm Out[6]: 1427247692705959880439315947500961989719490561 In [7]: lcm == prime1 * prime2 Out[7]: True
- galois.log_naive(beta, alpha, modulus)¶
Computes the discrete logarithm \(x = \textrm{log}_{\alpha}(\beta)\ (\textrm{mod}\ m)\).
This function implements the naive algorithm. It is included for testing and reference.
- Parameters
Examples
In [1]: N = 17 In [2]: galois.totatives(N) Out[2]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] In [3]: galois.primitive_roots(N) Out[3]: [3, 5, 6, 7, 10, 11, 12, 14] In [4]: x = galois.log_naive(3, 7, N); x Out[4]: 3 In [5]: 7**x % N Out[5]: 3
In [6]: N = 18 In [7]: galois.totatives(N) Out[7]: [1, 5, 7, 11, 13, 17] In [8]: galois.primitive_roots(N) Out[8]: [5, 11] In [9]: x = galois.log_naive(11, 5, N); x Out[9]: 5 In [10]: 5**x % N Out[10]: 11
- galois.mersenne_exponents(n=None)¶
Returns all known Mersenne exponents \(e\) for \(e \le n\).
A Mersenne exponent \(e\) is an exponent of \(2\) such that \(2^e - 1\) is prime.
- Parameters
n (int, optional) – The max exponent of 2. The default is
None
which returns all known Mersenne exponents.- Returns
The list of Mersenne exponents \(e\) for \(e \le n\).
- Return type
References
Examples
# List all Mersenne exponents for Mersenne primes up to 2000 bits In [1]: e = galois.mersenne_exponents(2000); e Out[1]: [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279] # Select one Merseene exponent and compute its Mersenne prime In [2]: p = 2**e[-1] - 1; p Out[2]: 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087 In [3]: galois.is_prime(p) Out[3]: True
- galois.mersenne_primes(n=None)¶
Returns all known Mersenne primes \(p\) for \(p \le 2^n - 1\).
Mersenne primes are primes that are one less than a power of 2.
- Parameters
n (int, optional) – The max power of 2. The default is
None
which returns all known Mersenne exponents.- Returns
The list of known Mersenne primes \(p\) for \(p \le 2^n - 1\).
- Return type
References
Examples
# List all Mersenne primes up to 2000 bits In [1]: p = galois.mersenne_primes(2000); p Out[1]: [3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727, 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151, 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127, 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087] In [2]: galois.is_prime(p[-1]) Out[2]: True
- galois.next_prime(n)¶
Returns the nearest prime \(p\), such that \(p > n\).
Examples
In [1]: galois.next_prime(13) Out[1]: 17 In [2]: galois.next_prime(15) Out[2]: 17
- galois.poly_gcd(a, b)¶
Finds the greatest common divisor of two polynomials \(a(x)\) and \(b(x)\) over \(\mathrm{GF}(q)\).
This implementation uses the Extended Euclidean Algorithm.
- Parameters
a (galois.Poly) – A polynomial \(a(x)\) over \(\mathrm{GF}(q)\).
b (galois.Poly) – A polynomial \(b(x)\) over \(\mathrm{GF}(q)\).
- Returns
galois.Poly – Polynomial greatest common divisor of \(a(x)\) and \(b(x)\).
galois.Poly – Polynomial \(x(x)\), such that \(a x + b y = gcd(a, b)\).
galois.Poly – Polynomial \(y(x)\), such that \(a x + b y = gcd(a, b)\).
Examples
In [1]: GF = galois.GF(7) In [2]: a = galois.Poly.Roots([2,2,2,3,6], field=GF); a Out[2]: Poly(x^5 + 6x^4 + x + 3, GF(7)) # a(x) and b(x) only share the root 2 in common In [3]: b = galois.Poly.Roots([1,2], field=GF); b Out[3]: Poly(x^2 + 4x + 2, GF(7)) In [4]: gcd, x, y = galois.poly_gcd(a, b) # The GCD has only 2 as a root with multiplicity 1 In [5]: gcd.roots(multiplicity=True) Out[5]: (GF([2], order=7), array([1])) In [6]: a*x + b*y == gcd Out[6]: True
- galois.poly_pow(poly, power, modulus)¶
Efficiently exponentiates a polynomial \(f(x)\) to the power \(k\) reducing by modulo \(g(x)\), \(f(x)^k\ \textrm{mod}\ g(x)\).
The algorithm is more efficient than exponentiating first and then reducing modulo \(g(x)\). Instead, this algorithm repeatedly squares \(f(x)\), reducing modulo \(g(x)\) at each step. This is the polynomial equivalent of
galois.pow()
.- Parameters
poly (galois.Poly) – The polynomial to be exponentiated \(f(x)\).
power (int) – The non-negative exponent \(k\).
modulus (galois.Poly) – The reducing polynomial \(g(x)\).
- Returns
The resulting polynomial \(h(x) = f^k\ \textrm{mod}\ g\).
- Return type
Examples
In [1]: GF = galois.GF(31) In [2]: f = galois.Poly.Random(10, field=GF); f Out[2]: Poly(24x^10 + 29x^9 + 19x^8 + 15x^7 + 10x^6 + 3x^5 + 12x^4 + 18x^3 + 6x^2 + 9x + 26, GF(31)) In [3]: g = galois.Poly.Random(7, field=GF); g Out[3]: Poly(28x^7 + 18x^6 + 18x^5 + 16x^4 + 17x^3 + 20x^2 + 22x + 3, GF(31)) # %timeit f**200 % g # 1.23 s ± 41.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) In [4]: f**200 % g Out[4]: Poly(19x^6 + 17x^5 + 17x^4 + 11x^3 + 17x^2 + 2x + 2, GF(31)) # %timeit galois.poly_pow(f, 200, g) # 41.7 ms ± 468 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) In [5]: galois.poly_pow(f, 200, g) Out[5]: Poly(19x^6 + 17x^5 + 17x^4 + 11x^3 + 17x^2 + 2x + 2, GF(31))
- galois.pow(base, exp, mod)¶
Efficiently exponentiates an integer \(a^k (\textrm{mod}\ m)\).
The algorithm is more efficient than exponentiating first and then reducing modulo \(m\). This is the integer equivalent of
galois.poly_pow()
.Note
This function is an alias of
pow()
in the standard library.- Parameters
- Returns
The modular exponentiation \(a^k (\textrm{mod}\ m)\).
- Return type
Examples
In [1]: galois.pow(3, 5, 7) Out[1]: 5 In [2]: (3**5) % 7 Out[2]: 5
- galois.prev_prime(n)¶
Returns the nearest prime \(p\), such that \(p \le n\).
Examples
In [1]: galois.prev_prime(13) Out[1]: 13 In [2]: galois.prev_prime(15) Out[2]: 13
- galois.prime_factors(n)¶
Computes the prime factors of the positive integer \(n\).
The integer \(n\) can be factored into \(n = p_1^{e_1} p_2^{e_2} \dots p_{k-1}^{e_{k-1}}\).
Steps:
Test if \(n\) is prime. If so, return
[n], [1]
.Use trial division with a list of primes up to \(10^6\). If no residual factors, return the discovered prime factors.
Use Pollard’s Rho algorithm to find a non-trivial factor of the residual. Continue until all are found.
- Parameters
n (int) – The positive integer to be factored.
- Returns
list – Sorted list of \(k\) prime factors \(p = [p_1, p_2, \dots, p_{k-1}]\) with \(p_1 < p_2 < \dots < p_{k-1}\).
list – List of corresponding prime powers \(e = [e_1, e_2, \dots, e_{k-1}]\).
Examples
In [1]: p, e = galois.prime_factors(120) In [2]: p, e Out[2]: ([2, 3, 5], [3, 1, 1]) # The product of the prime powers is the factored integer In [3]: np.multiply.reduce(np.array(p) ** np.array(e)) Out[3]: 120
Prime factorization of 1 less than a large prime.
In [4]: prime =1000000000000000035000061 In [5]: galois.is_prime(prime) Out[5]: True In [6]: p, e = galois.prime_factors(prime - 1) In [7]: p, e Out[7]: ([2, 3, 5, 17, 19, 112850813, 457237177399], [2, 1, 1, 1, 1, 1, 1]) In [8]: np.multiply.reduce(np.array(p) ** np.array(e)) Out[8]: 2003764205241896700
- galois.primes(n)¶
Returns all primes \(p\) for \(p \le n\).
- Parameters
n (int) – A positive integer.
- Returns
The primes up to and including \(n\).
- Return type
References
Examples
In [1]: galois.primes(19) Out[1]: [2, 3, 5, 7, 11, 13, 17, 19]
- galois.primitive_element(irreducible_poly, start=None, stop=None, reverse=False)¶
Finds the smallest primitive element \(g(x)\) of the Galois field \(\mathrm{GF}(p^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
- Parameters
irreducible_poly (galois.Poly) – The degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\) that defines the extension field \(\mathrm{GF}(p^m)\).
start (int, optional) – Starting value (inclusive, integer representation of the polynomial) in the search for a primitive element \(g(x)\) of \(\mathrm{GF}(p^m)\). The default is
None
which represents \(p\), which corresponds to \(g(x) = x\) over \(\mathrm{GF}(p)\).stop (int, optional) – Stopping value (exclusive, integer representation of the polynomial) in the search for a primitive element \(g(x)\) of \(\mathrm{GF}(p^m)\). The default is
None
which represents \(p^m\), which corresponds to \(g(x) = x^m\) over \(\mathrm{GF}(p)\).reverse (bool, optional) – Search for a primitive element in reverse order, i.e. find the largest primitive element first. Default is
False
.
- Returns
A primitive element of \(\mathrm{GF}(p^m)\) with irreducible polynomial \(f(x)\). The primitive element \(g(x)\) is a polynomial over \(\mathrm{GF}(p)\) with degree less than \(m\).
- Return type
Examples
In [1]: GF = galois.GF(3) In [2]: f = galois.Poly([1,1,2], field=GF); f Out[2]: Poly(x^2 + x + 2, GF(3)) In [3]: galois.is_irreducible(f) Out[3]: True In [4]: galois.is_primitive(f) Out[4]: True In [5]: galois.primitive_element(f) Out[5]: Poly(x, GF(3))
In [6]: GF = galois.GF(3) In [7]: f = galois.Poly([1,0,1], field=GF); f Out[7]: Poly(x^2 + 1, GF(3)) In [8]: galois.is_irreducible(f) Out[8]: True In [9]: galois.is_primitive(f) Out[9]: False In [10]: galois.primitive_element(f) Out[10]: Poly(x + 1, GF(3))
- galois.primitive_elements(irreducible_poly, start=None, stop=None, reverse=False)¶
Finds all primitive elements \(g(x)\) of the Galois field \(\mathrm{GF}(p^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
The number of primitive elements of \(\mathrm{GF}(p^m)\) is \(\phi(p^m - 1)\), where \(\phi(n)\) is the Euler totient function. See :obj:galois.euler_totient`.
- Parameters
irreducible_poly (galois.Poly) – The degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\) that defines the extension field \(\mathrm{GF}(p^m)\).
start (int, optional) – Starting value (inclusive, integer representation of the polynomial) in the search for primitive elements \(g(x)\) of \(\mathrm{GF}(p^m)\). The default is
None
which represents \(p\), which corresponds to \(g(x) = x\) over \(\mathrm{GF}(p)\).stop (int, optional) – Stopping value (exclusive, integer representation of the polynomial) in the search for primitive elements \(g(x)\) of \(\mathrm{GF}(p^m)\). The default is
None
which represents \(p^m\), which corresponds to \(g(x) = x^m\) over \(\mathrm{GF}(p)\).reverse (bool, optional) – Search for primitive elements in reverse order, i.e. largest to smallest. Default is
False
.
- Returns
List of all primitive elements of \(\mathrm{GF}(p^m)\) with irreducible polynomial \(f(x)\). Each primitive element \(g(x)\) is a polynomial over \(\mathrm{GF}(p)\) with degree less than \(m\).
- Return type
Examples
In [1]: GF = galois.GF(3) In [2]: f = galois.Poly([1,1,2], field=GF); f Out[2]: Poly(x^2 + x + 2, GF(3)) In [3]: galois.is_irreducible(f) Out[3]: True In [4]: galois.is_primitive(f) Out[4]: True In [5]: g = galois.primitive_elements(f); g Out[5]: [Poly(x, GF(3)), Poly(x + 1, GF(3)), Poly(2x, GF(3)), Poly(2x + 2, GF(3))] In [6]: len(g) == galois.euler_totient(3**2 - 1) Out[6]: True
In [7]: GF = galois.GF(3) In [8]: f = galois.Poly([1,0,1], field=GF); f Out[8]: Poly(x^2 + 1, GF(3)) In [9]: galois.is_irreducible(f) Out[9]: True In [10]: galois.is_primitive(f) Out[10]: False In [11]: g = galois.primitive_elements(f); g Out[11]: [Poly(x + 1, GF(3)), Poly(x + 2, GF(3)), Poly(2x + 1, GF(3)), Poly(2x + 2, GF(3))] In [12]: len(g) == galois.euler_totient(3**2 - 1) Out[12]: True
- galois.primitive_root(n, start=1, stop=None, reverse=False)¶
Finds the smallest primitive root modulo \(n\).
\(g\) is a primitive root if the totatives of \(n\), the positive integers \(1 \le a < n\) that are coprime with \(n\), can be generated by powers of \(g\).
Alternatively said, \(g\) is a primitive root modulo \(n\) if and only if \(g\) is a generator of the multiplicative group of integers modulo \(n\), \(\mathbb{Z}{_n^\times}\). That is, \(\mathbb{Z}{_n^\times} = \{g, g^2, \dots, g^k\}\), where \(k\) is order of the group. The order of the group \(\mathbb{Z}{_n^\times}\) is defined by Euler’s totient function, \(\phi(n) = k\). If \(\mathbb{Z}{_n^\times}\) is cyclic, the number of primitive roots modulo \(n\) is given by \(\phi(k)\) or \(\phi(\phi(n))\).
See
galois.is_cyclic
.- Parameters
n (int) – A positive integer.
start (int, optional) – Starting value (inclusive) in the search for a primitive root. The default is
1
. The resulting primitive root, if found, will be \(\textrm{start} \le g < \textrm{stop}\).stop (int, optional) – Stopping value (exclusive) in the search for a primitive root. The default is
None
which corresponds ton
. The resulting primitive root, if found, will be \(\textrm{start} \le g < \textrm{stop}\).reverse (bool, optional) – Search for a primitive root in reverse order, i.e. find the largest primitive root first. Default is
False
.
- Returns
The smallest primitive root modulo \(n\). Returns
None
if no primitive roots exist.- Return type
References
Shoup. Searching for primitive roots in finite fields. https://www.ams.org/journals/mcom/1992-58-197/S0025-5718-1992-1106981-9/S0025-5718-1992-1106981-9.pdf
Hua. On the least primitive root of a prime. https://www.ams.org/journals/bull/1942-48-10/S0002-9904-1942-07767-6/S0002-9904-1942-07767-6.pdf
http://www.numbertheory.org/courses/MP313/lectures/lecture7/page1.html
Examples
Here is an example with one primitive root, \(n = 6 = 2 * 3^1\), which fits the definition of cyclicness, see
galois.is_cyclic
. Because \(n = 6\) is not prime, the primitive root isn’t a multiplicative generator of \(\mathbb{Z}/\textbf{n}\mathbb{Z}\).In [1]: n = 6 In [2]: root = galois.primitive_root(n); root Out[2]: 5 # The congruence class coprime with n In [3]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[3]: {1, 5} # Euler's totient function counts the "totatives", positive integers coprime with n In [4]: phi = galois.euler_totient(n); phi Out[4]: 2 In [5]: len(Znx) == phi Out[5]: True # The primitive roots are the elements in Znx that multiplicatively generate the group In [6]: for a in Znx: ...: span = set([pow(a, i, n) for i in range(1, phi + 1)]) ...: primitive_root = span == Znx ...: print("Element: {}, Span: {:<6}, Primitive root: {}".format(a, str(span), primitive_root)) ...: Element: 1, Span: {1} , Primitive root: False Element: 5, Span: {1, 5}, Primitive root: True
Here is an example with two primitive roots, \(n = 7 = 7^1\), which fits the definition of cyclicness, see
galois.is_cyclic
. Since \(n = 7\) is prime, the primitive root is a multiplicative generator of \(\mathbb{Z}/\textbf{n}\mathbb{Z}\).In [7]: n = 7 In [8]: root = galois.primitive_root(n); root Out[8]: 3 # The congruence class coprime with n In [9]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[9]: {1, 2, 3, 4, 5, 6} # Euler's totient function counts the "totatives", positive integers coprime with n In [10]: phi = galois.euler_totient(n); phi Out[10]: 6 In [11]: len(Znx) == phi Out[11]: True # The primitive roots are the elements in Znx that multiplicatively generate the group In [12]: for a in Znx: ....: span = set([pow(a, i, n) for i in range(1, phi + 1)]) ....: primitive_root = span == Znx ....: print("Element: {}, Span: {:<18}, Primitive root: {}".format(a, str(span), primitive_root)) ....: Element: 1, Span: {1} , Primitive root: False Element: 2, Span: {1, 2, 4} , Primitive root: False Element: 3, Span: {1, 2, 3, 4, 5, 6}, Primitive root: True Element: 4, Span: {1, 2, 4} , Primitive root: False Element: 5, Span: {1, 2, 3, 4, 5, 6}, Primitive root: True Element: 6, Span: {1, 6} , Primitive root: False
The algorithm is also efficient for very large \(n\).
In [13]: n = 1000000000000000035000061 In [14]: galois.primitive_root(n) Out[14]: 7 In [15]: galois.primitive_root(n, reverse=True) Out[15]: 1000000000000000035000054
Here is a counterexample with no primitive roots, \(n = 8 = 2^3\), which does not fit the definition of cyclicness, see
galois.is_cyclic
.In [16]: n = 8 In [17]: root = galois.primitive_root(n); root # The congruence class coprime with n In [18]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[18]: {1, 3, 5, 7} # Euler's totient function counts the "totatives", positive integers coprime with n In [19]: phi = galois.euler_totient(n); phi Out[19]: 4 In [20]: len(Znx) == phi Out[20]: True # Test all elements for being primitive roots. The powers of a primitive span the congruence classes mod n. In [21]: for a in Znx: ....: span = set([pow(a, i, n) for i in range(1, phi + 1)]) ....: primitive_root = span == Znx ....: print("Element: {}, Span: {:<6}, Primitive root: {}".format(a, str(span), primitive_root)) ....: Element: 1, Span: {1} , Primitive root: False Element: 3, Span: {1, 3}, Primitive root: False Element: 5, Span: {1, 5}, Primitive root: False Element: 7, Span: {1, 7}, Primitive root: False # Note the max order of any element is 2, not 4, which is Carmichael's lambda function In [22]: galois.carmichael(n) Out[22]: 2
- galois.primitive_roots(n, start=1, stop=None, reverse=False)¶
Finds all primitive roots modulo \(n\).
\(g\) is a primitive root if the totatives of \(n\), the positive integers \(1 \le a < n\) that are coprime with \(n\), can be generated by powers of \(g\).
Alternatively said, \(g\) is a primitive root modulo \(n\) if and only if \(g\) is a generator of the multiplicative group of integers modulo \(n\), \(\mathbb{Z}{_n^\times}\). That is, \(\mathbb{Z}{_n^\times} = \{g, g^2, \dots, g^k\}\), where \(k\) is order of the group. The order of the group \(\mathbb{Z}{_n^\times}\) is defined by Euler’s totient function, \(\phi(n) = k\). If \(\mathbb{Z}{_n^\times}\) is cyclic, the number of primitive roots modulo \(n\) is given by \(\phi(k)\) or \(\phi(\phi(n))\).
See
galois.is_cyclic
.- Parameters
n (int) – A positive integer.
start (int, optional) – Starting value (inclusive) in the search for a primitive root. The default is 1. The resulting primitive roots, if found, will be \(\textrm{start} \le x < \textrm{stop}\).
stop (int, optional) – Stopping value (exclusive) in the search for a primitive root. The default is
None
which corresponds ton
. The resulting primitive roots, if found, will be \(\textrm{start} \le x < \textrm{stop}\).reverse (bool, optional) – List all primitive roots in descending order, i.e. largest to smallest. Default is
False
.
- Returns
All the positive primitive \(n\)-th roots of unity, \(x\).
- Return type
References
Shoup. Searching for primitive roots in finite fields. https://www.ams.org/journals/mcom/1992-58-197/S0025-5718-1992-1106981-9/S0025-5718-1992-1106981-9.pdf
http://www.numbertheory.org/courses/MP313/lectures/lecture7/page1.html
Examples
Here is an example with one primitive root, \(n = 6 = 2 * 3^1\), which fits the definition of cyclicness, see
galois.is_cyclic
. Because \(n = 6\) is not prime, the primitive root isn’t a multiplicative generator of \(\mathbb{Z}/\textbf{n}\mathbb{Z}\).In [1]: n = 6 In [2]: roots = galois.primitive_roots(n); roots Out[2]: [5] # The congruence class coprime with n In [3]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[3]: {1, 5} # Euler's totient function counts the "totatives", positive integers coprime with n In [4]: phi = galois.euler_totient(n); phi Out[4]: 2 In [5]: len(Znx) == phi Out[5]: True # Test all elements for being primitive roots. The powers of a primitive span the congruence classes mod n. In [6]: for a in Znx: ...: span = set([pow(a, i, n) for i in range(1, phi + 1)]) ...: primitive_root = span == Znx ...: print("Element: {}, Span: {:<6}, Primitive root: {}".format(a, str(span), primitive_root)) ...: Element: 1, Span: {1} , Primitive root: False Element: 5, Span: {1, 5}, Primitive root: True # Euler's totient function phi(phi(n)) counts the primitive roots of n In [7]: len(roots) == galois.euler_totient(phi) Out[7]: True
Here is an example with two primitive roots, \(n = 7 = 7^1\), which fits the definition of cyclicness, see
galois.is_cyclic
. Since \(n = 7\) is prime, the primitive root is a multiplicative generator of \(\mathbb{Z}/\textbf{n}\mathbb{Z}\).In [8]: n = 7 In [9]: roots = galois.primitive_roots(n); roots Out[9]: [3, 5] # The congruence class coprime with n In [10]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[10]: {1, 2, 3, 4, 5, 6} # Euler's totient function counts the "totatives", positive integers coprime with n In [11]: phi = galois.euler_totient(n); phi Out[11]: 6 In [12]: len(Znx) == phi Out[12]: True # Test all elements for being primitive roots. The powers of a primitive span the congruence classes mod n. In [13]: for a in Znx: ....: span = set([pow(a, i, n) for i in range(1, phi + 1)]) ....: primitive_root = span == Znx ....: print("Element: {}, Span: {:<18}, Primitive root: {}".format(a, str(span), primitive_root)) ....: Element: 1, Span: {1} , Primitive root: False Element: 2, Span: {1, 2, 4} , Primitive root: False Element: 3, Span: {1, 2, 3, 4, 5, 6}, Primitive root: True Element: 4, Span: {1, 2, 4} , Primitive root: False Element: 5, Span: {1, 2, 3, 4, 5, 6}, Primitive root: True Element: 6, Span: {1, 6} , Primitive root: False # Euler's totient function phi(phi(n)) counts the primitive roots of n In [14]: len(roots) == galois.euler_totient(phi) Out[14]: True
The algorithm is also efficient for very large \(n\).
In [15]: n = 1000000000000000035000061 # Euler's totient function phi(phi(n)) counts the primitive roots of n In [16]: galois.euler_totient(galois.euler_totient(n)) Out[16]: 237770895725348415787008 # Only find some of the primitive roots In [17]: galois.primitive_roots(n, stop=100) Out[17]: [7, 21, 28, 34, 35, 38, 39, 43, 47, 52, 58, 65, 67, 73, 88, 97, 98] # The generator can also be used in a for loop In [18]: for r in galois.primitive_roots(n, stop=100): ....: print(r, end=" ") ....: 7 21 28 34 35 38 39 43 47 52 58 65 67 73 88 97 98
Here is a counterexample with no primitive roots, \(n = 8 = 2^3\), which does not fit the definition of cyclicness, see
galois.is_cyclic
.In [19]: n = 8 In [20]: roots = galois.primitive_roots(n); roots Out[20]: [] # The congruence class coprime with n In [21]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[21]: {1, 3, 5, 7} # Euler's totient function counts the "totatives", positive integers coprime with n In [22]: phi = galois.euler_totient(n); phi Out[22]: 4 In [23]: len(Znx) == phi Out[23]: True # Test all elements for being primitive roots. The powers of a primitive span the congruence classes mod n. In [24]: for a in Znx: ....: span = set([pow(a, i, n) for i in range(1, phi + 1)]) ....: primitive_root = span == Znx ....: print("Element: {}, Span: {:<6}, Primitive root: {}".format(a, str(span), primitive_root)) ....: Element: 1, Span: {1} , Primitive root: False Element: 3, Span: {1, 3}, Primitive root: False Element: 5, Span: {1, 5}, Primitive root: False Element: 7, Span: {1, 7}, Primitive root: False
- galois.random_prime(bits)¶
Returns a random prime \(p\) with \(b\) bits, such that \(2^b \le p < 2^{b+1}\).
This function randomly generates integers with \(b\) bits and uses the primality tests in
galois.is_prime()
to determine if \(p\) is prime.- Parameters
bits (int) – The number of bits in the prime \(p\).
- Returns
A random prime in \(2^b \le p < 2^{b+1}\).
- Return type
References
Examples
Generate a random 1024-bit prime.
In [1]: p = galois.random_prime(1024); p Out[1]: 299544611607612739850260280020231686141958509918255151137813027672722169937189332954582785840734217402688632153308258410070998693697599208750028049858662720919136915937750621279887191247085325690323793035868416254143553219944544037819312123164905009038950225302716582702433491938247979286277751953010675748429 In [2]: galois.is_prime(p) Out[2]: True
$ openssl prime 236861787926957382206996886087214592029752524078026392358936844479667423570833116126506927878773110287700754280996224768092589904231910149528080012692722763539766058401127758399272786475279348968866620857161889678512852050561604969208679095086283103827661300743342847921567132587459205365243815835763830067933 1514D68EDB7C650F1FF713531A1A43255A4BE6D66EE1FDBD96F4EB32757C1B1BAF16A5933E24D45FAD6C6A814F3C8C14F3CB98F24FEA74C43C349D6FA3AB76EB0156811A1FBAA64EB4AC525CCEF9278AF78886DC6DBF46C4463A34C0E53B0FA2F784BB2DC5FDF076BB6E145AA15AA6D616ACC1D5F95B8BE757670B9AAF53292DD (236861787926957382206996886087214592029752524078026392358936844479667423570833116126506927878773110287700754280996224768092589904231910149528080012692722763539766058401127758399272786475279348968866620857161889678512852050561604969208679095086283103827661300743342847921567132587459205365243815835763830067933) is prime
- galois.totatives(n)¶
Returns the positive integers (totatives) in \(1 \le k < n\) that are coprime with \(n\), i.e. \(\mathrm{gcd}(n, k) = 1\).
The totatives of \(n\) form the multiplicative group \(\mathbb{Z}{_n^\times}\).
References
Examples
In [1]: n = 20 In [2]: totatives = galois.totatives(n); totatives Out[2]: [1, 3, 7, 9, 11, 13, 17, 19] In [3]: phi = galois.euler_totient(n); phi Out[3]: 8 In [4]: len(totatives) == phi Out[4]: True