Tuesday, May 17, 2005

Elliptic Curves with Pari/GP

From the example in section 3.1.2 in the Certicon ECC Challenge.

? t=Mod(1,2)
%1 = Mod(1, 2)
? p1=t*x^4+t*x+t
%2 = Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)
? polisirreducible(p1)
%124 = 1
? a=Mod(t*x+t,p1)
%3 = Mod(Mod(1, 2)*x + Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2))
? tt=Mod(t,p1)
%4 = Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2))
? e=ellinit([tt,a,0,0,tt])
%5 = [Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2)*x+ Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), 0, 0, Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(0, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(0, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), 0, 0, 0, 0, 0, 0]
? a1=[Mod(t*x^3+t*x^2,p1),Mod(t*x^2+t,p1)]
%6 = [Mod(Mod(1, 2)*x^3 + Mod(1, 2)*x^2, Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2)*x^2 + Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2))]
? ellisoncurve(e,a1)
%7 = 1
? elladd(e,a1,a1)
%8 = [Mod(Mod(1, 2)*x^2 + Mod(1, 2)*x + Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x+ Mod(1, 2)), Mod(Mod(1, 2)*x^2 + Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2))]
? q=[0,tt];
? for(pw=1,3,q1=q;
? for(i=1,length(q1),q1[i]=q1[i]+Mod(t*x^pw,p1));q=concat(q,q1))
for(ea=1,length(q), for(ec=2,length(q), e=ellinit([tt,q[ea],0,0,q[ec]]);listkill(l);for(i=1,length(q), for(j=1,length(q), if(ellisoncurve(e,[q[i],q[j]]),listput(l,[q[i],q[j]]))));print(ea-1," ",ec-1," ",length(l)+1)))

? for(s=1,length(l), for(i=1,length(l)+1, if([0]==ellpow(e,l[s],i),print(s," ",i);break)))

It's unfortunate the output is so messy.

1 comment :

Anonymous said...

Try using lift() more to clean up the all of the Mod's that are accumulating.