Re: Strange behaviour of FiniteFields?
- To: mathgroup at smc.vnet.net
- Subject: [mg25328] Re: [mg25287] Strange behaviour of FiniteFields?
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Sat, 23 Sep 2000 03:35:51 -0400 (EDT)
- References: <200009190745.DAA29313@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Wil Kortsmit wrote:
>
> Hello,
>
> Working with the FiniteFields package we have met some strange behaviour
> when we tried to compute the product of 2 polynomials a and b with
> coefficients in the field f32:
>
> <<Algebra`FiniteFields`
> f32=GF[2,{1,0,1,0,0,1}];
>
> The 2 polynomials a and b
>
> a[x]=x^2f32[{0,0,1,1,1}]+x*f32[{1,0,0,0,0}]+f32[{1,0,1,1,1,1}];
> b[x]=x^5f32[{0,1,1,1,1}]+x^4f32[{0,0,0,1,1}]+x^3f32[{0,0,1,1,0}]+
> x^2f32[{1,0,0,0}]+x*f32[{0,1,0,1,1}]+f32[{1,0,0,0,0}];
>
> We needed to abort the following computation because we ran out of
> patience:
>
> Collect[a[x]b[x],x]
>
> Preventing the early intervention of the FiniteFields package:
>
> Collect[a[x]b[x]/.GF->GF$,x]/.GF$->GF
>
> gave us the result that we expected immediately.
> Looking in the Mathgroup archives we didn't find a clue.
> Is this a bug in the FiniteFields package or are are we doing something
> wrong?
> Thanks for any help.
>
> Wil Kortsmit
The package suffers from problems related to use of UpValues. It appears
that there are interactions with pattern matching in internal code that
send some computations off to Never-Never Land. Offhand I would guess
that your best bet is to work around this pretty much in the manner you
demonstrate. I believe we should redesign and rewrite this package, and
recently made a suggestion in-house to that effect.
Here is another approach that may be helpful. Rather than load the
FiniteFields package, set up your own. If you wish to preserve the sort
of notation from the package, one might proceed as follows.
In[6]:= irred = 1+a^2+a^5;
In[7]:= f32[coeffs_List] := coeffs . a^Range[0,4]
In[8]:= a[x] = x^2*f32[{0,0,1,1,1}] + x*f32[{1,0,0,0,0}] +
f32[{1,0,1,1,1}];
In[9]:= b[x] = x^5*f32[{0,1,1,1,1}] + x^4*f32[{0,0,0,1,1}] +
x^3*f32[{0,0,1,1,0}] +
x^2*f32[{1,0,0,0,0}] + x*f32[{0,1,0,1,1}] + f32[{1,0,0,0,0}];
(I changed a couple of the field elements because they had list of
length 6 and 4 respectively; in the former case this probably gives a
different field element from what you had in mind.)
To express the product in powers of x, one now uses Collect directly but
provides a "canonicalizer" as the optional third argument.
In[10]:= prod = Collect[a[x]*b[x], x, PolynomialMod[#,{2,irred}]&]
2 3 4 2 3 3 4 2
Out[10]= 1 + a + a + a + (a + a + a ) x + (1 + a + a + a ) x +
2 3 4 3 3 5 2 4 6 3 7
> (a + a + a ) x + a x + (a + a + a ) x + (a + a ) x
Daniel Lichtblau
Wolfram Research
- References:
- Strange behaviour of FiniteFields?
- From: Wil Kortsmit <rcwil@win.tue.nl>
- Strange behaviour of FiniteFields?