| William Hart on Wed, 27 Mar 2013 16:20:56 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| Re: efficiency of modular exponentiation |
I believe Magma has special code for working over GF2.
Bill.
--- On Thu, 3/28/13, Max Alekseyev <maxale@gmail.com> wrote:
> From: Max Alekseyev <maxale@gmail.com>
> Subject: efficiency of modular exponentiation
> To: pari-users@pari.math.u-bordeaux.fr
> Date: Thursday, March 28, 2013, 2:08 AM
> Just out of curiosity: why the magma
> script is much faster the gp script?
> (both scripts are quoted below)
>
> Regards,
> Max
>
> ---------- Forwarded message ----------
> From: Antoine Joux <Antoine.Joux@cryptoexperts.com>
> Date: Sat, Mar 23, 2013 at 10:30 AM
> Subject: Re: Discrete Logarithms in GF(2^4080)
> To: NMBRTHRY@listserv.nodak.edu
>
>
> Dear All,
>
> In order to ease verification, here is a magma script which
> is much
> faster than the initial gp script.
>
> R:=RealField(1500);
> pival:=Pi(R);
> gf2:=GF(2);
> gf2pol<x>:=PolynomialRing(gf2);
> gf<a>:=ext<gf2|x^16+x^5+x^3+x+1>;
> gfpol<X>:=PolynomialRing(gf);
> A:=a+a^256;
> gfext<u>:=ext<gf|X^255+A>;
> g:=u+a;
> Z:=&+[(Floor(pival*2^(val+1)) mod 2)*u^(val div
> 16)*a^(15-(val mod
> 16)): val in [0..4079]];
>
lg:=59353779187142304322309999337177509722572580698560899749779496600238823248020768966984104049825902069586496316287726724661276696342748185963585826833021173528381659091884715799534202563877586879142852801779546582845723336698604368910059209174029030896077644774305473707701124753812449079655444968848078756720589220565006503637133963547210086459276862824577854862716999371053024895224750219833910241408471687930505897328596770589782471756462597383442328350019189881492688624580586546913942561985767106500301255440774114323233409394330514851945675712401856739817320459837149732672835343006476012262525680988924404624019651116229760032595910777047025842007630461719864803493308068998733128462048340583993525740054162316882615105451347411822779703584738839439585635790151798201209792922706374979070726121808710694006194508577230112680174541168235358272284732965167032730092388933453864445338715423835042424630016819617342682773785400678859200802905849360977161553293
13777328195435585629703275367750105825453097378643622824901407930221204813818805961136841682239404338275246672278987523193876833029445938199819122011285813404240449718569721922907241151390900428524224234201221755939491010573105885453826465599986918927823875647571538;
> if Z eq (g^lg) then
> print "Verification OK";
> else
> print "Verification Failed";
> end if;
>
>
> All the best,
> Antoine Joux
>
>
> Le 23 mars 2013 à 01:01, Antoine Joux <Antoine.Joux@m4x.org>
> a écrit :
>
> > Dear Number Theorists,
> >
> > We are pleased to announce a new record for the
> computation of
> > discrete logarithms in finite fields. We were able to
> compute discrete
> > logarithms in GF(2^4080) using about 14100 CPU.hours.
> This
> > computation was performed using the same index calculus
> algorithm as
> > in our recent computation [Jo13]. A draft describing
> the algorithm is
> > available as [Jo13a].
> >
> > As far as we know, the previous discrete logarithm
> record in
> > characteristic 2 is GF(2^1971), using a L(1/3)
> algorithm
> > (see [Go+13a,Go+13b]).
> >
> > The main features of our new index calculus algorithm
> are:
> >
> > - An asymptotic complexity L(1/4+o(1))
> >
> > - A small smoothness basis of size q^4 for
> discrete logs in a
> > field GF(q^(2k)) with k close to q.
> Indeed, this smoothness basis
> > contains polynomials of degree 1 and 2
> with coefficients in
> > GF(q^2). As a consequence, the computation
> of the logarithms of
> > smoothness basis elements takes polynomial
> time.
> >
> > - A new descent algorithm that together
> with classical descent
> > techniques allows to express arbitrary
> elements in the finite
> > field in terms of smoothness basis
> elements. This new descent step
> > is essential to reach the announced
> complexity.
> >
> >
> > We first defined GF(2^16), from the irreducible
> polynomial
> > x^16+x^5+x^3+x+1. We denote by 'a' a root of this
> polynomial and use the
> > polynomial basis 1, a, ..., a^15 to represent elements
> in GF(2^16).
> >
> > We then defined GF(2^4080) using the following Kummer
> extension
> >
> > GF((2^16)^255) =
> GF(2^16)[u]/(u^255+A),
> >
> > where A is the Trace of a [to GF(2^8)], i.e:
> > A=a^256+a=a^14 + a^12 + a^7 + a^6 + a^5 + a^4 + a.
> >
> > We choose as basis for the discrete logarithms, the
> value : g = u+a.
> >
> > As usual, we set to ourselves the challenge of
> computing the logarithm of:
> >
> > Z=
> sum(i=0,254,u^i*Pol(binary(floor(Pi*Q^(i+1))%Q),a)) [in
> Pari-gp syntax, with Q=2^16]
> >
> > The cardinality of the multiplicative group of
> GF(2^4080) is:
> >
> > 2^4080-1=
> >
> 3^2*5^2*7*11*13*17^2*31*41*61*97*103*137*151*241*257*307*331*409*673*953*1021*1321*
> >
> 1361*2143*2857*3061*4421*6529*8161*11119*12241*13669*26317*43691*51001*61681*
> >
> 106591*131071*354689*383521*550801*949111*12717361*15571321*23650061*40932193*
> >
> 394783681*1326700741*2949879781*4278255361*4562284561*46908728641*
> >
> 611787251461*1392971637361*1467129352609*2368179743873*2879347902817*15455023589221*
> > 33910825580641 *
> 116772720677761 * 418562986357561 * 737539985835313 *
> > 171664686650370481 *
> 4967178060528306401 * 7226904352843746841 *
> > 9520972806333758431 *
> 26831423036065352611 * 51366149455494753931 *
> > 373200722470799764577 *
> 1230412270786066204321 * 8088220746627020943841 *
> > 10146032011084172688350401 *
> > 5702451577639775545838643151 *
> 4251553088834471719044481725601 *
> >
> 630894905395143528221826310327361 *
> 18741457027056199460701768016571521 *
> >
> 420245688628846194691190674873072272865640768049748318922486401
> *
> > P78 * P116 * C295
> >
> > where:
> >
> P78=116244395157193581337282640791798084114394917399572436767868837818708235649281
> >
> >
> P116=59759045572704532151734514229676903701763064698110618010245423428627221235639899045664816790870237783305610352947361
> >
> >
> C295=1533490284616846723598415409259297911652711222168775547792306046025942905067111993457984065168194835553976875731082408417656840935335955173202390542791678493470066047287643716215585615327618503502688057052265147924415358240017501698179552850131324250482005642180027027923716821703262527243660161
> >
> > Since P116 has 385 bits, computing discrete logarithms
> in GF(2^4080) is
> > clearly out of reach of generic algorithms.
> >
> >
> > As usual, the computation was done in three steps:
> > - the generation of multiplicative relations,
> > - the linear algebra,
> > - the final computation of individual
> logarithms.
> >
> > As mentioned above, the factor basis that has been used
> contains all
> > irreducible monic polynomials of degree 1 and 2 in u
> (with arbitrary
> > coefficients in GF(2^16)). Thanks to the action
> of the 8-th power of
> > Frobenius, this basis can be reduced to approximately
> 2^22 elements.
> >
> > Note that performing linear algebra on 2^22 elements
> would be quite
> > costly. However, as explained in [Jo13a], in the case
> of Kummer
> > extension, we are in fact able to split the computation
> into several
> > much smaller ones. In the present case, we have to
> solve 130 linear
> > systems, the smallest one contains 130 linear
> polynomials (up to
> > Frobenius), the next system contains 2^14 elements
> (corresponding to
> > polynomials of the form u^2+u+alpha). Finally, we also
> have 128
> > systems containing 2^15 elements. Each of these 128
> systems was solved
> > in 9 hours (including the generation of the
> corresponding equations)
> > on 8-cores. They were run independently in parallel and
> the total
> > CPU time is less than 9300 CPU.hours.
> >
> >
> > Individual Logarithms:
> >
> > We followed a descent approach similar to [JoLe06]. As
> in our previous
> > computation [Jo13], this descent includes three
> separate parts.
> > First, we used continued fractions to find an
> expression of a value
> > related to Z as a product of relatively low degree
> polynomials. Here,
> > the highest degree polynomial has degree 29. Then using
> classical
> > descent (rercursively), we expressed these polynomials
> using
> > polyomials of degree 12 or less. Finally, the new
> descent phase allows
> > us to continue the descent down to degree 2.
> >
> > [In [Jo13], the maximal degree after the continued
> fraction step was
> > 18 and the new descent was only used for polynomials of
> degree 5 or less.]
> >
> > The continued fraction steps took a few hours on 8
> cores. Hitting
> > degree 29 so quickly was quite lucky. The classical
> descent took 12
> > hours on one core for the slowest of the polynomials
> appearing after
> > the continued fraction step. The total cost for
> classical descent was
> > less than 50 CPU.hours.
> >
> > After the classical descent, we had 149 polynomials of
> degree 12, 128
> > polynomials of degree 11 and 125 polynomials of degree
> 10 (we neglect
> > polynomials of degree 9 or less, which belongs to a
> lower level of the
> > descent tree and whose contribution to the total
> runtime is
> > negliglible). Among those, the most costly where the
> polynomials of
> > degree 12. On average, for each of those, it took 4
> hours on a Intel
> > Core i7 processor to find a decomposition into
> polynomials of degree 9
> > or less. Once this was done, the remaining time to get
> the value of
> > the logarithm was about 13 hours per degree 12
> polynomial (using the
> > same machine as for the linear algebra step). The
> polynomials of
> > degree 11 and 10 were less expensive, respectively
> requiring
> > a total time of 13 and 4 hours each.
> >
> > Once this logarithms were collected, concluding the
> computation took
> > about 20 CPU.hours.
> >
> > The total cost of the descent step was less than 4800
> CPU.hours.
> >
> > Finally, we find:
> > Z = g ^
>
593537791871423043223099993371775097225725806985608997497794966002388232480207689669841040498259020695864963162877267246612766963427481859635858268330211735283816590918847157995342025638775868791428528017795465828457233366986043689100592091740290308960776447743054737077011247538124490796554449688480787567205892205650065036371339635472100864592768628245778548627169993710530248952247502198339102414084716879305058973285967705897824717564625973834423283500191898814926886245805865469139425619857671065003012554407741143232334093943305148519456757124018567398173204598371497326728353430064760122625256809889244046240196511162297600325959107770470258420076304617198648034933080689987331284620483405839935257400541623168826151054513474118227797035847388394395856357901517982012097929227063749790707261218087106940061945085772301126801745411682353582722847329651670327300923889334538644453387154238350424246300168196173426827737854006788592008029058493609771615532931377
732819543558562!
> >
> 9703275367750105825453097378643622824901407930221204813818805961136841682239404338275246672278987523193876833029445938199819122011285813404240449718569721922907241151390900428524224234201221755939491010573105885453826465599986918927823875647571538
> >
> >
> > Antoine Joux (CryptoExperts and UVSQ, France, Antoine.Joux@m4x.org),
> >
> >
> > References:
> > ===========
> >
> > [Go+13a] Discrete logarithms in a GF(2^1971).
> > Faruk Gologlu, Robert
> Granger, Gary McGuire and Jens Zumbragel
> > NMBRTHRY list, Feb.
> 20th, 2013.
> > https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=4793
> >
> > [Go+13a] On the Function Field Sieve and the
> Impact of Higher Splitting Probabilities:
> >
> Application to Discrete Logarithms in
> GF(2^1971)
> >
> Faruk Gologlu, Robert Granger, Gary McGuire and Jens
> Zumbragel
> >
> Eprint Archive. http://eprint.iacr.org/2013/074
> >
> > [JoLe06] The Function Field Sieve in the Medium Prime
> Case. Antoine Joux and
> >
> Reynald Lercier. EUROCRYPT'2006
> >
> > [Jo13] Discrete logarithms in GF(2^1778). Antoine
> Joux.
> > NMBRTHRY list, Feb.
> 11th, 2013.
> > https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=2317
> >
> > [Jo13a] A new index calculus algorithm with
> complexity L(1/4+o(1)) in very small characteristic.
> > Antoine
> Joux.
> > Eprint
> Archive. http://eprint.iacr.org/2013/095
> >
> >
> > Appendix: Pari/GP verification script
> > =======================
> > Warning: This verification takes several minutes
> >
> > \p 2000
> > allocatemem(100000000)
> > Q=2^16
> > Z= sum(i=0,254,u^i*Pol(binary(floor(Pi*Q^(i+1))%Q),a))
> > pola=(a^16+a^5+a^3+a+1)*Mod(1,2)
> > polu=u^255+ Mod(a^14 + a^12 + a^7 + a^6 + a^5 + a^4 +
> a,pola)
> > g=(u+a)*Mod(1,2)*Mod(1,pola)*Mod(1,polu)
> >
>
lg=593537791871423043223099993371775097225725806985608997497794966002388232480207689669841040498259020695864963162877267246612766963427481859635858268330211735283816590918847157995342025638775868791428528017795465828457233366986043689100592091740290308960776447743054737077011247538124490796554449688480787567205892205650065036371339635472100864592768628245778548627169993710530248952247502198339102414084716879305058973285967705897824717564625973834423283500191898814926886245805865469139425619857671065003012554407741143232334093943305148519456757124018567398173204598371497326728353430064760122625256809889244046240196511162297600325959107770470258420076304617198648034933080689987331284620483405839935257400541623168826151054513474118227797035847388394395856357901517982012097929227063749790707261218087106940061945085772301126801745411682353582722847329651670327300923889334538644453387154238350424246300168196173426827737854006788592008029058493609771615532931
37773281954355856297032!
> >
> 75367750105825453097378643622824901407930221204813818805961136841682239404338275246672278987523193876833029445938199819122011285813404240449718569721922907241151390900428524224234201221755939491010573105885453826465599986918927823875647571538
> > if (g^lg == Z, print("Verification OK"),
> print("Verification FAILED"))
> >
>
>