## SPFFL

What is SPFFL?

SPFFL (pronounced spiffle) is a small-prime finite-field library, where small means 32 bits or less. Polynomials may have arbitrary degree, as limited by machine resources.

Where is SPFFL?

The source directory is math.arizona.edu/~kerl/src/spffl. A tar file is located at math.arizona.edu/~kerl/src/spffl.tgz.

Why SPFFL?

There are numerous other software packages for doing arithmetic over finite fields, e.g. Pari/GP, Shoup's NTL, Mathematica, etc. Pluses and minuses of SPFFL are as follows:

• My single most important reason for writing SPFFL was to learn by doing. I encourage you to do the same. Nonetheless, SPFFL is available on an as-is basis for anyone who would like to learn from it.

• SPFFL has I/O in a very compact format (examples are below).

• Special cases are made for p=2. This increases computation speed, and also permits an even more compact, hexadecimal I/O format.

• SPFFL aims for reasonable performance, but clarity of implementation is just as important. You will not find cutting-edge algorithms implemented here. SPFFL grew out of my desire for a simple desk calculator (cf. the Unix bc command) which would support finite-field arithmetic. Its main purpose remains that of automating simple computations.

• Unlike Shoup's NTL, there is no global modulus: each intmod or polymod has its own modulus, leading to a more elegant user experience.

• I limit p to 32 bits. This reduces required storage space, and also removes the need for third-party (or my own) arbitrary-precision integer arithmetic, along with the concomitant hard problem of factoring large integers. Any prime of 32 bits or less will have a prime factor of 16 bits or less. There are 6542 primes of 16 bits or less, which may be stored in a table. Thus, 32-bit integer factorization is trivial. The down side of this is that SPFFL is unsuitable for finite fields Fp for large p, e.g. in cryptographic applications.

• SPFFL does use dynamic memory allocation, which permits arbitrary-degree polynomials (as limited by machine resources). However, it cleans up after itself as it runs, via properly coded constructors and destructors, so it has no need for garbage collection, user tweaking via allocatemem() calls, etc.

• Unlike computer-algebra tools such as Mathematica, Maple, or GAP, SPFFL is not monolithic, and does not have startup time measured in seconds. Thus, it permits shell scripting in which executables are repeatedly invoked.

• Since the source code is my own, I can make it run on any platform I port it to, and I do not need to pay license fees.

• SPFFL's data types are not recursive. If you want to make a matrix of matrices, or use triple field extensions, you must create new C++ classes.

• SPFFL has no scripting language of its own. While SPFFL is a subroutine library, there is also a spiff executable which provides a command-line interface to most routines. spiff includes a simple expression parser, while variables, looping, and file I/O are provided by the shell. This offloads the script processing onto the shell, which already exists, freeing me from needing to re-invent the wheel, and allowing me to focus on SPFFL's core mathematical competency. Examples are shown below; the following example prints a multiplication table for F7.

Script file:

```        #!/bin/sh
p=7
elements="`spiff fplist -a \$p`"
for a in \$elements
do
for b in \$elements
do
c=`spiff fpop \$p \$a . \$b`
echo -n " \$c"
done
echo ""
done
```

Output:

```        0  0  0  0  0  0  0
0  1  2  3  4  5  6
0  2  4  6  1  3  5
0  3  6  2  5  1  4
0  4  1  5  2  6  3
0  5  3  1  6  4  2
0  6  5  4  3  2  1
```

Status

SPFFL is a work in progress, and will remain so for as long as I can think of algorithms to implement. There is very little documentation.

Availability

SPFFL has been run on Linux 2.4 and Solaris 5.8, compiled by GCC 3.3 and above. It uses C++ templates; it uses GCC's long long in a few spots. It should run on any Unix with a GCC.

Summary of data types

Data types include:

• Integers, residue class rings (finite fields when the modulus is a prime number), quotient fields (small rationals).
• Polynomials with coefficients in Fp.
• Residue class rings for polynomials with coefficients in Fp (finite fields when the modulus is an irreducible polynomial), quotient fields (rational functions).
• Polynomials with coefficients in Fq.
• Residue class rings for polynomials with coefficients in Fq (finite fields when the modulus is an irreducible polynomial), quotient fields (rational functions).

Thus, double extensions are supported, with tools for embedding double extensions into single extensions.

Data types in detail

C++ data type spiff prefix Notation Description

int z Z Ring
bit_t f2 Z/<2> = F2 Residue field, p=2
intmod_t fp Z/<p> = Fp Residue field
intrat_t q Q Quotient field

f2poly_t f2p F2[x] Ring
f2polymod_t f2pm F2[x]/<f(x)> = F2n Residue field
f2polyrat_t f2pr F2(x) Quotient field

fppoly_t fpp Fp[x] Ring
fppolymod_t fppm Fp[x]/<f(x)> = Fpn Residue field
fppolyrat_t fppr Fp(x) Quotient field

f2npoly_t f2np F2n[y] Ring
f2npolymod_t f2npm F2n[y] / <g(y)> Residue field
f2npolyrat_t f2npr F2n(y) Quotient field

fpnpoly_t fpnp Fpn[y] Ring
fpnpolymod_t fpnpm Fpn[y] / <g(y)> Residue field
fpnpolyrat_t fpnpr Fpn(y) Quotient field

