# zbMATH — the first resource for mathematics

Speeding up the computations on an elliptic curve using addition- subtraction chains. (English) Zbl 0724.11068
This paper describes two algorithms for the computation of $$x^ n$$ by means of addition-subtraction chains. An analysis shows that the best of the two algorithms is about 11% faster than the ordinary binary exponentiation algorithm. This can be applied to computations on elliptic curves for factorization and primality testing. The first author has used the second algorithm in his implementation of the so-called Atkin’s test for primality testing.
The first algorithm is based on the fact that a number whose binary representation consists of k 1’s can be written as the difference of $$2^ k$$ and 1: $1...^{k} 1=10...^{k} 0-1.$ Hence, in the standard binary algorithm we can replace the operation corresponding to a chain of 1’s by an operation corresponding to a chain of 0’s followed by a division. This may reduce the amount of work if the inverse of x is known or easily computable.
The second algorithm is a refinement of the first, based on the observation that for a string of 1’s containing an isolated 0 we have: $1...^{k} 101...^{\ell} 1=10...^{k} 000...^{\ell} 0-10...^{\ell -1} 01.$

##### MSC:
 11Y11 Primality 11Y05 Factorization 68Q25 Analysis of algorithms and problem complexity 11A63 Radix representation; digital problems
Maple
Full Text: