Finite field arithmetic in BASIC

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   : 01-15-2008
'Code   : FreeBasic 0.20.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 INTEGER '                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 INTEGER)
'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 INTEGER) 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 INTEGER) AS SHORT
'Return positive(c) mod global modulus
DECLARE FUNCTION Balc (ByVal c AS INTEGER) AS SHORT
'Return least absolute value(c) mod global modulus
DECLARE FUNCTION Inv (ByVal c AS INTEGER) AS SHORT
'Return 1/ c mod global modulus
DECLARE FUNCTION Modpwr (ByVal a AS INTEGER, 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 INTEGER, ByRef fx AS SHORT, ByVal n AS INTEGER)
'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 Tn(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:

Back to the Download page

SourceForge.net logo