Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2001
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: diagonalization
  • Next by Date: Zero does not equal Zero
  • Previous by thread: polynomials over finite fields
  • Next by thread: Simplifying expressions, and Alpha