The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Faster powering over GF(p)
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 3 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Oct 9 2010, 6:51 pm
From: Robert Gerbicz <robert.gerb...@gmail.com>
Date: Sat, 9 Oct 2010 15:51:21 -0700 (PDT)
Local: Sat, Oct 9 2010 6:51 pm
Subject: Faster powering over GF(p)
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

To post a message you must first join this group.
You do not have the permission required to post.
More options Oct 10 2010, 5:32 am
From: John Cremona <john.crem...@gmail.com>
Date: Sun, 10 Oct 2010 10:32:25 +0100
Local: Sun, Oct 10 2010 5:32 am
Subject: Re: [sage-algebra] Faster powering over GF(p)
time to search for it now, but it would be worth checking out.

John

On Sat, Oct 9, 2010 at 11:51 PM, Robert Gerbicz

To post a message you must first join this group.
You do not have the permission required to post.
More options Oct 10 2010, 1:08 pm
From: Simon King <simon.k...@nuigalway.ie>
Date: Sun, 10 Oct 2010 10:08:37 -0700 (PDT)
Local: Sun, Oct 10 2010 1:08 pm
Subject: Re: Faster powering over GF(p)
Hi!

On 10 Okt., 11:32, John Cremona <john.crem...@gmail.com> wrote:

> 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