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. \]


11Y11 Primality
11Y05 Factorization
68Q25 Analysis of algorithms and problem complexity
11A63 Radix representation; digital problems


Full Text: DOI EuDML


[1] 1. A. O. L. ATKIN, Manuscript.
[2] 2. F. BERGERON, J. BERSTEL, S. BRLEK and C. DUBOC, Addition Chains using Continued Fractions, Journal of Algorithms, 10, 3, 1989, pp. 403-412. Zbl0682.68025 MR1006993 · Zbl 0682.68025
[3] 3. W. BOSMA, Primality Testing using Elliptic Curves, Report 85-12, Math. Instituut, Universeit van Amsterdam. · Zbl 1103.11039
[4] 4. A. BRAUER, On Addition Chains, Bull. Amer Math. Soc, 45, 1939, pp. 736-739. MR245 JFM65.0154.02 · JFM 65.0154.02
[5] 5. R. P. BRENT, Some Integer Factorization Algorithms using Elliptic Curves, Research Report CMA-R32-85, The Australian National University, Canberra, 1985.
[6] 6. J. BRILLHART, D. H. LEHMER, B. TUCKERMAN and S. S. Jr. WAGSTAFF, Factorizations of bn\pm 1, B = 2, 3, 5, 6, 1, 10, 11, 12 up to High Powers, Contemporary Math., A. M. S., 1983, Zbl0527.10001 · Zbl 0527.10001
[7] 7. J. W. S. CASSELS, Diophantine Equations with Special References to Elliptic Curves, J. London Math. Soc., 1966, pp. 193-291. Zbl0138.27002 MR199150 · Zbl 0138.27002
[8] 8. B. W. CHAR, K. O. GEDDES, G. H. GONNET and S. M. WATT, MAPLE, Reference Marmal, Fourth Edition, Symbolic Computation Group, Department of Computer Science, University of Waterloo, 1985.
[9] 9. D. V. CHUDNOVSKY and G. V. CHUDNOVSKY, Sequences of Numbers Generated by Addition in Formal Groups and New primality and Factorization Tests, Research report RC 11262, I.B.M., Yorktown Heights, 1985. · Zbl 0614.10004
[10] 10. H. COHEN and A. K. LENSTRA, Implementation of a New Primality Test, Math. Comp., 1987, 177, pp. 103-121. Zbl0608.10001 MR866102 · Zbl 0608.10001
[11] 11. P. ERDÖS, Remarks on Number Theory III : On Addition Chains, Acta Arithmetica, 1960, pp. 77-81. Zbl0219.10064 MR121346 · Zbl 0219.10064
[12] 12. P. FLAJOLET, B. SALVY and P. ZIMMERMANN, Lambda-Upsilon-Omega : An assistant algorithms analyzer. In Applied Algebra, Algebraic Algotithms and Error-Correcting Codes (1989), T. MORA, Ed., Lecture Notes in Comp. Sci., 357, pp. 201-212. (Proceedings AAECC’6, Rome, July 1988). Zbl0681.68064 MR1008504 · Zbl 0681.68064
[13] 13. P. FLAJOLET, B. SALVY and P. ZIMMERMANN, Lambda-Upsilon-Omega : The, 1989 Cookbook, Research Report 1073, Institut National de Recherche en Informatique et en Automatique, August 1989, 116 pages.
[14] 14. S. GOLDWASSER and J. KILIAN, Almost all Primes can be quickly Certified. Proc. 18th A.C.M. Symp. on the Theory of Compt., Berkeley, 1986, pp. 316-329.
[15] 15. G. H. GONNET, Handbook of Algorithms and Data Structures, Addison-Wesley, 1984. Zbl0665.68001 · Zbl 0665.68001
[16] 16. D. H. GREENE, Labelled Formal Languages and Their Uses, Technical Report STAN-CS-83-982, Stanford University, 1983.
[17] 17. B. S. Jr. KALISKI, A Pseudo-Random Bit Generator Based on Elliptic Logarithms, Proc. Crypto 86, pp. 13-1, 13-21. Zbl0635.94011 · Zbl 0635.94011
[18] 18. D. E. KNUTH, Seminumerical Algorithms, The Art of Computer Programming, T. II, Addisoon-Wesley. Zbl0895.65001 · Zbl 0895.65001
[19] 19. N. KOBLITZ, Elliptic curve cryptosystems. Math. Comp., 1987, 48, 177, pp. 203-209. Zbl0622.94015 MR866109 · Zbl 0622.94015
[20] 20. H. W. Jr. LENSTRA, Factoring with Elliptic Curves, Report 86-18, Math. Inst., Univ. Amsterdam, 1986. Zbl0596.10007 · Zbl 0596.10007
[21] 21. H. W. Jr. LENSTRA, Elliptic Curves and Number Theoretic Algorithms, Report 86-19, Math. Inst., Univ. Amsterdam, 1986. MR934218
[22] 22. H. W. Jr. LENSTRA, Factoring integers with elliptic curves. Annals of Math., 1987, 126, pp. 649-673. Zbl0629.10006 MR916721 · Zbl 0629.10006
[23] 23. D. P. MCCARTHY, The Optimal Algorithm to Evaluate xn using Elementary Multiplication Methods, Math. Comp., 1977, 31, 137, pp. 251-256. Zbl0348.65041 MR428791 · Zbl 0348.65041
[24] 24. D. P. MCCARTHY, Effect to Improved Multiplication Efficiency on Exponentiation Algorithms Derived from Addition Chains, Math. Comp., 1986, 46, 174, pp. 603-608. Zbl0608.68027 MR829630 · Zbl 0608.68027
[25] 25. P. L. MONTGOMERY, Modular Multiplication without Trial Division, Math. Comp., 1985, 44, 170, pp. 519-521. Zbl0559.10006 MR777282 · Zbl 0559.10006
[26] 26. F. MORAIN, Implementation of the Atkin-Goldwasser-Kilian test. I.N.R.I.A. Research, Report 911, 1988.
[27] 27. F. MORAIN and J. OLIVOS, Un algorithmo de Evaluación de Potencia utilizando Cadenas de Suma y Resta, Proc. XIV Conference Latinoamericana de Informatica (C.L.E.I., Expodata), Buesnos Aires, September 1988.
[28] 28. J. OLIVOS, On Vectorial Additions Chains. J. of Algorithms, 1981, 2, pp. 13-21. Zbl0466.68034 MR640507 · Zbl 0466.68034
[29] 29. J.-M. POLLARD, Theorems on factorization and primality testing. Proc. Cambridge Phil. Soc., 1974, 76, pp. 521-528. Zbl0294.10005 MR354514 · Zbl 0294.10005
[30] 30. R. L. RIVEST, A. SHAMIR and L. ADLEMAN, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Comm. of the A.C.M., 1978, 21, 2, pp. 120-126. Zbl0368.94005 MR700103 · Zbl 0368.94005
[31] 31. A. SCHÖNHAGE, A Lower Bound for the Length of Addition Chains, Theor. Comput. Science, 1975, 1, 1, pp. 1-12. Zbl0307.68032 MR478756 · Zbl 0307.68032
[32] 32. J. T. TATE, The Arithmetic of Elliptic Curves, Inventiones Math., 1974, 23, pp.179-206. Zbl0296.14018 MR419359 · Zbl 0296.14018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.