|
Re: Elliptic Curves in polynomial groups
by abell (Chaplain) on May 22, 2003 at 22:27 UTC
|
I think Math::Pari is the best way to do elliptic curve computations within perl.
If you are willing to give up perl, you would gain in efficiency by using the native Pari C library or the scripting environment GP.
You would need some working knowledge of Pari anyway, if you meant to use Math::Pari.
If you know some C++, there is also the LiDIA library, which provides high level functions for dealing with finite fields and everything needed for elliptic curve computations.
Cheers
Antonio
The stupider the astronaut, the easier it is to win the trip to Vega - A. Tucket
| [reply] |
|
|
I want to do EC-based public key encryption and signature, and it's a small part of the overall program.
I was thinking of using Math::BigInt abstract interface and allowing whatever the most optimal implementation is on that platform as the "engine". But Math::Pari has some EC stuff built-in already... but I wonder if that's just EC in general using real numbers, not modular arithmetic on finite fields.
| [reply] |
|
|
Pari functions for elliptic curves are very general and work for finite fields as well.
A finite field elements is represented by a modular polynomial modulo an irreducible modular polynomial.
For instance, a representation of the finite fields with 7^3 elements consists of elements of this form (in Pari notation):
Mod( Mod(1, 7)*a*x^2 + Mod(1, 7)*b*x + Mod(1, 7)*c, Mod(1, 7)*x^3 + Mod(1, 7)*x + Mod(1, 7) )
You get all elements by varying a, b and c from 0 to 6.
See this recent thread for more examples.
Building an efficient finite field library starting from big integers is fun, but quite demanding, and you'd probably prefer to focus on the higher level algorithms. In this case, I suggest you try and play a bit with Pari under the GP environment (which is interactive and has online help).
Once you have understood what functions serve your purpose, you can assemble them into a C program or a GP script, which will be invoked from your program, or integrate them directly into your program (via Math::Pari).
Have fun
Antonio
The stupider the astronaut, the easier it is to win the trip to Vega - A. Tucket
| [reply] |
|
|
|
|
Re: Elliptic Curves in polynomial groups
by wufnik (Friar) on May 23, 2003 at 07:19 UTC
|
Math::Pari is a fine module, but suffers, I think, from the fact that PARI can't currently be compiled as a dll on windows, at least last time i tried. I would be happy to be corrected here.
Using Math::Pari will also presume a little familiarity with GP and GP scripts, which may not be something you wish to learn. I found GP fun, a little like mathematica without the graphics, but learning it properly, for ecc, will take a little time.
The absence of the native ability of perl to deal with large integer arithmetic has given rise to some of the
most ingenious perl/<large integer capable software> hybrids I've ever seen - witness adam back's diminutive munitions page, 5 lines over which i spent 2 days.
you could use bc instead of pari -
but the new perl will include large integers as a basic type.
or, perhaps quickest, you could perlify the code in michael rosing's 'implementing elliptic curve cryptography', written in c, and use bigint as the basis for your large integer arithmetic. while not the fastest in terms of runtime, at least you'd have the advantage that you could debug it all in one spot/ide(if you use activestate).
| [reply] |
|
|
Math::Pari is a fine module, but suffers, I think, from the fact that PARI can't currently be compiled as a dll on windows, at least last time i tried. I would be happy to be corrected here.
update: In case simply quoting you was a bit misterious, i'll explicitly state it, it's no longer true it no longer matters, just look at my signature.
MJD says you
can't just make shit up and expect the computer to know what you mean, retardo!
I run a Win32 PPM
repository for perl 5.6x+5.8x. I take requests.
** The Third rule of perl club is a statement of fact: pod is sexy.
|
| [reply] |
|
|
| [reply] |
|
|
| [reply] |