speeding up computations

[eabril]

Hi.
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 
first appeared.
IDEA: We want to compute g^k (mod N), where g is a generator and k is a 
random number. 
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,
Eduardo.