Speeding up the computations on an elliptic curve using addition-subtraction chains

 Access to full text

 Full (PDF)

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.68025MR1006993
3. 3. W. BOSMA, Primality Testing using Elliptic Curves, Report 85-12, Math. Instituut, Universeit van Amsterdam. Zbl1103.11039
4. 4. A. BRAUER, On Addition Chains, Bull. Amer Math. Soc, 45, 1939, pp. 736-739. Zbl65.0154.02MR245JFM65.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±1, B = 2, 3, 5, 6, 1, 10, 11, 12 up to High Powers, Contemporary Math., A. M. S., 1983, Zbl0527.10001
7. 7. J. W. S. CASSELS, Diophantine Equations with Special References to Elliptic Curves, J. London Math. Soc., 1966, pp. 193-291. Zbl0138.27002MR199150
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. Zbl0614.10004
10. 10. H. COHEN and A. K. LENSTRA, Implementation of a New Primality Test, Math. Comp., 1987, 177, pp. 103-121. Zbl0608.10001MR866102
11. 11. P. ERDÖS, Remarks on Number Theory III : On Addition Chains, Acta Arithmetica, 1960, pp. 77-81. Zbl0219.10064MR121346
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.68064MR1008504
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
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
18. 18. D. E. KNUTH, Seminumerical Algorithms, The Art of Computer Programming, T. II, Addisoon-Wesley. Zbl0895.65001
19. 19. N. KOBLITZ, Elliptic curve cryptosystems. Math. Comp., 1987, 48, 177, pp. 203-209. Zbl0622.94015MR866109
20. 20. H. W. Jr. LENSTRA, Factoring with Elliptic Curves, Report 86-18, Math. Inst., Univ. Amsterdam, 1986. Zbl0596.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.10006MR916721
23. 23. D. P. MCCARTHY, The Optimal Algorithm to Evaluate xn using Elementary Multiplication Methods, Math. Comp., 1977, 31, 137, pp. 251-256. Zbl0348.65041MR428791
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.68027MR829630
25. 25. P. L. MONTGOMERY, Modular Multiplication without Trial Division, Math. Comp., 1985, 44, 170, pp. 519-521. Zbl0559.10006MR777282
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.68034MR640507
29. 29. J.-M. POLLARD, Theorems on factorization and primality testing. Proc. Cambridge Phil. Soc., 1974, 76, pp. 521-528. Zbl0294.10005MR354514
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.94005MR700103
31. 31. A. SCHÖNHAGE, A Lower Bound for the Length of Addition Chains, Theor. Comput. Science, 1975, 1, 1, pp. 1-12. Zbl0307.68032MR478756
32. 32. J. T. TATE, The Arithmetic of Elliptic Curves, Inventiones Math., 1974, 23, pp.179-206. Zbl0296.14018MR419359

1. Wieb Bosma, Signed bits and fast exponentiation
2. Jiří Tůma, Jiří Vábek, On the number of binary signed digit representations of a given weight
3. Srećko Brlek, Pierre Castéran, Laurent Habsieger, Richard Mallette, On-line evaluation of powers using Euclid's algorithm