Re: efficiency of modular exponentiation

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Bill Allombert [2013-03-27 17:42]:
> On Wed, Mar 27, 2013 at 11:08:41AM -0400, Max Alekseyev wrote:
> > Just out of curiosity: why the magma script is much faster the gp script?
> > (both scripts are quoted below)
> 
> Try this GP script instead (From Karim) that use ffgen instead of POLMOD of
> INTMOD.

Here is another one, relying on libpari and install()
[ in 2.6.*, 6 times faster than the script Bill posted; about 60 times
faster than the original script ]

Cheers,

    K.B.

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
install(FpXQXQ_pow, GGGGG);
install(FpXQX_red, GGG);

allocatemem(100000000) 
Q=2^16 
\p2000 
pola=a^16+a^5+a^3+a+1;
Z = sum(i=0,254,x^i*Pol(binary(floor(Pi*Q^(i+1))%Q), 'a)); 
polx = x^255+ (a^14 + a^12 + a^7 + a^6 + a^5 + a^4 + a); 
lg=5935377918714230432230999933717750972257258069856089974977949660023882324802076896698410404982590206958649631628772672466127669634274818596358582683302117352838165909188471579953420256387758687914285280177954658284572333669860436891005920917402903089607764477430547370770112475381244907965544496884807875672058922056500650363713396354721008645927686282457785486271699937105302489522475021983391024140847168793050589732859677058978247175646259738344232835001918988149268862458058654691394256198576710650030125544077411432323340939433051485194567571240185673981732045983714973267283534300647601226252568098892440462401965111622976003259591077704702584200763046171986480349330806899873312846204834058399352574005416231688261510545134741182277970358473883943958563579015179820120979292270637497907072612180871069400619450857723011268017454116823535827228473296516703273009238893345386444533871542383504242463001681961734268277378540067885920080290584936097716155329313777328195435585629703275367750105825453097378643622824901407930221204813818805961136841682239404338275246672278987523193876833029445938199819122011285813404240449718569721922907241151390900428524224234201221755939491010573105885453826465599986918927823875647571538;
G = FpXQXQ_pow(x+a, lg, polx, pola, 2);
check = FpXQX_red(G-Z, pola, 2);
if (check == 0, print("Verification OK"), print("Verification FAILED")) 
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`