galois

A performant numpy extension for Galois fields.

Classes

GF(array[, dtype])

Create an array over \(\mathrm{GF}(p^m)\).

GF2(array[, dtype])

Create an array over \(\mathrm{GF}(2)\).

Poly(coeffs[, field, order])

Create a polynomial over a Galois field, \(p(x) \in \mathrm{GF}(q)[x]\).

Class Factory Functions

GF_factory(characteristic, degree[, …])

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

Functions

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\).

chinese_remainder_theorem(a, m)

Solves the simultaneous system of congruences for \(x\).

conway_poly(characteristic, degree)

Returns the Conway polynomial for \(\mathrm{GF}(p^m)\).

euclidean_algorithm(a, b)

Finds the greatest common divisor of two integers.

euler_totient(n)

Counts the positive integers (totatives) in \(1 \le k < n\) that are relatively prime to \(n\), i.e. \(gcd(n, k) = 1\).

extended_euclidean_algorithm(a, b)

Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = gcd(a,b)\).

factors(x)

Computes the positive factors of the integer \(x\).

fermat_primality_test(n)

Probabilistic primality test of \(n\).

is_prime(n)

Determines if \(n\) is prime.

miller_rabin_primality_test(n[, a, rounds])

Probabilistic primality test of \(n\).

modular_exp(base, exponent, modulus)

Compute the modular exponentiation \(base^exponent \textrm{mod}\ modulus\).

next_prime(x)

Returns the nearest prime \(p > x\).

prev_prime(x)

Returns the nearest prime \(p \le x\).

prime_factors(x)

Computes the prime factors of the positive integer \(x\).

primitive_root(n[, start])

Finds the first, smallest primitive n-th root of unity \(x\) that satisfies \(x^n \equiv 1 (\textrm{mod}\ n)\).
class galois.GF(array, dtype=None)[source]

Bases: numpy.ndarray

Create an array over \(\mathrm{GF}(p^m)\).

Warning

This is an abstract base class for all Galois field array classes. galois.GF cannot be instantiated directly. Instead, Galois field array classes are created using galois.GF_factory.

For example, one can create the \(\mathrm{GF}(7)\) field array class as follows:

In [1]: GF7 = galois.GF_factory(7, 1)

In [2]: print(GF7)
<Galois Field: GF(7^1), prim_poly = x + 4 (11 decimal)>

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([[1, 4, 3, 2, 1],
    [6, 6, 0, 2, 0]], order=7)
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, or int.

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is numpy.int64.

Returns

The copied input array as a \(\mathrm{GF}(p^m)\) field array.

Return type

galois.GF

Examples

Construct various kinds of Galois fields using galois.GF_factory.

# Construct a GF(2^m) class
In [5]: GF256 = galois.GF_factory(2, 8); print(GF256)
<Galois Field: GF(2^8), prim_poly = x^8 + x^4 + x^3 + x^2 + 1 (285 decimal)>

# Construct a GF(p) class
In [6]: GF571 = galois.GF_factory(571, 1); print(GF571)
<Galois Field: GF(571^1), prim_poly = x + 568 (1139 decimal)>

# Construct a very large GF(2^m) class
In [7]: GF2m = galois.GF_factory(2, 100); print(GF2m)
<Galois Field: GF(2^100), prim_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 (1267650600228486663289456659305 decimal)>

# Construct a very large GF(p) class
In [8]: GFp = galois.GF_factory(36893488147419103183, 1); print(GFp)
<Galois Field: GF(36893488147419103183^1), prim_poly = x + 36893488147419103180 (73786976294838206363 decimal)>

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 as dtype=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([177, 102,  68, 122, 232, 101, 144, 126,  40, 195], 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([ 49, 146, 163,  47, 209,   2, 214,  28, 168, 203], order=2^8)

In [16]: a.dtype
Out[16]: dtype('uint32')

Arrays can 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 in memory. 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)[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 is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of all the field’s elements.

Return type

galois.GF

Examples

In [1]: GF = galois.GF_factory(31, 1)

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 Ones(shape, dtype=None)[source]

Create a Galois field array with all ones.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.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 is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of ones.

Return type

galois.GF

Examples

In [1]: GF = galois.GF_factory(31, 1)

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)[source]

Create a Galois field array with random field elements.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.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 is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of random field elements.

Return type

galois.GF

Examples

In [1]: GF = galois.GF_factory(31, 1)

In [2]: GF.Random((2,5))
Out[2]: 
GF([[18, 28, 19, 30, 14],
    [16, 10, 13, 11, 18]], order=31)
