Re: efficiency of modular exponentiation

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

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.

Cheers,
Bill.

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
allocatemem(100000000)
Q=2^16
\p2000
pola=(a^16+a^5+a^3+a+1)*Mod(1,2);
a = ffgen(pola, 'a);
Z= sum(i=0,254,u^i*subst(Pol(binary(floor(Pi*Q^(i+1))%Q)),'x,a));
polu=u^255+ (a^14 + a^12 + a^7 + a^6 + a^5 + a^4 + a);
g=Mod(u+a,polu);
lg=5935377918714230432230999933717750972257258069856089974977949660023882324802076896698410404982590206958649631628772672466127669634274818596358582683302117352838165909188471579953420256387758687914285280177954658284572333669860436891005920917402903089607764477430547370770112475381244907965544496884807875672058922056500650363713396354721008645927686282457785486271699937105302489522475021983391024140847168793050589732859677058978247175646259738344232835001918988149268862458058654691394256198576710650030125544077411432323340939433051485194567571240185673981732045983714973267283534300647601226252568098892440462401965111622976003259591077704702584200763046171986480349330806899873312846204834058399352574005416231688261510545134741182277970358473883943958563579015179820120979292270637497907072612180871069400619450857723011268017454116823535827228473296516703273009238893345386444533871542383504242463001681961734268277378540067885920080290584936097716155329313777328195435585629703275367750105825453097378643622824901407930221204813818805961136841682239404338275246672278987523193876833029445938199819122011285813404240449718569721922907241151390900428524224234201221755939491010573105885453826465599986918927823875647571538;
if (g^lg == Z, print("Verification OK"), print("Verification FAILED"))