Re: polynomials over finite fields

*To*: mathgroup at smc.vnet.net*Subject*: [mg31356] Re: [mg31339] polynomials over finite fields*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Tue, 30 Oct 2001 04:35:40 -0500 (EST)*References*: <200110290723.CAA15086@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

theodore hwa wrote: > > How does one do polynomial arithmetic over finite fields using > Mathematica efficiently? After loading the Algebra`FiniteFields package, I > constructed a few polynomials with finite field coefficients (over the > field of 25 elements), and then tried both Expand and Distribute to > multiply it out, but it was extremely slow. I was only multiplying > something like a 5 term polynomial by a 4 term polynomial, and it was > taking forever. This would not happen with normal polynomials in Mathematica. > > Ted One thing you might try is to define such fields by explicitly computing an appropriate irreducible polynomila to define the extension to a given prime field Z_p (I'm using a standard math notation which is decidedly NOT Mathematica notation). The multiplication can be done by Expand followed by PolynomialMod[product,{irred,p}]. Actually I think the latter will do the whole thing directly including the Expand but I have not checked this for a fact. You might instead find a primitive element of the cyclic group GF[p,n]-{0}, express everything as a power thereof, and use Expand thereon. Now multiplication becomes trivial but addition requires a table. Alot of the details for how to do this in Mathematica may be found from the URL below. http://library.wolfram.com/mathgroup/archive/1998/Nov/msg00195.html One thing not shown is the construction of the Zech logarithms (the addition table when using the primitive element cyclic group representation). That one is, as they say, left as an exercise for the reader. Daniel Lichtblau Wolfram Research

**References**:**polynomials over finite fields***From:*theodore hwa <hwatheod@Stanford.EDU>