classmethod Range(start, stop, step=1, dtype=None)[source]

Create 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 is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of a range of field elements.

Return type

galois.GF

Examples

In [1]: GF = galois.GF_factory(31, 1)

In [2]: GF.Range(10,20)
Out[2]: GF([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], order=31)
classmethod Zeros(shape, dtype=None)[source]

Create a Galois field array with all zeros.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.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 is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of zeros.

Return type

galois.GF

Examples

In [1]: GF = galois.GF_factory(31, 1)

In [2]: GF.Zeros((2,5))
Out[2]: 
GF([[0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]], order=31)
classmethod display(mode='int', poly_var='x')[source]

Sets the printing mode for arrays.

Parameters

  • mode (str, optional) – The field element display mode, either "int" (default) or "poly".

  • poly_var (str, optional) – The polynomial representation’s variable. The default is "x".

Examples

Change the display mode by calling the galois.GF.display method.

In [1]: GF = galois.GF_factory(2, 3)

In [2]: a = GF.Random(4); a
Out[2]: GF([6, 1, 7, 7], order=2^3)

In [3]: GF.display("poly"); a
Out[3]: GF([x^2 + x, 1, x^2 + x + 1, x^2 + x + 1], order=2^3)

In [4]: GF.display("poly", "r"); a
Out[4]: GF([r^2 + r, 1, r^2 + r + 1, r^2 + r + 1], order=2^3)

# Reset the print mode
In [5]: GF.display(); a
Out[5]: GF([6, 1, 7, 7], order=2^3)

The galois.GF.display method can also be used as a context manager.

# The original display mode
In [6]: print(a)
GF([6, 1, 7, 7], order=2^3)

# The new display context
In [7]: with GF.display("poly"):
   ...:     print(a)
   ...: 
GF([x^2 + x, 1, x^2 + x + 1, x^2 + x + 1], order=2^3)

# Returns to the original display mode
In [8]: print(a)
GF([6, 1, 7, 7], order=2^3)
classmethod target(target, mode, rebuild=False)[source]

Retarget the just-in-time compiled numba ufuncs.

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

int

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

int

degree = None

The prime characteristic’s degree \(m\) of the Galois field \(\mathrm{GF}(p^m)\). The degree is a positive integer.

Type

int

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)\).

Type

list

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

int

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

galois.Poly

ufunc_mode = None

The mode for ufunc compilation, either "lookup" or "calculate".

Type

str

ufunc_target = None

The numba target for the JIT-compiled ufuncs, either "cpu", "parallel", or "cuda".

Type

str

class galois.GF2(array, dtype=None)[source]

Bases: galois.gf.GF

Create an array over \(\mathrm{GF}(2)\).

Note

This Galois field class is a pre-made subclass of galois.GF. It is included in the package because of the ubiquity of \(\mathrm{GF}(2)\) fields.

# The pre-made GF(2) class
In [1]: print(galois.GF2)
<Galois Field: GF(2^1), prim_poly = x + 1 (3 decimal)>

# The GF class factory for `(2,1)` returns `galois.GF2`
In [2]: GF2 = galois.GF_factory(2, 1); print(GF2)
<Galois Field: GF(2^1), prim_poly = x + 1 (3 decimal)>

In [3]: GF2 is galois.GF2
Out[3]: True
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, or int.

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is numpy.int64.

Returns

The copied input array as a \(\mathrm{GF}(2)\) field array.

Return type

galois.GF2

Examples

Various Galois field properties are accessible as class attributes.

In [4]: print(galois.GF2)
<Galois Field: GF(2^1), prim_poly = x + 1 (3 decimal)>

In [5]: galois.GF2.characteristic
Out[5]: 2

In [6]: galois.GF2.degree
Out[6]: 1

In [7]: galois.GF2.order
Out[7]: 2

In [8]: galois.GF2.prim_poly
Out[8]: Poly(x + 1, GF(2))

Construct arrays over \(\mathrm{GF}(2)\).

In [9]: a = galois.GF2([1,0,1,1]); a
Out[9]: GF([1, 0, 1, 1], order=2)

In [10]: b = galois.GF2([1,1,1,1]); b
Out[10]: GF([1, 1, 1, 1], order=2)

Perform array arithmetic over \(\mathrm{GF}(2)\).

# Element-wise addition
In [11]: a + b
Out[11]: GF([0, 1, 0, 0], order=2)

