Dear Yuhao Huang,
> In Elliptic curve calculations, there are lots of modular inversions. And
> the prime is a fixed large number, say 256 bits.
> I wonder how I can optimize this operation, right now it takes a lot of
> time. Can any one point me to something?
>
For computing scalar multiplications use inversion-free formulas
(projective, Jacobian, etc.). and only transform the result to affine
coordinates. See
http://hyperelliptic.org/EFD/
for a lot of choices.
The fastest method for inverting is the extended Euclidean algorithm but it
doesn't run in constant time. A secure way of computing inversions is
Fermat's little theorem:
a^{-1} = a^{p-2} mod p.
All the best
Tanja
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
