Abstract
Modular exponentiation is one of the most important operations in almost all modern cryptosystems. It is performed using a series of modular multiplications. This operation is time consuming for large operands as is always the case in cryptography. Hence fast public-key cryptography software or hardware requires optimisation of the time consumed by a single modular multiplication and/or the reduction of the total number of modular multiplications required. This paper introduces a novel idea based on the principles of ant colony optimisation for finding a minimal addition chain that allows one to reduce the number of modular multiplications so that modular exponentiation can be implemented efficiently. The best addition chain reached by the ant system is compared to the one used in the m-ary and sliding window methods as well as with the best addition chain evolved by genetic algorithms. We demonstrate that the ant system significantly outperforms all these methods for any exponent size.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Begeron, R., Berstel, J., Brlek, S. and Duboc, C.: Addition chains using continued fractions, J. Algorithms 10 (1989), 403–412.
Davis, L.: Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991.
Diaconis, P. and Efron, B.: Testing for independence in a two-way table: new interpretations of the chi-square statistic (with discussion), Ann. Stat. 13 (1985), 845–913.
Dorigo, M. and Gambardella, L. M.: Ant colony: a cooperative learning approach to the travelling salesman problem, IEEE Trans. Evol. Comput. 1(1) (1997), 53–66.
Dorigo, M. and Stutzle, T.: Ant Colony Optimisation, MIT Press, 2004.
Downing, P., Leong, B. and Sthi, R.: Computing sequences with addition chains, SIAM J. Comput. 10(3) (1981), 638–646.
Feber, J.: Multi-Agent Systems: an Introduction to Distributed Artificial Intelligence, Addison-Wesley, 1995.
Haupt, R. L. and Haupt, S. E.: Practical Genetic Algorithms, Wiley, 1998.
Knuth, D. E.: The Art of Programming: Semi-numerical Algorithms, Vol. 2, 2nd edn, Addison-Wesley, Reading, MA, 1981.
Koç, Ç. K.: High-speed RSA Implementation, Technical report, RSA Laboratories, Redwood City, California, USA, November 1994.
Kunihiro, N. and Yamamoto, H.: New methods for generating short addition chain, IEICE Trans. E83-A(1) (January 2000), 60–67.
Menezes, A. J., Van Oorschot, P. C. and Vanstone, S. A.: Handbook of Applied Cryptography, CRC, 1996.
Nedjah, N. and Mourelle, L. M.: Efficient parallel modular exponentiation algorithm, in Second International Conference on Information Systems, Lecture Notes in Computer Science, Vol. 2457, Springer, 2002, pp. 405–414.
Nedjah, N. and Mourelle, L. M.: Minimal addition chains using genetic algorithms, in Proceedings of the Fifteenth International Conference on Industrial & Engineering Applications of Artificial Intelligence & Expert Systems, Lecture Notes in Computer Science, Vol. 2358, Springer, 2002, pp. 88–98.
Nedjah, N. and Mourelle, L. M.: Efficient pre-processing for large window-based modular exponentiation using genetic algorithms, in Proceedings of the Sixteenth International Conference on Industrial & Engineering Applications of Artificial Intelligence & Expert Systems, Lecture Notes in Computer Science, Vol. 2718, Springer, 2003, pp. 625–635.
Rivest, R., Shamir, A. and Adleman, L.: A method for obtaining digital signature and public-key cryptosystems, Commun. ACM (21) (1978), 120–126.
Stutzle, T. and Dorigo, M.: ACO Algorithms for the Travelling Salesman Problems, Evolutionary Algorithms in Engineering and Computer Science, Wiley, 1999.
Author information
Authors and Affiliations
Corresponding author
Additional information
★★ Research supported by FAPERJ (http://www.faperj.br) and CNPq (http://www.cnpq.br).
Rights and permissions
About this article
Cite this article
Nedjah, N., de Macedo Mourelle, L. Towards Minimal Addition Chains Using Ant Colony Optimisation. J Math Model Algor 5, 525–543 (2006). https://doi.org/10.1007/s10852-005-9024-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10852-005-9024-z