Full Disclosure mailing list archives
DL over GF(p^k), p small
From: Imaginero Lamero <imaginerolamero () yahoo com>
Date: Mon, 20 Aug 2007 07:22:23 -0700 (PDT)
Hello, Can someone coment on theese fast DLs over GF(p^k) with p smal? Atached pari programme use p-adic logs, time is less than an minute: (Numbers may wrap) (13:19) gp > \r fil.gp q=370801^18 ;po1=17 ; po2=3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117109 ; tt=4702816082614016182965692121592448734541768804994600705383687298520660242493249158332154303805784930 ;po1^tt-po2 mod q=0 q=2^2003 ; po1=3 ; po2=19 ; t2=46046993139340166507090345615136250245999852064751171464668824387327204617681975780033079082311475657137920713633763250220430610306299407245801779788107829618296187553498768740217764857679385834036527096610226088132909804871500857727685554848681412848966715381705429730393858144254724754753785416583532641000842142306002349659344124042311390577104136195412245014808630785142511094125656912846715271821518325318857294740147530820821910283761699863431400217626353118504249795670889601044291930122883686330300672097906241079404551995315676104058601306583435730299863940037603350130072634964196048067365501 po1^t2-po2 mod q=0 (13:20) { \\ Tries to find l such that \\ po1^l = po2 mod p^k \\ Complexity p-1 \\ This program is distributed under the terms of the GPL dlani(p,k,po1,po2)= local(i,j,j2,j3,z1,z2,l1,l2,lo,q,kk); q=p^k; kk=k+1; po1=Mod(1,q)*lift(po1); po2=Mod(1,q)*lift(po2); z1=polrootspadic(x-lift(po1),p,kk); z1=z1[1]; z2=polrootspadic(x-lift(po2),p,kk); z2=z2[1]; l1=log(z1); l2=log(z2); lo=lift(Mod(1,p^(k-1))*lift(l2/l1)); \\ ;) j=po1^lo; if(j==po2,return(lo)); j3=po1^(p^(k-1)); j2=j3; for(i=1,p-1, if((j*j3)==po2,return(lo+i*p^(k-1))); j3=j3*j2; ); return(0); } p=370801; k=18; q=p^k; ro=znprimroot(q);\\XXX this may be slow pre=round(log(q)/log(10))-1; default(realprecision,pre); sec=floor(Pi()*10^pre)+42; po1=Mod(ro,q); po2=sec; tt=dlani(p,k,po1,po2); print("q=",p,"^",k," ;po1=",lift(po1)," ; po2=",lift(po2)," ; tt=",tt," ;po1^tt-po2 mod q=",lift(po1^tt-po2)); p=2; k=2003; q=p^k; po1=Mod(3,q);po2=19;\\ 7^2, 13^2 t2=dlani(p,k,po1,po2); print("q=",p,"^",k," ; po1=",lift(po1)," ; po2=",lift(po2)," ; t2=",t2," po1^t2-po2 mod q=",lift(po1^t2-po2)); 2/0; \\ Exit nicely --------------------------------- Choose the right car based on your needs. Check out Yahoo! Autos new Car Finder tool.
_______________________________________________ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Current thread:
- DL over GF(p^k), p small Imaginero Lamero (Aug 20)