# Element-wise subtraction
In [12]: a - b
Out[12]: GF([0, 1, 0, 0], order=2)

# Element-wise multiplication
In [13]: a * b
Out[13]: GF([1, 0, 1, 1], order=2)

# Element-wise division
In [14]: a / b
Out[14]: GF([1, 0, 1, 1], order=2)
classmethod Elements(dtype=None)

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 is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of all the field’s elements.

Return type

galois.GF

Examples

In [1]: GF = galois.GF_factory(31, 1)

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 Ones(shape, dtype=None)

Create a Galois field array with all ones.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.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 is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of ones.

Return type

galois.GF

Examples

In [1]: GF = galois.GF_factory(31, 1)

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)

Create a Galois field array with random field elements.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.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 is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of random field elements.

Return type

galois.GF

Examples

In [1]: GF = galois.GF_factory(31, 1)

In [2]: GF.Random((2,5))
Out[2]: 
GF([[25, 10, 22, 23, 26],
    [24, 22, 29, 25, 23]], order=31)
classmethod Range(start, stop, step=1, dtype=None)

Create 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 is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of a range of field elements.

Return type

galois.GF

Examples

In [1]: GF = galois.GF_factory(31, 1)

In [2]: GF.Range(10,20)
Out[2]: GF([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], order=31)
classmethod Zeros(shape, dtype=None)

Create a Galois field array with all zeros.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.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 is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of zeros.

Return type

galois.GF

Examples

In [1]: GF = galois.GF_factory(31, 1)

In [2]: GF.Zeros((2,5))
Out[2]: 
GF([[0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]], order=31)
classmethod display(mode='int', poly_var='x')

Sets the printing mode for arrays.

Parameters

  • mode (str, optional) – The field element display mode, either "int" (default) or "poly".

  • poly_var (str, optional) – The polynomial representation’s variable. The default is "x".

Examples

Change the display mode by calling the galois.GF.display method.

In [1]: GF = galois.GF_factory(2, 3)

In [2]: a = GF.Random(4); a
Out[2]: GF([4, 4, 3, 6], order=2^3)

In [3]: GF.display("poly"); a
Out[3]: GF([x^2, x^2, x + 1, x^2 + x], order=2^3)

In [4]: GF.display("poly", "r"); a
Out[4]: GF([r^2, r^2, r + 1, r^2 + r], order=2^3)

# Reset the print mode
In [5]: GF.display(); a
Out[5]: GF([4, 4, 3, 6], order=2^3)

The galois.GF.display method can also be used as a context manager.

# The original display mode
In [6]: print(a)
GF([4, 4, 3, 6], order=2^3)

# The new display context
In [7]: with GF.display("poly"):
   ...:     print(a)
   ...: 
GF([x^2, x^2, x + 1, x^2 + x], order=2^3)

# Returns to the original display mode
In [8]: print(a)
GF([4, 4, 3, 6], order=2^3)
classmethod target(target)[source]

Retarget the just-in-time compiled numba ufuncs.

Parameters

target (str) – The target keyword argument from numba.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

int

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

int

degree = 1

The prime characteristic’s degree \(m\) of the Galois field \(\mathrm{GF}(p^m)\). The degree is a positive integer.

Type

int

dtypes = [<class 'numpy.uint8'>, <class 'numpy.uint16'>, <class 'numpy.uint32'>, <class 'numpy.int8'>, <class 'numpy.int16'>, <class 'numpy.int32'>, <class 'numpy.int64'>]

List of valid integer numpy.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)\).

Type

list

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

int

prim_poly = Poly(x + 1, GF(2))

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

galois.Poly

ufunc_mode = 'calculate'

The mode for ufunc compilation, either "lookup" or "calculate".

Type

str

ufunc_target = 'cpu'

The numba target for the JIT-compiled ufuncs, either "cpu", "parallel", or "cuda".

Type

str

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

Bases: object

Create a polynomial over a Galois field, \(p(x) \in \mathrm{GF}(q)[x]\).

The polynomial \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\) has coefficients \(\{a_{N-1}, \dots, a_1, a_0\}\) in \(\mathrm{GF}(q)\).

Parameters

  • coeffs (array_like) – List of polynomial coefficients \(\{a_{N-1}, \dots, a_1, a_0\}\) with type galois.GF, numpy.ndarray, list, or tuple. The first element is the highest-degree element if order="desc" or the first element is the 0-th degree element if order="asc".

  • field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2. If coeffs is a Galois field array, then that field is used and the field argument is ignored.

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

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Create a polynomial over \(\mathrm{GF}(2)[x]\).

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}(7)[x]\).

