Finite field arithmetic in BASIC

→Library header file
→Applications survey
→Download page

Library header file

' ***************************************************************************************
'Subject: Basic library include file for polynomial arithmetic modulo p.
'         (version exclusively for characteristic 2 in packet PolMods.zip)
'Author : Sjoerd.J.Schaper
'Date   : 11-01-2012
'Code   : FreeBasic 1.06.0 (QuickBasic 7.1 adaptation in packet PolMods.zip)
'
' ***************************************************************************************
CONST nmx = 256, pmx = 27 '           max.degree, primes
CONST LB = 15, MB = &H8000& '         bigint base
'
' ***************************************************************************************
TYPE Poly FIELD = 1 '                 univariate polynomial:
   n AS SHORT '                       degree and
   c(nmx) AS LONG '                   coefficients
END TYPE
TYPE Bigi FIELD = 1 '                 big integer:
   l AS SHORT '                       length,
   s AS SHORT '                       sign and
   d(nmx) AS SHORT '                  base 2^ 15 digits
END TYPE
DIM SHARED Modulus AS SHORT '         field characteristic < 32768
'
' ***************************************************************************************
'                             Initialization and assignment
' ***************************************************************************************
DECLARE FUNCTION Setchar (ByVal p AS SHORT) AS SHORT
'Set prime field characteristic, returns 0 if composite(p)
DECLARE SUB Letc (ByRef f AS Poly, ByVal c AS SHORT)
'Set f to constant c
DECLARE SUB Letm (ByRef f AS Poly, ByVal c AS SHORT)
'Set f to monomial X + c
DECLARE SUB Rndp (ByRef f AS Poly, ByVal n AS SHORT, ByVal m AS SHORT)
'f:= random monic polynomial of degree n with m non-zero coefficients
DECLARE SUB Leti (ByRef a AS Bigi, ByVal b AS LONG)
'Let bigint a = b
'
' ***************************************************************************************
'                                    In- and output
' ***************************************************************************************
DECLARE FUNCTION Parsp (ByRef f AS Poly, ByVal g AS ZSTRING PTR) AS SHORT
'Parse input polynomial, set modulus to input fractions
DECLARE SUB Prntp (ByRef f AS Poly, ByRef g AS STRING)
'Pretty print polynomial with prefix g
DECLARE SUB Readp (ByRef f AS Poly, ByVal n AS SHORT)
'Input coefficient vector f.c[n..0]
DECLARE FUNCTION CRTfile (ByVal p AS SHORT) AS SHORT
'Open an inputfile for LargeInt-module CRTtrans.bas
'set p = number of CRT-primes (<= pmx), p = 0 to close
DECLARE SUB CRTprnt (f() AS Poly, ByVal sw AS SHORT, ByVal g AS ZSTRING PTR)
'Print polynomial array f() to open file #Tfile.
'Set sw = 0 for integral f, sw = 1 for rational f
'with denominators cleared, sw = 2 for printing fractions.
'Set sw + 4 to divide out content(f), g is a comment string.
DECLARE SUB CRTchar (ByVal p AS SHORT)
'Fast field characteristic, without primality test
'
' ***************************************************************************************
'                             Polynomial arithmetic functions
' ***************************************************************************************
DECLARE SUB Addp (ByRef f AS Poly, ByRef g AS Poly)
'Polynomial f:= f + g
DECLARE SUB Divdp (ByRef f AS Poly, ByRef g AS Poly, ByRef q AS Poly)
'Division f = g * q + r; f:= r, q:= f / g
DECLARE SUB Multp (ByRef f AS Poly, ByRef g AS Poly)
'f:= f * g
DECLARE SUB Squp (ByRef f AS Poly)
'f:= f ^ 2
DECLARE SUB Subtp (ByRef f AS Poly, ByRef g AS Poly)
'f:= f - g
DECLARE SUB Shlp (ByRef f AS Poly, ByVal k AS SHORT)
'f:= f * X^ k
DECLARE SUB Shrp (ByRef f AS Poly, ByVal k AS SHORT)
'f:= f / X^ k
'
' ***************************************************************************************
'                               Modulo-polynomial functions
' ***************************************************************************************
DECLARE SUB Invp (ByRef f AS Poly, ByRef g AS Poly, ByRef d AS Poly)
'f:= f^ -1 Mod g, g:= g / gcd(f, g), d:= gcd(f, g)
DECLARE SUB Modmltp (ByRef f AS Poly, ByRef g AS Poly, ByRef h AS Poly)
'Polynomial f:= f * g Mod h
DECLARE SUB Modpwrp (ByRef f AS Poly, ByRef k AS Bigi, ByRef g AS Poly)
'f:= f^ bigint(k) Mod g, set g = 0 to skip reduction
'
' ***************************************************************************************
'                                        Checks
' ***************************************************************************************
DECLARE FUNCTION Ispc (ByRef f AS Poly, ByVal c AS SHORT) AS SHORT
'Is f = constant c ?
DECLARE FUNCTION Ispm (ByRef f AS Poly, ByVal c AS SHORT) AS SHORT
'Is f = monomial X + c ?
DECLARE FUNCTION Isirrd (ByRef f AS Poly) AS SHORT
'Is f irreducible ?
'
' ***************************************************************************************
'                                   Assorted functions
' ***************************************************************************************
DECLARE SUB Bezoup (ByRef f AS Poly, ByRef g AS Poly, ByRef d AS Poly)
'Solution of the Diophantine equation fa + gb = gcd(f, g).
'Returns a in f, b in g, and gcd(f, g) in d
DECLARE SUB Deriv (ByRef f AS Poly, ByRef g AS Poly)
'g:= derivative f'
DECLARE FUNCTION Disc (ByRef f AS Poly) AS SHORT
'Return discriminant(f)
DECLARE FUNCTION Eval (ByRef f AS Poly, ByVal c AS LONG) AS SHORT
'Evaluate f(c) with Horner's rule
DECLARE SUB Gcdp (ByRef f AS Poly, ByRef g AS Poly, ByRef d AS Poly)
'd:= polynomial gcd(f, g)
DECLARE SUB Monic (ByRef f AS Poly)
'Make monic(f)
DECLARE FUNCTION Psdiv (ByRef f AS Poly, ByRef g AS Poly, ByRef q AS Poly) AS SHORT
'Pseudo-division, returns the scalar L(g)^(f.n - g.n + 1) * f = g * q + r
DECLARE SUB Recip (ByRef f AS Poly)
'f:= reciprocal X^f.n * f(1/ X)
DECLARE FUNCTION Result (ByRef f AS Poly, ByRef g AS Poly) AS SHORT
'Return resultant(f, g)
DECLARE SUB Subst (ByRef f AS Poly, ByRef g AS Poly)
'Horner substitution f:= f(g(X))
'
' ***************************************************************************************
'                              Modular arithmetic functions
' ***************************************************************************************
DECLARE FUNCTION Modd (ByVal c AS LONG) AS SHORT
'Return positive(c) mod global modulus
DECLARE FUNCTION Balc (ByVal c AS LONG) AS SHORT
'Return least absolute value(c) mod global modulus
DECLARE FUNCTION Inv (ByVal c AS LONG) AS SHORT
'Return 1/ c mod global modulus
DECLARE FUNCTION Modpwr (ByVal a AS LONG, ByVal k AS SHORT) AS SHORT
'Return a^ k mod global modulus
'
' ***************************************************************************************
'                             Building big integer exponents
' ***************************************************************************************
DECLARE SUB Addi (ByRef a AS Bigi, ByVal c AS SHORT)
'bigint a:= a + c
DECLARE FUNCTION Divi (ByRef a AS Bigi, ByVal c AS SHORT) AS SHORT
'a:= a / c, returns remainder
DECLARE SUB Muli (ByRef a AS Bigi, ByVal c AS SHORT)
'a:= a * c
DECLARE SUB Pwri (ByRef p AS Bigi, ByVal a AS SHORT, ByVal k AS SHORT)
'p:= a ^ k
DECLARE SUB Squi (ByRef a AS Bigi)
'a:= a ^ 2
'
' ***************************************************************************************
'                                  Internal functions
' ***************************************************************************************
DECLARE SUB Adjp (ByRef f AS Poly, ByVal n AS SHORT)
'Adjust degree n of polynomial f
DECLARE SUB Lftj (ByRef a AS Bigi, ByVal k AS SHORT)
'Left-justify bigint a, starting at array element k
DECLARE SUB Mulc (ByRef f AS Poly, ByVal c AS SHORT)
'f:= f * c mod global modulus
DECLARE SUB Negp (ByRef f AS Poly)
'f:= -f mod global modulus
DECLARE SUB PosLc (ByRef f AS Poly)
'Make positive leading coefficient
DECLARE FUNCTION Tail (ByRef f AS Poly, ByRef g AS Poly) AS SHORT
'Zeroed poly tail for Addp and Subtp
DECLARE SUB Triald (Pf() AS LONG, ByRef fx AS SHORT, ByVal n AS LONG)
'Return primefactors of n in Pf(fx, k)
DECLARE SUB Work (ByRef f AS STRING)
'Set f to the working directory in ENVIRON("LARGEINT"),
'the stringbuffer must be large enough to hold the path
'
' ***************************************************************************************
#IFNDEF __LIB
#INCLIB "polymodp"
' ***************************************************************************************
'28 largest primes < 2^ 15 for CRT-transform:
' ***************************************************************************************
DATA 32749,32719,32717,32713,32707,32693,32687
DATA 32653,32647,32633,32621,32611,32609,32603
DATA 32587,32579,32573,32569,32563,32561,32537
DATA 32533,32531,32507,32503,32497,32491,32479
'
' ***************************************************************************************
#ENDIF

