SPFFL

What is SPFFL?
Where is SPFFL?
Why SPFFL?
Status
Availability
Summary of data types
Data types in detail
Summary of features
Features in detail
Examples
To do
Contact information

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 F_p 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 F₇.
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 is released under the terms of the GNU General Public License (GPL). Please see the file COPYING for more details. Also please visit www.gnu.org.

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 F_p.
Residue class rings for polynomials with coefficients in F_p (finite fields when the modulus is an irreducible polynomial), quotient fields (rational functions).
Polynomials with coefficients in F_q.
Residue class rings for polynomials with coefficients in F_q (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> = F₂	Residue field, p=2
`intmod_t`	`fp`	Z/<p> = F_p	Residue field
`intrat_t`	`q`	Q	Quotient field

`f2poly_t`	`f2p`	F₂[x]	Ring
`f2polymod_t`	`f2pm`	F₂[x]/<f(x)> = F_2ⁿ	Residue field
`f2polyrat_t`	`f2pr`	F₂(x)	Quotient field

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

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

`fpnpoly_t`	`fpnp`	F_pⁿ[y]	Ring
`fpnpolymod_t`	`fpnpm`	F_pⁿ[y] / <g(y)>	Residue field
`fpnpolyrat_t`	`fpnpr`	F_pⁿ(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