Unified method for iterative computation of modular multiplication and reduction operations

William L. Freking, Keshab K Parhi

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

In this paper, a unified methodology is introduced for the computation of modular multiplication and reduction operations, which are fundamental to numerous public-key cryptography systems. First, a general theory is presented which aides the construction of arbitrary most-significant-digit first and least-significant-digit first iterative modular reduction methods. Utilizing this foundation, new methods are presented which are not premised in division techniques. The resultant class of algorithmic techniques, which we dub iterative residue accumulation (IRA) methods, are robust, accommodating general radixes. Furthermore, forms supporting both most-significant-digit or least-significant-digit first evaluation are presented. Significantly, in comparison to earlier methods, IRA effectively replaces quotient-digit evaluation and quotient-modulus multiplication steps encountered in techniques such as Montgomery's method with a single-step residue evaluation, thereby permitting efficiency improvements. Forms suitable for either lookup or multiplication-based evaluation are explored. Precomputation overhead is minimal and the methods are suitable for VLSI implementation.

Original languageEnglish (US)
Pages (from-to)80-87
Number of pages8
JournalProceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors
StatePublished - Dec 1 1999

Fingerprint

Public key cryptography
Iterative methods

Cite this

@article{f2240b652b1d42b5905530ad207508b0,
title = "Unified method for iterative computation of modular multiplication and reduction operations",
abstract = "In this paper, a unified methodology is introduced for the computation of modular multiplication and reduction operations, which are fundamental to numerous public-key cryptography systems. First, a general theory is presented which aides the construction of arbitrary most-significant-digit first and least-significant-digit first iterative modular reduction methods. Utilizing this foundation, new methods are presented which are not premised in division techniques. The resultant class of algorithmic techniques, which we dub iterative residue accumulation (IRA) methods, are robust, accommodating general radixes. Furthermore, forms supporting both most-significant-digit or least-significant-digit first evaluation are presented. Significantly, in comparison to earlier methods, IRA effectively replaces quotient-digit evaluation and quotient-modulus multiplication steps encountered in techniques such as Montgomery's method with a single-step residue evaluation, thereby permitting efficiency improvements. Forms suitable for either lookup or multiplication-based evaluation are explored. Precomputation overhead is minimal and the methods are suitable for VLSI implementation.",
author = "Freking, {William L.} and Parhi, {Keshab K}",
year = "1999",
month = "12",
day = "1",
language = "English (US)",
pages = "80--87",
journal = "Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors",
issn = "1063-6404",

}

TY - JOUR

T1 - Unified method for iterative computation of modular multiplication and reduction operations

AU - Freking, William L.

AU - Parhi, Keshab K

PY - 1999/12/1

Y1 - 1999/12/1

N2 - In this paper, a unified methodology is introduced for the computation of modular multiplication and reduction operations, which are fundamental to numerous public-key cryptography systems. First, a general theory is presented which aides the construction of arbitrary most-significant-digit first and least-significant-digit first iterative modular reduction methods. Utilizing this foundation, new methods are presented which are not premised in division techniques. The resultant class of algorithmic techniques, which we dub iterative residue accumulation (IRA) methods, are robust, accommodating general radixes. Furthermore, forms supporting both most-significant-digit or least-significant-digit first evaluation are presented. Significantly, in comparison to earlier methods, IRA effectively replaces quotient-digit evaluation and quotient-modulus multiplication steps encountered in techniques such as Montgomery's method with a single-step residue evaluation, thereby permitting efficiency improvements. Forms suitable for either lookup or multiplication-based evaluation are explored. Precomputation overhead is minimal and the methods are suitable for VLSI implementation.

AB - In this paper, a unified methodology is introduced for the computation of modular multiplication and reduction operations, which are fundamental to numerous public-key cryptography systems. First, a general theory is presented which aides the construction of arbitrary most-significant-digit first and least-significant-digit first iterative modular reduction methods. Utilizing this foundation, new methods are presented which are not premised in division techniques. The resultant class of algorithmic techniques, which we dub iterative residue accumulation (IRA) methods, are robust, accommodating general radixes. Furthermore, forms supporting both most-significant-digit or least-significant-digit first evaluation are presented. Significantly, in comparison to earlier methods, IRA effectively replaces quotient-digit evaluation and quotient-modulus multiplication steps encountered in techniques such as Montgomery's method with a single-step residue evaluation, thereby permitting efficiency improvements. Forms suitable for either lookup or multiplication-based evaluation are explored. Precomputation overhead is minimal and the methods are suitable for VLSI implementation.

UR - http://www.scopus.com/inward/record.url?scp=0033296541&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033296541&partnerID=8YFLogxK

M3 - Article

SP - 80

EP - 87

JO - Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors

JF - Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors

SN - 1063-6404

ER -