In [3]: GF7 = galois.GF_factory(7, 1)

In [4]: galois.Poly([4,0,3,0,0,2], field=GF7)
Out[4]: Poly(4x^5 + 3x^3 + 2, GF(7))

In [5]: galois.Poly.Degrees([5,3,0], coeffs=[4,3,2], field=GF7)
Out[5]: Poly(4x^5 + 3x^3 + 2, GF(7))

Polynomial arithmetic using binary operators.

In [6]: a = galois.Poly([1,0,6,3], field=GF7); a
Out[6]: Poly(x^3 + 6x + 3, GF(7))

In [7]: b = galois.Poly([2,0,2], field=GF7); b
Out[7]: Poly(2x^2 + 2, GF(7))

In [8]: a + b
Out[8]: Poly(x^3 + 2x^2 + 6x + 5, GF(7))

In [9]: a - b
Out[9]: Poly(x^3 + 5x^2 + 6x + 1, GF(7))

# Compute the quotient of the polynomial division
In [10]: a / b
Out[10]: Poly(4x, GF(7))

# 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(5x + 3, GF(7))
classmethod Degrees(degrees, coeffs=None, field=<class 'galois.gf2.GF2'>)[source]

Create a polynomial over \(\mathrm{GF}(q)[x]\) from its non-zero degrees.

Parameters

  • degrees (list) – The 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).

  • roots (array_like) – List of roots in \(\mathrm{GF}(q)\) of the desired polynomial.

  • field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)[x]\) 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}(7)[x]\) by specifying the degrees with non-zero coefficients.

In [2]: GF7 = galois.GF_factory(7, 1)

In [3]: galois.Poly.Degrees([3,1,0], coeffs=[5,2,1], field=GF7)
Out[3]: Poly(5x^3 + 2x + 1, GF(7))
classmethod Identity(field=<class 'galois.gf2.GF2'>)[source]

Create the identity polynomial, \(p(x) = x \in \mathrm{GF}(q)[x]\).

Parameters

field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct the identity polynomial over \(\mathrm{GF}(2)[x]\).

In [1]: galois.Poly.Identity()
Out[1]: Poly(x, GF(2))

Construct the identity polynomial over \(\mathrm{GF}(7)[x]\).

In [2]: GF7 = galois.GF_factory(7, 1)

In [3]: galois.Poly.Identity(field=GF7)
Out[3]: Poly(x, GF(7))
classmethod Integer(integer, field=<class 'galois.gf2.GF2'>, order='desc')[source]

Create a polynomial over \(\mathrm{GF}(q)[x]\) from its integer representation.

The integer value \(d\) represents polynomial \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\) over field \(\mathrm{GF}(q)\) if \(d = a_{N-1} q^{N-1} + \dots + a_1 q + a_0\) using integer arithmetic, not field arithmetic.

Parameters

  • integer (int) – The integer representation of the polynomial \(p(x)\).

  • field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)[x]\) from its integer representation.

In [1]: galois.Poly.Integer(5)
Out[1]: Poly(x^2 + 1, GF(2))

Construct a polynomial over \(\mathrm{GF}(7)[x]\) from its integer representation.

In [2]: GF7 = galois.GF_factory(7, 1)

In [3]: galois.Poly.Integer(9, field=GF7)
Out[3]: Poly(x + 2, GF(7))
classmethod One(field=<class 'galois.gf2.GF2'>)[source]

Create the one polynomial, \(p(x) = 1 \in \mathrm{GF}(q)[x]\).

Parameters

field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct the one polynomial over \(\mathrm{GF}(2)[x]\).

In [1]: galois.Poly.One()
Out[1]: Poly(1, GF(2))

Construct the one polynomial over \(\mathrm{GF}(7)[x]\).

In [2]: GF7 = galois.GF_factory(7, 1)

In [3]: galois.Poly.One(field=GF7)
Out[3]: Poly(1, GF(7))
classmethod Roots(roots, field=<class 'galois.gf2.GF2'>)[source]

Create a monic polynomial in \(\mathrm{GF}(q)[x]\) from its roots.

The polynomial \(p(x)\) with roots \(\{r_0, r_1, \dots, r_{N-1}\}\) is:

\[p(x) = (x - r_0) (x - r_1) \dots (x - r_{N-1})\]
Parameters

  • roots (array_like) – List of roots in \(\mathrm{GF}(q)\) of the desired polynomial.

  • field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)[x]\) 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}(7)[x]\) from a list of its roots.

