"letsimp" honors "modulus" only partially?

I am surprised that letsimp is so slow.  Glad to hear that the 'gf' package
solves your problem.

But if you want to do the original calculation faster, you can code up the
reduction (iterative ratsubst) very simply yourself:

    iratsubst(a,b,c,modulus):=
        (a:rat(a),b:rat(b),c:rat(c),
         while(c # (c:ratsubst(a,b,c))) do 1,
         c);

On my installation (Maxima 5.25.1 GCL 2.6.8, Windows Vista, Intel 8400 3GHz)

     iratsubst(x+2,x^3,x^3000,1009) => -426*x^2-479*x+97

takes under 1/2 second.  Unfortunately, it runs into some limitations with
ratsubst:

   ratsubst(x+2,x^3,x^3030),modulus:1009;
   Maxima encountered a Lisp error:
   Error in PROGN [or a callee]: Bind stack overflow.

This is one of those rare cases where requesting a larger stack may
actually be the correct solution -- but I'm afraid I can't help with that.

           -s


On Mon, Nov 21, 2011 at 11:07, Lutz Euler <lutz.euler at freenet.de> wrote:

> Hi Stavros and Oliver,
>
> thanks for the fast answers to my mail. Both are very useful.
>
> I wrote:
>
> > I am trying to calculate x^31 in the finite field with 125 elements,
> > (Z/5Z)[x]/(x^3 - x - 2). I don't know the canonical way to deal with
> > fields of this kind in Maxima, but I found "letsimp" and the variable
> > "modulus" and that nearly works.
>
> Stavros wrote:
>
> > I believe the issue here is that 'modulus' is only applied to
> > expressions in canonical rational form (CRE) -- expressions
> > created using 'rat'.
>
> Yes, this explains why letsimp only partially reduces the numbers
> with respect to "modulus". I have read up more on "rat" and CRE in
> the documentation now, so thank you for the pointer.
>
> Now, the letsimp-based method very easily gets way too slow;
> while it can do the 31th power, with for example the 50th it didn't
> return an answer after several minutes.
>
> So thanks to Oliver for pointing me to "gf". You wrote:
>
> > there is the package "gf" which would do all of this ---
> > unfortunately it is broken, and only some of the functions work.
> >
> > The package-functions are also very slow.
>
> I have now tried "gf" very successfully. It seems way sufficient for
> my needs, for example exponentiation is instantaneous and it even
> can calculate a logarithm in GF(p^3) with p of the order of 2^32
> within a minute or so (with p chosen such that the prime factors
> of p^3 - 1 are 2, (p - 1)/2 and p^2 + p + 1).
>
> My interest is mostly in interactively experimenting with some simple
> calculations to get a better understanding of the structure of the
> multiplicative group in these fields, so this amount of performance
> is sufficient for me.
>
> Thanks again! Yours,
>
> Lutz
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>