galois¶
A performant numpy extension for Galois fields.
Classes
|
An abstract base class for all Galois field array classes. |
|
Galois field array class for \(\mathrm{GF}(2)\) fields. |
|
An abstract base class for all \(\mathrm{GF}(2^m)\) field array classes. |
|
An abstract base class for all \(\mathrm{GF}(p)\) field array classes. |
|
A polynomial class with coefficients in any Galois field. |
Class Factory Functions
|
Factory function to construct Galois field array classes of type \(\mathrm{GF}(p^m)\). |
Functions
|
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\). |
Solves the simultaneous system of congruences for \(x\). |
|
|
Returns the Conway polynomial for \(\mathrm{GF}(p^m)\). |
|
Finds the greatest common divisor of two integers. |
Counts the positive integers (totatives) in \(1 \le k < n\) that are relatively prime to \(n\), i.e. \(gcd(n, k) = 1\). |
|
Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = gcd(a,b)\). |
|
|
Computes the positive factors of the integer \(x\). |
Probabilistic primality test of \(n\). |
|
|
Determines if \(n\) is prime. |
|
Probabilistic primality test of \(n\). |
|
Compute the modular exponentiation \(base^exponent \textrm{mod}\ modulus\). |
|
Returns the nearest prime \(p > x\). |
|
Returns the nearest prime \(p \le x\). |
Computes the prime factors of the positive integer \(x\). |
|
|
Finds the first, smallest primitive n-th root of unity \(x\) that satisfies \(x^n \equiv 1 (\textrm{mod}\ n)\). |
-
class
galois.
GF
[source]¶ Bases:
object
An abstract base class for all Galois field array classes.
Note
This is an abstract base class for all Galois fields. It cannot be instantiated directly. Galois field array classes are created using
galois.GF_factory
.-
classmethod
Elements
(dtype=None)[source]¶ Create 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 field class, i.e.cls.dtypes[0]
.
-
classmethod
Ones
(shape, dtype=None)[source]¶ Create 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 field class, i.e.cls.dtypes[0]
.
-
classmethod
Random
(shape=(), low=0, high=None, dtype=None)[source]¶ Create 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 field class, i.e.cls.dtypes[0]
.
-
classmethod
Zeros
(shape, dtype=None)[source]¶ Create 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 field class, i.e.cls.dtypes[0]
.
-
classmethod
display
(mode='int', poly_var='x')[source]¶ Sets the printing mode for arrays.
- Parameters
Examples
In [1]: GF = galois.GF_factory(2, 3) In [2]: a = GF.Random(4); a Out[2]: GF([5, 5, 0, 3], order=2^3) In [3]: GF.display("poly"); a Out[3]: GF([x^2 + 1, x^2 + 1, 0, x + 1], order=2^3) In [4]: GF.display("poly", "r"); a Out[4]: GF([r^2 + 1, r^2 + 1, 0, r + 1], order=2^3) # Reset the print mode In [5]: GF.display(); a Out[5]: GF([5, 5, 0, 3], order=2^3)
-
alpha
= None¶ The primitive element of the Galois field \(\mathrm{GF}(p^m)\). The primitive element is a root of the primitive polynomial \(p(x)\), such that \(p(\alpha) = 0\). The primitive element is also a multiplicative generator of the field, such that \(\mathrm{GF}(p^m) = \{0, 1, \alpha^1, \alpha^2, \dots, \alpha^{p^m - 2}\}\).
- Type
-
characteristic
= None¶ The prime characteristic \(p\) of the Galois field \(\mathrm{GF}(p^m)\). Adding \(p\) copies of any element will always result in \(0\).
- Type
-
degree
= None¶ The prime characteristic’s degree \(m\) of the Galois field \(\mathrm{GF}(p^m)\). The degree is a positive integer.
- Type
-
dtypes
= []¶ List of valid integer
numpy.dtype
objects that are compatible with this Galois field array class. Valid data types are signed and unsinged integers that can represent decimal values in \([0, p^m)\).- Type
-
order
= None¶ 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.
- Type
-
prim_poly
= None¶ The primitive polynomial \(p(x)\) of the Galois field \(\mathrm{GF}(p^m)\). The primitive polynomial is of degree \(m\) in \(\mathrm{GF}(p)[x]\).
- Type
-
classmethod
-
class
galois.
GF2
(array, dtype=None)[source]¶ Bases:
galois.gf.GF
,galois.gf.GFArray
Galois field array class for \(\mathrm{GF}(2)\) fields.
- 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
,tuple
, orint
.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isnumpy.int64
.
- Returns
The copied input array as a \(\mathrm{GF}(2)\) field array.
- Return type
Examples
GF2 class properties
In [1]: print(galois.GF2) <Galois Field: GF(2^1), prim_poly = x + 1 (3 decimal)> In [2]: galois.GF2.characteristic Out[2]: 2 In [3]: galois.GF2.degree Out[3]: 1 In [4]: galois.GF2.order Out[4]: 2 In [5]: galois.GF2.prim_poly Out[5]: Poly(x + 1, GF2)
Construct arrays in GF2
In [6]: a = galois.GF2([1,0,1,1]); a Out[6]: GF([1, 0, 1, 1], order=2) In [7]: b = galois.GF2([1,1,1,1]); b Out[7]: GF([1, 1, 1, 1], order=2)
Arithmetic with GF2 arrays
# Element-wise addition In [1]: a + b Out[1]: GF([0, 1, 0, 0], order=2) # Element-wise subtraction In [2]: a - b Out[2]: GF([0, 1, 0, 0], order=2) # Element-wise multiplication In [3]: a * b Out[3]: GF([1, 0, 1, 1], order=2) # Element-wise division In [4]: a / b Out[4]: GF([1, 0, 1, 1], order=2)
-
classmethod
target
(target)[source]¶ Retarget the just-in-time compiled
numba
ufuncs.- Parameters
target (str) – The
target
keyword argument fromnumba.vectorize
, either"cpu"
,"parallel"
, or"cuda"
.
-
alpha
= GF(1, order=2)¶ The primitive element of the Galois field \(\mathrm{GF}(p^m)\). The primitive element is a root of the primitive polynomial \(p(x)\), such that \(p(\alpha) = 0\). The primitive element is also a multiplicative generator of the field, such that \(\mathrm{GF}(p^m) = \{0, 1, \alpha^1, \alpha^2, \dots, \alpha^{p^m - 2}\}\).
- Type
-
characteristic
= 2¶ The prime characteristic \(p\) of the Galois field \(\mathrm{GF}(p^m)\). Adding \(p\) copies of any element will always result in \(0\).
- Type
-
degree
= 1¶ The prime characteristic’s degree \(m\) of the Galois field \(\mathrm{GF}(p^m)\). The degree is a positive integer.
- Type
-
dtypes
= [<class 'numpy.uint8'>, <class 'numpy.uint16'>, <class 'numpy.uint32'>, <class 'numpy.int8'>, <class 'numpy.int16'>, <class 'numpy.int32'>, <class 'numpy.int64'>]¶ List of valid integer
numpy.dtype
objects that are compatible with this Galois field array class. Valid data types are signed and unsinged integers that can represent decimal values in \([0, p^m)\).- Type
-
order
= 2¶ 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.
- Type
-
prim_poly
= Poly(x + 1, GF2)¶ The primitive polynomial \(p(x)\) of the Galois field \(\mathrm{GF}(p^m)\). The primitive polynomial is of degree \(m\) in \(\mathrm{GF}(p)[x]\).
- Type
-
class
galois.
GF2m
(*args, **kwargs)[source]¶ Bases:
galois.gf.GF
,galois.gf.GFArray
An abstract base class for all \(\mathrm{GF}(2^m)\) field array classes.
- 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
,tuple
, orint
.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isnumpy.int64
.
- Returns
The copied input array as a \(\mathrm{GF}(2^m)\) field array.
- Return type
Note
This is an abstract base class for all \(\mathrm{GF}(2^m)\) fields. It cannot be instantiated directly. \(\mathrm{GF}(2^m)\) field classes are created using
galois.GF_factory
.-
classmethod
target
(target, mode, rebuild=False)[source]¶ Retarget the just-in-time compiled numba ufuncs.
- Parameters
target (str) – The
target
keyword argument fromnumba.vectorize
, either"cpu"
,"parallel"
, or"cuda"
.mode (str) – The type of field computation, either
"lookup"
or"calculate"
. The “lookup” mode will use Zech log, log, and anti-log lookup tables for speed. The “calculate” mode will not store any lookup tables, but perform field arithmetic on the fly. The “calculate” mode is designed for large fields that cannot store lookup tables in RAM. Generally, “calculate” will be slower than “lookup”.rebuild (bool, optional) – Indicates whether to force a rebuild of the lookup tables. The default is
False
.
-
class
galois.
GFp
(*args, **kwargs)[source]¶ Bases:
galois.gf.GF
,galois.gf.GFArray
An abstract base class for all \(\mathrm{GF}(p)\) field array classes.
- 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
,tuple
, orint
.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isnumpy.int64
.
- Returns
The copied input array as a \(\mathrm{GF}(p)\) field array.
- Return type
Note
This is an abstract base class for all \(\mathrm{GF}(p)\) fields. It cannot be instantiated directly. \(\mathrm{GF}(p)\) field classes are created using
galois.GF_factory
.-
classmethod
target
(target, mode, rebuild=False)[source]¶ Retarget the just-in-time compiled numba ufuncs.
- Parameters
target (str) – The
target
keyword argument fromnumba.vectorize
, either"cpu"
,"parallel"
, or"cuda"
.mode (str) – The type of field computation, either
"lookup"
or"calculate"
. The “lookup” mode will use Zech log, log, and anti-log lookup tables for speed. The “calculate” mode will not store any lookup tables, but perform field arithmetic on the fly. The “calculate” mode is designed for large fields that cannot store lookup tables in RAM. Generally, “calculate” will be slower than “lookup”.rebuild (bool, optional) – Indicates whether to force a rebuild of the lookup tables. The default is
False
.
-
class
galois.
Poly
(coeffs, field=None, order='desc')[source]¶ Bases:
object
A polynomial class with coefficients in any Galois field.
- Parameters
coeffs (array_like) – List of polynomial coefficients of type Galois field array,
np.ndarray
, list, or tuple. The first element is the highest-degree element iforder="desc"
or the first element is the 0-th degree element iforder="asc"
.field (galois.GF, optional) – Optionally specify the field to which the coefficients belong. The default field is
galois.GF2
. Ifcoeffs
is a Galois field array, then that field is used and thefield
parameter 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^(N-1)
) and the last element is the 0-th degree element (x^0
).
Examples
Create polynomials over GF(2)
# Construct a polynominal over GF(2) In [1]: a = galois.Poly([1,0,1,1]); a Out[1]: Poly(x^3 + x + 1, GF2) # Construct the same polynomial by only specifying its non-zero coefficients In [2]: b = galois.Poly.NonZero([1,1,1], [3,1,0]); b Out[2]: Poly(x^3 + x + 1, GF2)
Create polynomials over GF(7)
# Construct the GF(7) field In [3]: GF = galois.GF_factory(7, 1) # Construct a polynominal over GF(7) In [4]: galois.Poly([4,0,3,0,0,2], field=GF) Out[4]: Poly(4x^5 + 3x^3 + 2, GF7) # Construct the same polynomial by only specifying its non-zero coefficients In [5]: galois.Poly.NonZero([4,3,2], [5,3,0], field=GF) Out[5]: Poly(4x^5 + 3x^3 + 2, GF7)
Polynomial arithmetic
In [1]: a = galois.Poly([1,0,6,3], field=GF); a Out[1]: Poly(x^3 + 6x + 3, GF7) In [2]: b = galois.Poly([2,0,2], field=GF); b Out[2]: Poly(2x^2 + 2, GF7) In [3]: a + b Out[3]: Poly(x^3 + 2x^2 + 6x + 5, GF7) In [4]: a - b Out[4]: Poly(x^3 + 5x^2 + 6x + 1, GF7) # Compute the quotient of the polynomial division In [5]: a / b Out[5]: Poly(4x, GF7) # True division and floor division are equivalent In [6]: a / b == a // b Out[6]: True # Compute the remainder of the polynomial division In [7]: a % b Out[7]: Poly(5x + 3, GF7)
-
classmethod
NonZero
(coeffs, degrees, field=<class 'galois.gf2.GF2'>)[source]¶ Examples
# Construct a polynomial over GF2 only specifying the non-zero terms In [1]: a = galois.Poly.NonZero([1,1,1], [3,1,0]); a Out[1]: Poly(x^3 + x + 1, GF2)
-
property
coeffs
¶ The polynomial coefficients as a Galois field array. Coefficients are \([a_{N-1}, \dots, a_1, a_0]\) if
order="desc"
or \([a_0, a_1, \dots, a_{N-1}]\) iforder="asc"
, where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).- Type
galois.GF2, galois.GF2m, galois.GFp, galois.GFpm
-
property
coeffs_asc
¶ The polynomial coefficients \([a_0, a_1, \dots, a_{N-1}]\) as a Galois field array in exponent-ascending order, where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).
- Type
galois.GF2, galois.GF2m, galois.GFp, galois.GFpm
-
property
coeffs_desc
¶ The polynomial coefficients \([a_{N-1}, \dots, a_1, a_0]\) as a Galois field array in exponent-ascending order, where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).
- Type
galois.GF2, galois.GF2m, galois.GFp, galois.GFpm
-
property
decimal
¶ The integer representation of the polynomial. For \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\) with elements in \(\mathrm{GF}(q)\), the decimal representation is \(d = a_{N-1} q^{N-1} + \dots + a_1 q + a_0\) (using integer arithmetic, not field arithmetic) where \(q\) is the field order.
- Type
-
property
degree
¶ The degree of the polynomial, i.e. the highest degree with non-zero coefficient.
- Type
-
property
field
¶ The finite field to which the coefficients belong.
- Type
galois.GF2, galois.GF2m, galois.GFp, galois.GFpm
-
galois.
GF_factory
(characteristic, degree, prim_poly=None, target='cpu', mode='auto', rebuild=False)[source]¶ Factory function to construct Galois field array classes of type \(\mathrm{GF}(p^m)\).
- Parameters
characteristic (int) – The prime characteristic \(p\) of the field \(\mathrm{GF}(p^m)\).
degree (int) – The prime characteristic’s degree \(m\) of the field \(\mathrm{GF}(p^m)\).
prim_poly (galois.Poly, optional) – The primitive polynomial of the field. Default is
None
which will use the Conway polynomial obtained fromgalois.conway_poly
.target (str) – The
target
keyword argument fromnumba.vectorize
, either"cpu"
,"parallel"
, or"cuda"
.mode (str, optional) – The type of field computation, either
"auto"
,"lookup"
, or"calculate"
. The default is"auto"
. The “lookup” mode will use Zech log, log, and anti-log lookup tables for speed. The “calculate” mode will not store any lookup tables, but perform field arithmetic on the fly. The “calculate” mode is designed for large fields that cannot store lookup tables in RAM. Generally, “calculate” will be slower than “lookup”. The “auto” mode will determine whether to use “lookup” or “calculate” based on the field size. For “auto”, field’s withorder <= 2**16
will use the “lookup” mode.rebuild (bool, optional) – Indicates whether to force a rebuild of the lookup tables. The default is
False
.
- Returns
A new Galois field class that is a sublcass of
galois.GF
.- Return type
galois.GF2, galois.GF2m, galois.GFp, galois.GFpm
-
galois.
carmichael
(n)[source]¶ 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 galois.euclidean_algorithm(i, n) == 1]; totatives Out[3]: [1, 3, 7, 9, 11, 13, 17, 19] In [4]: for a in totatives: ...: result = galois.modular_exp(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.
chinese_remainder_theorem
(a, m)[source]¶ Solves the simultaneous system of congruences for \(x\).
\[ \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.chinese_remainder_theorem(a, m); x Out[3]: 39 In [4]: for i in range(len(a)): ...: ai = x % m[i] ...: print(f"{x} % {m[i]} = {ai}, Valid congruence: {ai == a[i]}") ...: 39 % 3 = 0, Valid congruence: True 39 % 4 = 3, Valid congruence: True 39 % 5 = 4, Valid congruence: True
-
galois.
conway_poly
(characteristic, degree)[source]¶ Returns the Conway polynomial for \(\mathrm{GF}(p^m)\).
This function uses Frank Luebeck’s Conway polynomial database. See: http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/index.html.
- Parameters
- Returns
The degree-\(m\) polynomial in \(\mathrm{GF}(p)[x]\).
- Return type
Note
If the \(\mathrm{GF}(p)\) field hasn’t already been created, it will be created in this function since it’s needed in 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, GF2) In [2]: galois.conway_poly(7, 13) Out[2]: Poly(x^13 + 6x^2 + 4, GF7)
-
galois.
euclidean_algorithm
(a, b)[source]¶ Finds the greatest common divisor of two integers.
- Parameters
- Returns
Greatest common divisor of \(a\) and \(b\), i.e. \(gcd(a,b)\).
- Return type
References
Moon, “Error Correction Coding”, Section 5.2.2: The Euclidean Algorithm and Euclidean Domains, p. 181
Examples
In [1]: a, b = 2, 13 In [2]: galois.euclidean_algorithm(a, b) Out[2]: 1
-
galois.
euler_totient
(n)[source]¶ Counts the positive integers (totatives) in \(1 \le k < n\) that are relatively prime to \(n\), i.e. \(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 galois.euclidean_algorithm(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.
extended_euclidean_algorithm
(a, b)[source]¶ Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = gcd(a,b)\).
- Parameters
- Returns
int – Integer \(x\), such that \(a x + b y = gcd(a, b)\).
int – Integer \(y\), such that \(a x + b y = gcd(a, b)\).
int – Greatest common divisor of \(a\) and \(b\).
References
Moon, “Error Correction Coding”, Section 5.2.2: The Euclidean Algorithm and Euclidean Domains, p. 181
https://en.wikipedia.org/wiki/Euclidean_algorithm#Extended_Euclidean_algorithm
Examples
In [1]: a, b = 2, 13 In [2]: x, y, gcd = galois.extended_euclidean_algorithm(a, b) In [3]: x, y, gcd Out[3]: (-6, 1, 1) In [4]: a*x + b*y == gcd Out[4]: True
-
galois.
factors
(x)[source]¶ Computes the positive factors of the integer \(x\).
- Parameters
x (int) – An integer to be factored.
- Returns
Sorted array of factors of \(x\).
- Return type
Examples
In [1]: galois.factors(120) Out[1]: array([ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120])
-
galois.
fermat_primality_test
(n)[source]¶ Probabilistic primality test of \(n\).
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
Examples
# List of some primes In [1]: primes = [257, 24841, 65497] In [2]: for prime in primes: ...: is_prime = galois.fermat_primality_test(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.fermat_primality_test(pseudoprime) ...: p, k = galois.prime_factors(pseudoprime) ...: print("Psuedoprime = {:5d}, Fermat's Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p))) ...: Psuedoprime = 2047, Fermat's Prime Test = True, Prime factors = [23, 89] Psuedoprime = 29341, Fermat's Prime Test = True, Prime factors = [13, 37, 61] Psuedoprime = 65281, Fermat's Prime Test = True, Prime factors = [97, 673]
-
galois.
is_prime
(n)[source]¶ Determines if \(n\) is prime.
This algorithm will first run Fermat’s primality test to check \(n\) for compositeness. If it determines \(n\) is composite, the function will quickly return. If Fermat’s primality test returns
True
, then \(n\) could be prime or pseudoprime. If so, then this function will run seven rounds of Miller-Rabin’s primality test. With this many rounds, a result ofTrue
should have high probability of 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
-
galois.
miller_rabin_primality_test
(n, a=None, rounds=1)[source]¶ Probabilistic primality test of \(n\).
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, optinal) – 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.miller_rabin_primality_test(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.miller_rabin_primality_test(pseudoprime) ...: p, k = galois.prime_factors(pseudoprime) ...: print("Psuedoprime = {:5d}, Miller-Rabin Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p))) ...: Psuedoprime = 2047, Miller-Rabin Prime Test = False, Prime factors = [23, 89] Psuedoprime = 29341, Miller-Rabin Prime Test = False, Prime factors = [13, 37, 61] Psuedoprime = 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.miller_rabin_primality_test(pseudoprime, rounds=7) ...: p, k = galois.prime_factors(pseudoprime) ...: print("Psuedoprime = {:5d}, Miller-Rabin Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p))) ...: Psuedoprime = 2047, Miller-Rabin Prime Test = False, Prime factors = [23, 89] Psuedoprime = 29341, Miller-Rabin Prime Test = False, Prime factors = [13, 37, 61] Psuedoprime = 65281, Miller-Rabin Prime Test = False, Prime factors = [97, 673]
-
galois.
modular_exp
(base, exponent, modulus)[source]¶ Compute the modular exponentiation \(base^exponent \textrm{mod}\ modulus\).
- Parameters
base (array_like) – The base of exponential, an int or an array (follows numpy broadcasting rules).
exponent (array_like) – The exponent, an int or an array (follows numpy broadcasting rules).
modulus (array_like) – The modulus of the computation, an int or an array (follows numpy broadcasting rules).
- Returns
The results of \(base^exponent \textrm{mod}\ modulus\).
- Return type
array_like
-
galois.
next_prime
(x)[source]¶ Returns the nearest prime \(p > x\).
Examples
In [1]: galois.next_prime(13) Out[1]: 17 In [2]: galois.next_prime(15) Out[2]: 17
-
galois.
prev_prime
(x)[source]¶ Returns the nearest prime \(p \le x\).
Examples
In [1]: galois.prev_prime(13) Out[1]: 13 In [2]: galois.prev_prime(15) Out[2]: 13
-
galois.
prime_factors
(x)[source]¶ Computes the prime factors of the positive integer \(x\).
The integer \(x\) can be factored into \(x = p_1^{k_1} p_2^{k_2} \dots p_{n-1}^{k_{n-1}}\).
- Parameters
x (int) – The positive integer to be factored.
- Returns
numpy.ndarray – Sorted array of prime factors \(p = [p_1, p_2, \dots, p_{n-1}]\) with \(p_1 < p_2 < \dots < p_{n-1}\).
numpy.ndarray – Array of corresponding prime powers \(k = [k_1, k_2, \dots, k_{n-1}]\).
Examples
In [1]: p, k = galois.prime_factors(120) In [2]: p, k Out[2]: (array([2, 3, 5]), array([3, 1, 1])) # The product of the prime powers is the factored integer In [3]: np.multiply.reduce(p ** k) Out[3]: 120 # Prime factorization of 1 less than a large prime In [4]: p, k = galois.prime_factors(1000000000000000035000061 - 1) In [5]: p, k Out[5]: (array([2, 3, 5, 17, 19, 51599587203302375387], dtype=object), array([2, 1, 1, 1, 1, 1])) In [6]: np.multiply.reduce(p ** k) Out[6]: 1000000000000000035000060
-
galois.
primitive_root
(n, start=1)[source]¶ Finds the first, smallest primitive n-th root of unity \(x\) that satisfies \(x^n \equiv 1 (\textrm{mod}\ n)\).
- Parameters
- Returns
The first, smallest primitive root of unity modulo \(n\).
- Return type
References
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
In [1]: n = 7 In [2]: root = galois.primitive_root(n); root Out[2]: 3 # Test that the primitive root is a multiplicative generator of GF(n) In [3]: for i in range(1, n): ...: result = galois.modular_exp(root, i, n) ...: print(f"{root}^{i} = {result} (mod {n})") ...: 3^1 = 3 (mod 7) 3^2 = 2 (mod 7) 3^3 = 6 (mod 7) 3^4 = 4 (mod 7) 3^5 = 5 (mod 7) 3^6 = 1 (mod 7) # The algorithm is also efficient for very large prime n In [4]: galois.primitive_root(1000000000000000035000061) Out[4]: 7