Re: ECC modelling

[Eugene N <neverov.biks.07.1@gmail.com>]

Thank you very much, Bill

I will try to understand the scripts you provided (especially one with vectors, for i am new to gp syntax). This is very kind of you!

Unfortunately i installed the older version of pari and am now reinstalling the latest one (in mine ffgen was missing).

One more question: if i were to generate EC(GF(2^m)) random points, i would have to choose random x, solve an equation and obtain corresponding y.

Does pari provides something for square roots in GF(2^m)?

Thanks a lot!

Eugene

2011/4/2 Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>

On Sat, Apr 02, 2011 at 04:41:43PM +0300, Eugene N wrote:
> Hello Sirs
>
> I am a student and i recently decided to use this renound tool for the
> purpose of ECC modelling.
> I browsed through the manuals & did some web searcehes (
> http://orion.math.iastate.edu/cbergman/crypto/pari/parihelp.html)
> and i am very happy to discover this great tool.
>
> However, i stumbled upon some problems, wich made me turn for advice to
> expirienced users like you. I hope you will clear som things for me.
>
> I am looking for a way to generate n-nomials (generators of m.gr. inGF(2^m)
> ), especially tri-and pentanomials. I have read about ffinit(p,n) - but it
> produces
> long polies.

There are no functions in PARI to generate irreducible trinomials or pentanomials.
but you can program it in GP easily:

trino(N)=for(i=1,N-1,P=x^N+x^i+1;if(polisirreducible(P*Mod(1,2)),return(P)))
penta(N)=forvec(v=vector(3,i,[1,N-1]),P=x^N+1+sum(i=1,3,x^v[i]);if(polisirreducible(P*Mod(1,2)),return(P)))

ffinit is much faster, though.

> I would like also to find some examples of binary elliptic curves and
> base-point generation.

If you mean elliptic curve of GF(2^m),
you need to get an irreducible polynomial P and do
g=ffgen(P*Mod(1,2),'g)
g is now a field generator for GF(2^m).

You can define the elliptic curve Y^2+Y=X^3+X over GF(2^m) as follow:
E=ellinit([0,0,1,1,0]*g^0);

Cheers,
Bill.