Compilation Modes¶

The galois library supports finite field arithmetic on NumPy arrays by just-in-time compiling custom NumPy ufuncs. It uses Numba to JIT compile ufuncs written in pure Python. The created FieldArray subclass GF intercepts NumPy calls to a given ufunc, JIT compiles the finite field ufunc (if not already cached), and then invokes the new ufunc on the input array(s).

There are two primary compilation modes: "jit-lookup" and "jit-calculate". The supported ufunc compilation modes of a given finite field are listed in ufunc_modes.

In [1]: GF = galois.GF(3**5)

In [2]: GF.ufunc_modes
Out[2]: ['jit-lookup', 'jit-calculate']

Large finite fields, which have numpy.object_ data types, use "python-calculate" which utilizes non-compiled, pure-Python ufuncs.

In [3]: GF = galois.GF(2**100)

In [4]: GF.ufunc_modes
Out[4]: ['python-calculate']

Lookup tables¶

The lookup table compilation mode "jit-lookup" uses exponential, logarithm, and Zech logarithm lookup tables to speed up arithmetic computations. These tables are built once at FieldArray subclass-creation time during the call to GF().

The exponential and logarithm lookup tables map every finite field element to a power of the primitive element \(\alpha\).

\[x = \alpha^i\]

\[\textrm{log}_{\alpha}(x) = i\]

With these lookup tables, many arithmetic operations are simplified. For instance, multiplication of two finite field elements is reduced to three lookups and one integer addition.

\[\begin{split}x \cdot y &= \alpha^m \cdot \alpha^n \\ &= \alpha^{m + n}\end{split}\]

The Zech logarithm is defined below. A similar lookup table is created for it.

\[1 + \alpha^i = \alpha^{Z(i)}\]

\[Z(i) = \textrm{log}_{\alpha}(1 + \alpha^i)\]

With Zech logarithms, addition of two finite field elements becomes three lookups, one integer addition, and one integer subtraction.

\[\begin{split}x + y &= \alpha^m + \alpha^n \\ &= \alpha^m (1 + \alpha^{n - m}) \\ &= \alpha^m \alpha^{Z(n - m)} \\ &= \alpha^{m + Z(n - m)}\end{split}\]

Finite fields with order less than \(2^{20}\) use lookup tables by default. In the limited cases where explicit calculation is faster than table lookup, the explicit calculation is used.

In [5]: GF = galois.GF(3**5)

In [6]: GF.ufunc_mode
Out[6]: 'jit-lookup'

Explicit calculation¶

Finite fields with order greater than \(2^{20}\) use explicit calculation by default. This eliminates the need to store large lookup tables. However, explicit calculation is usually slower than table lookup.

In [7]: GF = galois.GF(2**24)

In [8]: GF.ufunc_mode
Out[8]: 'jit-calculate'

However, if memory is of no concern, even large fields can be compiled to use lookup tables. Initially constructing the lookup tables may take some time, however.

In [9]: GF = galois.GF(2**24, compile="jit-lookup")

In [10]: GF.ufunc_mode
Out[10]: 'jit-lookup'

Python explicit calculation¶

Large finite fields cannot use JIT compiled ufuncs. This is because they cannot use NumPy integer data types. This is either because the order of the field or an intermediate arithmetic result is larger than the max value of numpy.int64.

These finite fields use the numpy.object_ data type and have ufunc compilation mode "python-calculate". This mode does not compile the Python functions, but rather converts them into Python ufuncs using numpy.frompyfunc(). The lack of JIT compilation allows the ufuncs to operate on Python integers, which have unlimited size. This does come with a performance penalty, however.

In [11]: GF = galois.GF(2**100)

In [12]: GF.ufunc_mode
Out[12]: 'python-calculate'

Recompile the ufuncs¶

The compilation mode may be explicitly set during creation of the FieldArray subclass using the compile keyword argument to GF().

Here, the FieldArray subclass for \(\mathrm{GF}(3^5)\) would normally select "jit-lookup" as its default compilation mode. However, we can intentionally choose explicit calculation.

In [13]: GF = galois.GF(3**5, compile="jit-calculate")

In [14]: GF.ufunc_mode
Out[14]: 'jit-calculate'

After a FieldArray subclass has been created, its compilation mode may be changed using the compile() method.

In [15]: GF.compile("jit-lookup")

In [16]: GF.ufunc_mode
Out[16]: 'jit-lookup'

This will not immediately recompile all of the ufuncs. The ufuncs are compiled on-demand (during their first invocation) and only if a cached version is not available.

Last update: May 17, 2022