From: rodney@math.toronto.edu (Peter Rodney)
Subject: finite field arithmetic in Mathematica
Organization: Department of Mathematics, University of Toronto
Date: Fri, 10 Apr 92 18:48:13 GMT

I've had a few requests for this since I posted a few days ago 
requesting it myself. I am therefore posting what I have found.
This is a finite field arithmetic package for Mathematica
available from the Mathematica repository. Thanks to Mark Hasse
for letting me know about it. If you would like to check out the 
repository yourself send an Email letter containing the line
'help intro' to MathSource@wri.com.
-peter
rodney@math.toronto.edu



From wri.com!ms-admin Thu Apr  9 12:17:06 GMT 1992
Received: from fiji.wri.com by dragonfly.wri.com with SMTP id AA20467
  (5.65c/IDA-1.4.4 for <rodney@math.toronto.edu>); Thu, 9 Apr 1992 12:17:15 -0500
Return-Path: <ms-admin@wri.com>
Date: Thu, 9 Apr 92 12:17:06 GMT-0600
Message-Id: <9204091817.AA02552@fiji.wri.com>
From: "MathSource" <ms-admin@wri.com>
To: rodney@math.toronto.edu
Subject: MathSource Subitem 0200-350-0011 [1 of 1]
Status: R

This is an automatic response from the MathSource server at mathsource@wri.com.

The MathSource system is currently being tested and undergoing
revisions.  The next software update is scheduled for Monday,
April 13.  Please report all problems and suggestions to
ms-admin@wri.com.

A complete listing of all files in MathSource can be obtained by
issuing the following commands

	maxlong 10000
	find *

You cannot blind-reply to mail responses from MathSource.  This is
to prevent infinte loops within the MathSource server due to returned
mail.  If you reply to this message, the mail will go to a human
operator and NOT to the MathSource server.

Sent for request of  Thu, 9 Apr 92 13:18:03 EDT
Part 1 of 1
--------------------------------
(* $Id: FiniteFields.m,v 1.2 1991/08/14 23:54:11 rory Exp $ *)

(**FiniteFields.m  **)
 
(* Program by Ilan Vardi, December, 1989.
 
   Copyright Wolfram Research, Inc.
   P.O. Box 6059, Champaign, IL 61820, 217-398-0700   *)
 
(*
   A finite field of p^n elements can be constructed as polynomials
   f[y] with coefficients (mod p), and the polynomials themselves
   are taken (mod Generator[y]), which is an irreducible polynomial
   of degree n (mod p). Multiplication and addition are just as usual
   but taken (mod p, Generator[y]).
 
   The only hard part is taking inverses (i.e., 1/f[y]), which ends up
   being equivalent to computing the extended GCD (mod p). In other words,
   given f[y], Generator[y], find a[y], b[y], such that
 
  a[y] f[y] + b[y] Generator[y] = GCD[Generator[y], f[y], Modulus-> p]
 
   If GCD = 1, then a[y] is the required inverse. This is the only
   nontrivial part. The rest of the code is just a routine set up of
   finite field rules.
 
   I set up a data structure FiniteField[f, y, {p, n}] which represents finite
   field elements. Once the rules of addition, multiplication,
   and division have been generalized to this data structure, other
   functions will operate on them like field elements. Thus
   PolynomialQuotient[f, g, x] will give the correct answer when
   applied to polynomials f, g, in x with coeffients FiniteField[f, y, {p, n}].
 
*)
 
(* This is the irreducible polynomial (mod p) that generates
   the finite field of p^n elements  *)
 
Generator[y_, p_, n_] := Generator[y, p, n] =
   First[Select[First /@
   FactorList[Cyclotomic[p^n-1,y], Modulus -> p],
   Exponent[#, y] == n&]]
 
(* An element in the finite field of p^n elements is a polynomial
   (mod Generator) and (mod p)                                       *)
 
FiniteField[f_, y_, {p_, n_}] :=
          FiniteField[Mod[PolynomialRemainder[Mod[f, p],
                   Generator[y, p, n], y], p],y, {p, n}] /;
     Exponent[f, y] >= n || Select[CoefficientList[f, y], # >= p&] != {}
 
(* The field laws for elements in a finite field. The only hard
   part is defining inverses, which is equivalent to finding the
   ExtendedGCD for polynomials (mod p)                           *)
 
FiniteField /: FiniteField[f_, y_, {p_, n_}] + FiniteField[g_, y_, {p_, n_}] :=
   FiniteField[Mod[f + g, p], y, {p, n}]
 
FiniteField /: FiniteField[f_, y, {p_, n_}] + m_Integer :=
   FiniteField[Mod[f + m,p], y, {p, n}]
 
FiniteField /: FiniteField[f_, y_, {p_, n_}] * FiniteField[g_, y_, {p_, n_}] :=
   FiniteField[Mod[f * g, p] , y, {p, n}]
 
FiniteField /: FiniteField[f_, y_, {p_, n_}] * m_Integer :=
   FiniteField[Mod[f * m, p], y, {p, n}]
 
FiniteField /: FiniteField[0, y_, {p_, n_}] * x_ :=
   FiniteField[0, y, {p, n}]
 
(*    Taking 1/x, the only hard part    *)
 
FiniteField /: Power[FiniteField[f_, y_, {p_, n_}], -1] :=
   FiniteField[Last[FFExtendedGCD[Generator[y, p, n], f, y, p]], y, {p, n}]  /;
   PolynomialGCD[Generator[y, p, n], f, Modulus -> p] == 1
 
FiniteField /: FiniteField[f_, y_, {p_, n_}]^k_ :=
   FiniteField[Mod[f^k, p], y, {p, n}]    /;  k >= 0
 
 
(*   **********************************************************
 
     Computing ExtendedGCD (mod p). This is a little awkward
     since PolynomialRemainder[f, g, x], and PolynomialQuotient[f, g, x]
     don't have the option Modulus -> p, so if g is not monic
     you have to compute inverses (mod p) to make them monic.
     For example,
 
PolynomialRemainder[233 x^5 + 641 x^3 + 5 x + 17, 101 x^3 + 54 x^2 +67, x]
 
   =>  -(466108906/1030301) + (893999 x)/10201 - (549034337 x^2 )/1030301
 
    ************************************************************    *)
 
 
FFExtendedGCD[f_,g_, y_, p_] :=
    Reverse[FFExtendedGCD[g, f, y, p]] /;
            Exponent[Mod[f, p], y] < Exponent[Mod[g, p], y]
 
FFExtendedGCD[f_, g_, y_, p_Integer] :=
    {1, 0} /;  Exponent[Mod[g, p], y] == -Infinity
 
FFExtendedGCD[f_, g_, y_, p_] :=
     Block[{fp = Mod[f, p], gp = Mod[g, p],
            extf = {1, 0}, extg = {0, 1},
            q, r = y, leading},
       If[Exponent[gp, y] == 0, {0, PowerMod[gp, -1, p]},
           While[Exponent[r, y] > 0,
                 leading = Coefficient[gp, y, Exponent[gp, y]];
                  monic = PowerMod[leading, -1, p];
            q = PolynomialQuotient[Mod[monic fp, p], Mod[monic gp, p], y];
            r = leading *
                   PolynomialRemainder[Mod[monic fp, p], Mod[monic gp, p], y];
           {fp, gp, extf, extg}  = Mod[#, p] & /@
                                   {gp, r, extg, extf - q extg};
                 ];
             If[r == 0, Null, PowerMod[r, -1, p] extg]]]
 

--------------------------------
End of part 1 of 1

Newsgroups: sci.math.symbolic