Summary of features

Features include:

• Arithmetic for integers and polynomial rings, residue class rings/fields, and quotient fields.
• Generation of random elements.
• GCD, LCM, totient.
• Irreducibility testing, factorization (Berlekamp).
• Periods of polynomials.
• Printing of tables.
• Discrete log (Shanks).
• Matrix arithmetic for all data types.
• Computation of row echelon form, determinant, matrix inverse.
• Diagonalizability testing for matrices over finite fields (under construction).
• Jordan normal form and rational canonical form for matrices over finite fields (to be implemented).
• Computation of eigenspaces and generalized eigenspaces for matrices over finite fields (under construction).

Features in detail

```Key:
o means coded
. means not coded yet
- means not applicable or not interesting.

Rings:

cmd/type   z    f2p  f2np fpp  fpnp
---------- ---- ---- ---- ---- ----
op         o    o    o    o    .
eval       -    o    o    o    .
rand       -    o    o    o    .
deg        -    o    o    o    .
gcd        o    o    o    o    .
lcm        o    o    o    o    .
totient    o    o    o    o    .
test       o    o    o    o    .
find       -    o    o    o    .
period     -    o    .    .    .
factor     o    o    o    o    .
divisors   o    o    o    o    .
list       -    o    o    o    .
compmx     -    o    o    o    .

----------------------------------------------------------------
Fields:

cmd/type q    fp   f2   f2pm f2pr f2npm f2npr fppm fppr fpnpm fpnpr
-------- ---- ---- ---- ---- ---- ----- ----- ---- ---- ----- -----
op       o    o    .    o    o    o     o     o    o    .     .
tbl      -    o    -    o    -    o     -     o    -    .     -
ord      -    o    -    o    -    o     -     r    -    .     -
findgen  -    o    -    o    -    o     -     .    -    .     -
log      -    o    -    o    -    o     -     .    -    .     -
rand     -    o    o    o    o    o     .     o    .    .     .
chpol    -    -    -    o    -    -     -     .    -    -     -
minpol   -    -    -    o    -    -     -     .    -    -     -
list     -    o    -    o    -    o     -     o    -    .     -
matop    o    o    o    o    o    o     o     o    o    .     .
matord   -    o    o    o    -    .     -     o    -    .     .
matrand  -    o    o    o    o    .     .     o    .    .     .
matchpol -    o    o    o    -    -     -     .    -    -     -
dable    .    .    .    .    .    .     .     .    .    .     .
eisys    .    .    .    .    .    .     .     .    .    .     .
jordan   .    .    .    .    .    .     .     .    .    .     .
ratcanon .    .    .    .    .    .     .     .    .    .     .
```

Examples

to do: many more

```bash\$ f=`spiff f2pop 2 ^ 64 - 2`

bash\$ spiff f2pfactor \$f
2 3 7 b d 43 49 57 5b 61 67 6d 73 75

bash\$ spiff f2pmtbl 13 .
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 2 4 6 8 a c e 3 1 7 5 b 9 f d
0 3 6 5 c f a 9 b 8 d e 7 4 1 2
0 4 8 c 3 7 b f 6 2 e a 5 1 d 9
0 5 a f 7 2 d 8 e b 4 1 9 c 3 6
0 6 c a b d 7 1 5 3 9 f e 8 2 4
0 7 e 9 f 8 1 6 d a 3 4 2 5 c b
0 8 3 b 6 e 5 d c 4 f 7 a 2 9 1
0 9 1 8 2 b 3 a 4 d 5 c 6 f 7 e
0 a 7 d e 4 9 3 f 5 8 2 1 b 6 c
0 b 5 e a 1 f 4 7 c 2 9 d 6 8 3
0 c b 7 5 9 e 2 a 6 1 d f 3 4 8
0 d 9 4 1 c 8 5 2 f b 6 3 e a 7
0 e f 1 d 3 2 c 9 7 6 8 4 a b 5
0 f d 2 9 6 4 b 1 e c 3 8 7 5 a

m=13
for r in `spiff f2pmlist -a \$m`
do
spiff f2pmchpol \$m \$r
done

1:0:0:0:0
1:0:0:0:1
1:0:0:1:1
1:0:0:1:1
1:0:0:1:1
1:0:0:1:1
1:0:1:0:1
1:0:1:0:1
1:1:1:1:1
1:1:0:0:1
1:1:1:1:1
1:1:0:0:1
1:1:1:1:1
1:1:0:0:1
1:1:0:0:1
1:1:1:1:1

spiff f2pperiod `spiff f2plist 4`
10:  0
11:  4
12:  0
13: 15
14:  0
15:  6
16:  0
17:  7
18:  0
19: 15
1a:  0
1b:  6
1c:  0
1d:  7
1e:  0
1f:  5

spiff fpord  35 `spiff fplist -u 35`
1:  1
2: 12
3: 12
4:  6
6:  2
8:  4
9:  6
11:  3
12: 12
13:  4
16:  3
17: 12
18: 12
19:  6
22:  4
23: 12
24:  6
26:  6
27:  4
29:  2
31:  6
32: 12
33: 12
34:  2

```

To do

• links both ways between spffl and ffcomp
• examples
• compilation instructions

Contact information

John Kerl
johnkerl.org
kerl.john.r@gmail.com

Last updated: 2004-08-14