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>
- polynomials over finite fields