In [4]: GF7 = galois.GF_factory(7, 1)

In [5]: roots = [2,6,1]

In [6]: p = galois.Poly.Roots(roots, field=GF7); p
Out[6]: Poly(x^3 + 5x^2 + 6x + 2, GF(7))

In [7]: p(roots)
Out[7]: GF([0, 0, 0], order=7)
classmethod Zero(field=<class 'galois.gf2.GF2'>)[source]

Create the zero polynomial, \(p(x) = 0 \in \mathrm{GF}(q)[x]\).

Parameters

field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct the zero polynomial over \(\mathrm{GF}(2)[x]\).

In [1]: galois.Poly.Zero()
Out[1]: Poly(0, GF(2))

Construct the zero polynomial over \(\mathrm{GF}(7)[x]\).

In [2]: GF7 = galois.GF_factory(7, 1)

In [3]: galois.Poly.Zero(field=GF7)
Out[3]: Poly(0, GF(7))
static divmod(dividend, divisor)[source]
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}\}\) if order="asc", where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).

Type

galois.GF

property coeffs_asc

The polynomial coefficients \(\{a_0, a_1, \dots, a_{N-1}\}\) as a Galois field array in degree-ascending order, where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).

Type

galois.GF

property coeffs_desc

The polynomial coefficients \(\{a_{N-1}, \dots, a_1, a_0\}\) as a Galois field array in degree-ascending order, where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).

Type

galois.GF

property degree

The degree of the polynomial, i.e. the highest degree with non-zero coefficient.

Type

int

property field

The finite field to which the coefficients belong.

Type

galois.GF

property integer

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 integer 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

int

property order

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

Type

str

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 from galois.conway_poly.

  • target (str) – The target keyword argument from numba.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 with order <= 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 array class that is a sublcass of galois.GF.

Return type

galois.GF

Examples

Construct various kinds of Galois fields.

# Construct a GF(2^m) class
In [1]: GF256 = galois.GF_factory(2, 8); print(GF256)
<Galois Field: GF(2^8), prim_poly = x^8 + x^4 + x^3 + x^2 + 1 (285 decimal)>

# Construct a GF(p) class
In [2]: GF571 = galois.GF_factory(571, 1); print(GF571)
<Galois Field: GF(571^1), prim_poly = x + 568 (1139 decimal)>

# Construct a very large GF(2^m) class
In [3]: GF2m = galois.GF_factory(2, 100); print(GF2m)
<Galois Field: GF(2^100), prim_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 (1267650600228486663289456659305 decimal)>

# Construct a very large GF(p) class
In [4]: GFp = galois.GF_factory(36893488147419103183, 1); print(GFp)
<Galois Field: GF(36893488147419103183^1), prim_poly = x + 36893488147419103180 (73786976294838206363 decimal)>

See galois.GF for more examples of what a Galois field array can do.

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

int

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

int

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

  • 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)\).

Returns

The degree-\(m\) polynomial in \(\mathrm{GF}(p)[x]\).

Return type

galois.Poly

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, GF(2))

In [2]: galois.conway_poly(7, 13)
Out[2]: Poly(x^13 + 6x^2 + 4, GF(7))
galois.euclidean_algorithm(a, b)[source]

Finds the greatest common divisor of two integers.

Parameters

  • a (int) – Any integer.

  • b (int) – Any integer.

Returns

Greatest common divisor of \(a\) and \(b\), i.e. \(gcd(a,b)\).

Return type

int

References

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

int

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

  • a (int) – Any integer.

  • b (int) – Any integer.

Returns

  • int – Integer \(x\), such that \(a x + b y = gcd(a, b)\).

  • int – Integer \(y\), such that \(a x + b y = gcd(a, b)\).

  • int – Greatest common divisor of \(a\) and \(b\).

References

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

numpy.ndarray

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

bool

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 of True 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

bool

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

bool

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\).

Parameters

x (int) – A positive integer.

Returns

The nearest prime \(p > x\).

Return type

int

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\).

Parameters

x (int) – A positive integer.

Returns

The nearest prime \(p \le x\).

Return type

int

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

  • n (int) – A positive integer \(n > 1\).

  • start (int, optional) – Initial primitive root hypothesis. The resulting primitive root will be root >= start. The default is 1.

Returns

The first, smallest primitive root of unity modulo \(n\).

Return type

int

References

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