Redundant integer representations and fast exponentiation
type: Item
instance of: scholarly article
title: Redundant integer representations and fast exponentiation
zbMATH Open document ID: 0852.94016
DOI: 10.1007/BF00125080
author: Dieter Gollmann
author: Yongfei Han
author: Chris J. Mitchell
published in: Designs, Codes and Cryptography
publication date: 1996-12-12T00:00:00Z
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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 863676
zbMATH Keywords: implementation of modular exponentiation of large integers
zbMATH Keywords: cryptographic algorithms
zbMATH Keywords: signed-digit representations
zbMATH Keywords: string replacement
zbMATH Keywords: complexity
zbMATH Keywords: square-and-multiply exponentiation algorithm
reviewed by: Jozef Vyskoč
MaRDI profile type: Publication
cites work: A SIGNED BINARY MULTIPLICATION TECHNIQUE
cites work: Minimum weight modified signed-digit representations and fast exponentiation
cites work: Q3935355
cites work: High-radix and bit recoding techniques for modular exponentiation
cites work: Adaptive \(m\)-ary segmentation and canonical recoding algorithms for multiplication of large binary numbers
cites work: Modular Multiplication Without Trial Division
cites work: Q3660954
cites work: A method for obtaining digital signatures and public-key cryptosystems
cites work: High-Speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree
cites work: An improved binary algorithm for RSA
full work available at URL: https://doi.org/10.1007/bf00125080
OpenAlex ID: W2081847638
description: scientific article; zbMATH DE number 863676