×

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
PDFBibTeX XMLCite