speeding up computations
eabril at ole.com
Sun Dec 29 18:53:01 CET 2002
This is a nice trick you might use to speed up computations, for example
in El Gamal cryptosytem.
I give you a brief explaination and the reference of the paper where it
IDEA: We want to compute g^k (mod N), where g is a generator and k is a
The cost of computing g^k is proportional to the number of 1's that k
has in its binary representation.
What we do is to choose r,s,t with only a few 1's and set k=r*s*t, so we
have to compute:
g^k = ((g^r)^s)^t. This does NOT affect its security (see the reference)
and it's very easy to implement, isn't?.
REFERENCE: "Random small Hamming weight products with applications to
cryptography" ,authors:J.Hoffstein and J.H.Silverman, downlable at
www.ntru.com (fast to read, just a bit of math background...).
Happy new year,
More information about the Gnupg-devel