Faster powering over GF(p)

[Robert Gerbicz]

From the benchmark page:
sage: R.<x,y,z> = PolynomialRing(GF(13))
sage: time _ = expand((x+y+z+1)**100)
CPU times: user 0.07 s,...

Since (a+b)^p=a^p+b^p over a finite field with charachteristic p and
a^p+b^p has got only two terms this gives the idea to expand the
exponent of the polynom in base p and use this in the powering:

# still a naive code, because sage is not use that the computation of
(a+b+c+..)^p is easy
def fastpower(f,e,p):
if e<0:
return fastpower(f,-e,p)**-1
if e<p:
return f**e
return f**(e%p)*fastpower(f**p,e//p,p)

By this code the above task:
time _ = expand(fastpower(x+y+z+1,100,13))
takes only 0.01 sec. (the original code takes 0.14 sec. on my
computer).

For exponent=500:
time _ = expand(fastpower(x+y+z+1,500,13))
takes only 0.12 sec. (the original code takes 13.79 sec.), means an
about 115 times faster code.

[John Cremona]

There is a trac ticket about this, quite an old one. I don't have
time to search for it now, but it would be worth checking out.

John

[Simon King]

Hi!

On 10 Okt., 11:32, John Cremona <john.crem...@gmail.com> wrote:
> There  is a trac ticket about this, quite an old one.  I don't have
> time to search for it now, but it would be worth checking out.

I do remember that there has been a thread, likely on sage-devel, and
perhaps also a ticket, but I have not been able to find it.

Since we are likely to talk about libSingular polynomials here, I
think it would be the best solution if the Singular team would
consider to add a special case for finite fields. I don't know why
they don't.

Cheers,
Simon