Cohen, Gérard; Lobstein, Antoine; Naccache, David; Zémor, Gilles How to improve an exponentiation black-box. (English) Zbl 0929.68050 Nyberg, Kaisa (ed.), Advances in Cryptology. International conference on the Theory and application of cryptographic techniques. Espoo, Finland, May 31 - June 4, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1403, 211-220 (1998). Summary: We present a method for improving the performance of RSA-type exponentiations. The scheme is based on the observation that replacing the exponent \(d\) by \(d'=d+k\varphi(n)\) has no arithmetic impact but results in significant speed-ups when \(k\) is properly chosen. Statistical analysis, verified by extensive simulations, confirms a performance improvement of 9.3% for the square-and-multiply scheme and 4.3% for the signed binary digit algorithm. However, the most attractive feature of our method seems to be the fact that in most cases, existing exponentiation black-boxes can be accelerated by simple external one-time pre-computations without any internal code or hardware modifications.For the entire collection see [Zbl 0889.00042]. MSC: 68P25 Data encryption (aspects in computer science) 11Y16 Number-theoretic algorithms; complexity Keywords:RSA-type exponentiations PDFBibTeX XMLCite \textit{G. Cohen} et al., Lect. Notes Comput. Sci. 1403, 211--220 (1998; Zbl 0929.68050)