Redundant integer representations and fast exponentiation

DOI10.1007/BF00125080MaRDI QIDQ1910428zbMATH OpenOpenAlexFDO

Authors Dieter Gollmann, Yongfei Han, Chris J. Mitchell

Publication date 12 December 1996

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00125080

zbMATH Keywords

complexitycryptographic algorithmsimplementation of modular exponentiation of large integerssigned-digit representationssquare-and-multiply exponentiation algorithmstring replacement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Review text

Efficient implementation of modular exponentiation of large integers is of great significance for many cryptographic algorithms. The well-known ``square and multiply technique seems to be generally accepted, yet the number of multiplications involved can be reduced using alternative representation of the exponent. The paper deals with two such representations. In the first case use of signed-digit representations of the exponent already proposed by other authors is considered and a precise analysis of its performance is given. Next, a new technique based on a different redundant representation of the exponent, called string replacement, is proposed and its complexity analyzed. Finally the new algorithm is compared with other variants of the square-and-multiply exponentiation algorithm.

Recommendations

• Fast exponentiation by folding the signed-digit exponent in half
• scientific article; zbMATH DE number 2188494
• A faster modular multiplication algorithm
• An improved binary algorithm for RSA

Cites work

• A method for obtaining digital signatures and public-key cryptosystems
• A SIGNED BINARY MULTIPLICATION TECHNIQUE
• Adaptive \(m\)-ary segmentation and canonical recoding algorithms for multiplication of large binary numbers
• An improved binary algorithm for RSA
• High-radix and bit recoding techniques for modular exponentiation
• High-Speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree
• scientific article; zbMATH DE number 3812999 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• Minimum weight modified signed-digit representations and fast exponentiation
• Modular Multiplication Without Trial Division

Cited in

(6)

• Signed bits and fast exponentiation
• Exponent Recoding and Regular Exponentiation Algorithms
• Minimal weight k-SR representations
• Speculatively Redundant Continued Logarithm Representation
• Low-cost addition-subtraction sequences for the final exponentiation in pairings
• Should one always use repeated squaring for modular exponentiation?

This page was built for publication: Redundant integer representations and fast exponentiation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1910428)