Speeding up the computations on an elliptic curve using addition-subtraction chains
Morain, François ; Olivos, Jorge
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990), p. 531-543 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1990__24_6_531_0,
     author = {Morain, Fran\c cois and Olivos, Jorge},
     title = {Speeding up the computations on an elliptic curve using addition-subtraction chains},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {24},
     year = {1990},
     pages = {531-543},
     mrnumber = {1082914},
     zbl = {0724.11068},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1990__24_6_531_0}
}

Morain, François; Olivos, Jorge. Speeding up the computations on an elliptic curve using addition-subtraction chains. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990) pp. 531-543. http://gdmltest.u-ga.fr/item/ITA_1990__24_6_531_0/

1.A. O. L. Atkin, Manuscript.

2.F. Bergeron, J. Berstel, S. Brlek and C. Duboc, Addition Chains using Continued Fractions, Journal of Algorithms, 10, 3, 1989, pp. 403-412. | MR 1006993 | Zbl 0682.68025

3.W. Bosma, Primality Testing using Elliptic Curves, Report 85-12, Math. Instituut, Universeit van Amsterdam.

4.A. Brauer, On Addition Chains, Bull. Amer Math. Soc, 45, 1939, pp. 736-739. | JFM 65.0154.02 | MR 245

5.R. P. Brent, Some Integer Factorization Algorithms using Elliptic Curves, Research Report CMA-R32-85, The Australian National University, Canberra, 1985.

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, | Zbl 0527.10001

7. J. W. S. Cassels, Diophantine Equations with Special References to Elliptic Curves, J. London Math. Soc., 1966, pp. 193-291. | MR 199150 | Zbl 0138.27002

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

10. H. Cohen and A. K. Lenstra, Implementation of a New Primality Test, Math. Comp., 1987, 177, pp. 103-121. | MR 866102 | Zbl 0608.10001

11. P. Erdös, Remarks on Number Theory III : On Addition Chains, Acta Arithmetica, 1960, pp. 77-81. | MR 121346 | Zbl 0219.10064

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). | MR 1008504 | Zbl 0681.68064

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. 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. G. H. Gonnet, Handbook of Algorithms and Data Structures, Addison-Wesley, 1984. | Zbl 0665.68001

16. D. H. Greene, Labelled Formal Languages and Their Uses, Technical Report STAN-CS-83-982, Stanford University, 1983.

17. B. S. Jr. Kaliski, A Pseudo-Random Bit Generator Based on Elliptic Logarithms, Proc. Crypto 86, pp. 13-1, 13-21. | Zbl 0635.94011

18. D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming, T. II, Addisoon-Wesley. | Zbl 0895.65001

19. N. Koblitz, Elliptic curve cryptosystems. Math. Comp., 1987, 48, 177, pp. 203-209. | MR 866109 | Zbl 0622.94015

20. H. W. Jr. Lenstra, Factoring with Elliptic Curves, Report 86-18, Math. Inst., Univ. Amsterdam, 1986. | Zbl 0596.10007

21. H. W. Jr. Lenstra, Elliptic Curves and Number Theoretic Algorithms, Report 86-19, Math. Inst., Univ. Amsterdam, 1986. | MR 934218

22. H. W. Jr. Lenstra, Factoring integers with elliptic curves. Annals of Math., 1987, 126, pp. 649-673. | MR 916721 | Zbl 0629.10006

23. D. P. Mccarthy, The Optimal Algorithm to Evaluate xn using Elementary Multiplication Methods, Math. Comp., 1977, 31, 137, pp. 251-256. | MR 428791 | Zbl 0348.65041

24. D. P. Mccarthy, Effect to Improved Multiplication Efficiency on Exponentiation Algorithms Derived from Addition Chains, Math. Comp., 1986, 46, 174, pp. 603-608. | MR 829630 | Zbl 0608.68027

25. P. L. Montgomery, Modular Multiplication without Trial Division, Math. Comp., 1985, 44, 170, pp. 519-521. | MR 777282 | Zbl 0559.10006

26. F. Morain, Implementation of the Atkin-Goldwasser-Kilian test. I.N.R.I.A. Research, Report 911, 1988.

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. J. Olivos, On Vectorial Additions Chains. J. of Algorithms, 1981, 2, pp. 13-21. | MR 640507 | Zbl 0466.68034

29. J.-M. Pollard, Theorems on factorization and primality testing. Proc. Cambridge Phil. Soc., 1974, 76, pp. 521-528. | MR 354514 | Zbl 0294.10005

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. | MR 700103 | Zbl 0368.94005

31. A. Schönhage, A Lower Bound for the Length of Addition Chains, Theor. Comput. Science, 1975, 1, 1, pp. 1-12. | MR 478756 | Zbl 0307.68032

32. J. T. Tate, The Arithmetic of Elliptic Curves, Inventiones Math., 1974, 23, pp.179-206. | MR 419359 | Zbl 0296.14018