On the Construction of Short Addition-Subtraction Chains and their Applications

Ngom, Moussa; Tall, Amadou

doi:10.2478/tmmp-2023-0010

Abstract

The problem of computing xⁿ effciently, such that x and n are known to be very interesting, specially when n is very large. In order to find effcient methods to solve this problem, addition chains have been much studied, and generalized to addition-subtraction chains. These various chains have been useful in finding effcient exponentiation algorithms. In this paper, we present a new method to recover all existing exponentiation algorithms. It will be applied to design a new fast exponentiation method.

References

[1] BERGERON, F.—BERSTEL, J.—BRLEK, S.—DUBOC, C.: Addition chains using continued fractions, J. Algorithms 10 (1989), no. 3, 403–412.
Search in Google Scholar Back to article
[2] BLEICHENBACHER, D.—FLAMMENKAMP, A.: An effcient algorithm for computing shortest addition chains, SIAM J. Discrete Math. 10 (1997), no. 1, 15–17.
Search in Google Scholar Back to article
[3] DOWNEY, P.—LEONG, B.—SETHI, R.: Computing sequences with addition chains, SIAM J. Comput. 10 (1981), no. 3, 638–646.
Search in Google Scholar Back to article
[4] VOLGER, H.: Some results on addition-subtraction chains, Inform. Process. Lett. 20 (1985), no. 3, 155–160.
Search in Google Scholar Back to article
[5] KNUTH, D. E.: The Art of Computer Programming, Vol. 2. Seminumerical Algorithms. Second edition. Addison-Wesley Series in Computer Science and Information Processing. Addison-Wesley Publishing Co., Reading, Mass., 1981.
Search in Google Scholar Back to article
[6] MIGNOTTE, M.—TALL, A.: A note on addition chains, Int. J. Algebra, 5 (2011), no. 6, 269–274.
Search in Google Scholar Back to article
[7] TAKAGI, T.—REIS, D.—YEN, S.—WU, B.: Radix-r non-adjacent form and its application to pairing-based cryptosystem, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E89-A (2006), no. 1, 115–123. DOI: 10.1093/ietfec/e89-a.1.11510.1093/ietfec/e89-a.1.115
Search in Google Scholar Back to article
[8] TALL, A.: A generalization of Lucas addition chains, Bull. Math. Soc. Sci. Math. Roumanie (N.S.) 55(103) (2012), no. 1, 79–93.
Search in Google Scholar Back to article
[9] YACOBI, Y.: Exponentiating faster with addition chains, In: Advances in cryptology—EUROCRYPT ’90 (Aarhus, 1990), Lecture Notes in Comput. Sci., Vol. 473, Springer-Verlag, Berlin, 1991. pp. 222–229,10.1007/3-540-46877-3_20
Search in Google Scholar Back to article
[10] MORRAIN, F.—OLIVOS, J.: Speeding up the computation on an elliptic curve using addition-subtraction chains,RAIROInformatique Théor. Appl. 24 (1990), no. 6, 531–543.
Search in Google Scholar Back to article
[11] GORDON, D. M.: A survey of fast exponentiation methods J. Algorithms 27 (1998), no. 1, 129–146.
Search in Google Scholar Back to article
[12] TALL, A.: A generalization of Lucas addition chains, Bull. Math. Soc. Sci. Math. Roumanie (N.S.) 55 (103) (2012), 79–93.
Search in Google Scholar Back to article

On the Construction of Short Addition-Subtraction Chains and their Applications

Abstract

Paradigm

My account