Skip to content
IJAMR International Journal of Applied Mathematical Research E-ISSN 2227-4324

Efficient computation of addition-subtraction chains using generalized continued Fractions

Authors and Affiliations

About this article

DOI
https://doi.org/10.14419/ijamr.v2i1.553
Received
13-11-2012
Accepted
02-12-2012
Published
19-12-2012
Views
633
Downloads
273
Download PDF

Abstract

The aim of this paper is to present a new way of computing short addition-subtraction chains using the generalized continued fractions where subtraction is allowed. We will recover the most used ways of getting addition-subtraction chains. This method is not always optimal but gives minimal chains that are easy to compute.

Author Biography

  • Amadou Tall, African Institute for Mathematical Sciences, African Institute for Mathematical Sciences, African Institute for Mathematical Sciences, African Institute for Mathematical Sciences

    Academic Manager

    AIMS-Senegal

References

[1] Fran¸cois Morrain, Jorge Olivos Speeding up the computation on an elliptic curve using addition-subtaction chains, Informatique th´eorique et applications 24, (6) (1990) 531-543.

[2] Peter L. Montgomery. Evaluating recurrences of form Xm+n = f(Xm, Xn, Xm−n) via Lucas Chains, January 1992.

[3] F. Bergeron, J. Berstel, S. Brlek and C. Duboc, Addition chains using continued fractions, journal of algorithms 10, p 403-412, 1989

[4] F. Bergeron, J. Berstel and S. Brlek, Efficient computation of addition chains, Journal de th´eorie des nombres de Bordeaux 6, p 21-38, 1994

[5] Hugo Volger. Some results on addition-subtraction chains, Information Processing Letters 20 (3) (8 April 1985) 155-160.

View more references (9)

[6] Maurice Mignotte, Amadou Tall, A note on addition chains, International Journal of Algebra 5 (6) (2011) 269 - 274.

[7] Tall Amadou, A generalization of Lucas addition chains, Bulletin Math´ematique de la Roumanie Tome 55 (103) (1) (2012) 79 - 93.

[8] K. Koyama, Y Tsuruoka, Speeding elliptic cryptosystems using a signed binary window method, Advances in cryptology 740 (1992) 345 - 357.

[9] CY. Sakari, K. Sakurai, Efficient scalar multiplication on elliptic curve with direct computations of several doublings, IEICE Transactions Fundamentals E84-A(1) (2001) 120-129.

[10] P. Downey, B. Leong and R. Sethi; ”computing sequences with addition chains”’, SIAM journal on Computing, 10 (3), p 638-646, 1981

[11] Y. Yacobi, ”Exponentiating faster with addition chains”, Lecture notes in computer science, Volume 473/1991, p 222-229, Bellcore, 1991

[12] A. Flammenkamp ”Integers with a Small Number of Minimal Addition Chains”, Discrete Mathematics V. 205 1999 pp 221-227

[13] T. Takgi, D. Reis, S. Yen and B. Wu. Radix-r Non-Adjacent Form and Its Application to Pairing-Based Cryptosystem. IEICETRANS. Fundamentals,VOL. E 89-A,NO. 1 January 2006

[14] D. Bleichenbacher and A. Flammenkamp ”An Efficient Algorithm for Computing Shortest Addition Chains”, submitted 1997 to SIAM Journal of Discrete Mathematics.


How to Cite

Tall, A., & Sanghare, A. Y. (2012). Efficient computation of addition-subtraction chains using generalized continued Fractions. International Journal of Applied Mathematical Research, 2(1), 76-83. https://doi.org/10.14419/ijamr.v2i1.553

Related Articles