Fast modular exponentiation and elliptic curve group operation in Maple
Song Yuan Yan, Glyn James · International Journal of Mathematical Education in Science and Technology · 2006
The modular exponentiation, y≡x k (mod n) with x,y,k,n integers and n > 1, is the most fundamental operation in RSA and ElGamal public-key cryptographic systems. Thus the efficiency of RSA and ElGamal depends entirely on the efficiency of the modular exponentiation. The same situation arises also in elliptic curve cryptography, in which the elliptic curve group operation, Q≡kP (mod q) with P , Q points on elliptic curve E: y 2=x 3+ax+b over a finite field q , is the most fundamental operation and needs to be performed as fast as possible. In this paper, two variants of fast implementations for modular exponentiation and elliptic curve group operation in Maple are presented.