All this functionality in only 20 Kb

Applications survey

using lib PolyModp.bas

FiboPoly.bas

The first 50 Fibonacci polynomials with discriminants and values f(1), all modulo p.

ChebyPol.bas

The first 19 Chebyshev polynomials T_n(x) = cos(n * arccos(x)), with discriminants and values t(1), all modulo p.

HermiPol.bas

The first 99 Hermite polynomials modulo p, with a final differential equation check.

CycloPol.bas

Cyclotomic polynomials: minimal poly's for primitive n-th roots of unity, with discriminants and values c(2) modulo p.

BezouPol.bas

Bezout's identity ua + vb = gcd(u,v) for polynomials modulo p.

TanhPoly.bas

Coefficients for the Taylor series of tanh(x) with corresponding Bernoulli numbers modulo p.

Poly_SNF.bas

Minimal polynomial of an m × n integral matrix with Smith normal form.

PolyDisc.bas

Discriminant of an integer poly f via resultant (f, f') modulo p.

The above eight modules need transformation module CRTtrans.bas
to lift the results from the intersection of 28 small equivalence classes:

CRTtrans.bas

Number theoretic transform with the Chinese remainder theorem, Rational reconstruction with Wang's algorithm.
This module uses my Basic large integer library.

MpolRoot.bas

Roots of polynomials modulo a prime.

MpolFact.bas

Factorization of polynomials modulo a prime.

PolyFact.bas

Much like MpolFact.bas, now with routines for combining modular factors into true factors over ℤ.

Hensel_p.bas

Polynomial Hensel lifting, toy version for small coefficients.

ElgamalG.bas

Cryptography: polynomial Elgamal key generator.
Private key (mp, k), public key (mp, X^k), with irreducible poly mp and random exponent k.

ElgamalE.bas

Polynomial Elgamal enciphering w/key (mp, X^k).

ElgamalD.bas

Polynomial Elgamal deciphering w/key (mp, k).

using lib PolyGF2n.bas

R-S_Enco.bas

Encoder for GF(2^8) Reed-Solomon error correction.

R-S_Deco.bas

Euclidean decoder for Reed-Solomon error correction.

CRC_byte.bas

Cyclic redundancy check with true GF(2^8) polynomial division,
allowing for all multi-byte width generators and optional register initialization.

LFSRbyte.bas

Galois form linear feedback shift register, allowing for all multi-byte width generators.

GF2nRoot.bas

Find a primitive polynomial of degree n over GF(2) to define extended field GF(2^n) for coefficient arithmetic.

GF2nFact.bas

An adaptation of the above MpolFact.bas for polynomials over GF(2^n).

IrredPol.bas

Finding irreducible polynomials over GF(2^n).

PrimiPol.bas

Finding primitive polynomials over GF(2^n).

MinimPol.bas

The minimal polynomial of a root over GF(2^n).

Plus GF(2^8) versions of the above three Elgamal cryptography modules.

using lib RealPoly.bas

CPolFact.bas

Polynomial factorization over ℂ or root-finding.

ZPolFact.bas

Polynomial factorization over ℤ by finding minimal polynomials with PSLQ.

p-Adic0s.bas

p-Adic roots of an integral polynomial with Hensel's lemma.

CMiniPol.bas

The minimal polynomial of an algebraic number with complex PSLQ. Includes a basic recursive expression parser.

Resultnt.bas

Resultant of bivariate polynomials f(x, y) and g(y): a tool for computing minimal polynomials.

EigenSys.bas

Characteristic polynomial f(x) = det(A - xI) of m × n integral matrix A with eigenvalues and eigenvectors over ℂ.

References: