Home

What is RUFFL?

RUFFL (pronounced ruffle) is a Ruby finite-field library for integers mod p, or polynomials with coefficients mod 2. Integers may have arbitrary size and polynomials may have arbitrary degree, as limited by machine resources.

Why RUFFL?

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 RUFFL are as follows:

My single most important reason for writing RUFFL was to learn by doing. I encourage you to do the same. Nonetheless, RUFFL is available on an as-is basis for anyone who would like to learn from it.
RUFFL 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.
RUFFL aims for reasonable performance, but clarity of implementation is just as important. You will not find cutting-edge algorithms implemented here. RUFFL 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.
Unlike computer-algebra tools such as Mathematica, Maple, or GAP, RUFFL is not monolithic, and does not have startup time measured in multiple 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.
This was a nice opportunity for me to teach myself some Ruby: here I am porting part of SPFFL which I wrote several years ago (circa 2004) in C++ with templates.

RUFFL is scriptable since it is written in Ruby. There are also little bash scripts in the cmds subdirectory which provide a command-line interface to most routines. You can code in Ruby, or you can write shell scripts; in the latter case, looping, and file I/O are provided by the shell. (I make use of $(...) in bash, which nests much more nicely than backticks.) Some examples are shown below.

Examples

Print a multiplication table for F7 using a Bash script:

#!/bin/bash
p=7
elements="$(fplist -a $p)"
for a in $elements; do
        for b in $elements; do
                c=$(fp. $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

Ruby script file for the same:

#!/usr/bin/ruby -Wall
require 'Int_mod.rb'
elements = Int_mod.elements_for_modulus(7)
for a in elements
    for b in elements
        c = a * b
        printf " #{c}"
    end
    printf "\n"
end

Division table for the 16-element field mod x^4 + x + 1:

#!/usr/bin/ruby -Wall
require 'F2_poly_mod.rb'
elements = F2_poly_mod.units_for_modulus(0x13)
for a in elements
    for b in elements
        c = a / b
        printf " #{c}"
    end
    printf "\n"
end

Output:

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 3 2 1 0 7 6
0 2 4 6 8 a c e 3 1 6 4 2 0 e c
0 3 6 5 c f a 9 b 8 5 6 3 0 9 a
0 4 8 c 3 7 b f 6 2 c 8 4 0 f b
0 5 a f 7 2 d 8 e b f a 5 0 8 d
0 6 c a b d 7 1 5 3 a c 6 0 1 7
0 7 e 9 f 8 1 6 d a 9 e 7 0 6 1
0 8 3 b 6 e 5 d c 4 b 3 8 0 d 5
0 9 1 8 2 b 3 a 4 d 8 1 9 0 a 3
0 3 6 5 c f a 9 b 8 5 6 3 0 9 a
0 2 4 6 8 a c e 3 1 6 4 2 0 e c
0 1 2 3 4 5 6 7 8 9 3 2 1 0 7 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 7 e 9 f 8 1 6 d a 9 e 7 0 6 1
0 6 c a b d 7 1 5 3 a c 6 0 1 7

Orders of units in the multiplicative group mod 13:

bash$ fpord 13 $(fplist -u 13)
1
12
3
6
4
12
12
4
3
6
12
2

Factorization of x^64 - x mod 2:

bash$ a=$( f- $(fexp 2 64) 2)

bash$ ffactor $a
10000000000000002 = 2 3 7 b d 43 49 57 5b 61 67 6d 73 75

Find a random irreducible mod 2, and a generator:

irb(main):001:0> require 'F2_poly_factor.rb'
=> true
irb(main):002:0> require 'Order.rb'
=> true

irb(main):003:0> irr = F2_poly_factor.random_irr(64)
=> 16d3d0ec441738ff3
irb(main):004:0> g = Order.F2_poly_mod_generator(irr)
=> 3

Status

RUFFL 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

RUFFL is released under the terms of the GNU General Public License (GPL). Please see the file LICENSE.txt for more details. Also please visit www.gnu.org.

RUFFL has been run on Linux 2.6 and Ruby 1.8.7.

Summary of features

Features include:

Arithmetic for integers and polynomial rings, and residue class rings/fields.
Generation of random elements.
GCD, LCM, totient.
Irreducibility testing, factorization (Berlekamp).
Periods of polynomials (in port).
Printing of tables.

Features in detail

Integers   Integers mod m  F2[x]       F2[x]/<r(x)>
--------   --------------  -----       ---------------
z+         zm+             f+          fm+
z-         zm-             f-          fm-
z.         zm.             f.          fm.
zdiv       zmdiv           fdiv        fmdiv
zmod       zmexp           fmod        fmexp
zexp       zmrandom        fexp        fmrandom
zfactorial zmfindgen       ftotient    fmfindgen
zgcd       zmord           fgcd        fmord
zegcd      zmlist          fegcd       fmlist
zlcm       zmtbl           flcm        fmtbl
zfactor                    fdeg
ztotient                   ffactor
zrandom                    frandom
zdivisors                  ftestirr
                           flowestirr
                           frandomirr
                           fperiod
                           ftestprim
                           fdivisors

Provide feedback

Saved searches

Use saved searches to filter your results more quickly