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/
