Rescheduled Montgomery Multiplication : digit level parallelism in serial architectures

Simple item page
dc.contributor.advisorSwartzlander, Earl E., Jr., 1945-
dc.contributor.committeeMemberGerstlauer, Andreas
dc.contributor.committeeMemberJohn, Lizy K
dc.contributor.committeeMemberOrshansky, Michael E
dc.contributor.committeeMemberSchulte, Michael J
dc.creatorGrale, Trenton John
dc.creator.orcid0000-0002-7924-5144
dc.date.accessioned2021-09-24T21:22:45Z
dc.date.available2021-09-24T21:22:45Z
dc.date.created2021-08
dc.date.issued2021-08-05
dc.date.submittedAugust 2021
dc.date.updated2021-09-24T21:22:46Z
dc.description.abstractTwo well-known cryptographic protocols, RSA and ECC, employ modular multiplication on large integers or binary polynomial bit strings of hundreds or thousands of bits. The modulus may be an odd integer (usually prime), or an irreducible polynomial. Large products exceeding the value of the modulus must be reduced to congruent values smaller than the modulus. In simple terms, this is done by taking the remainder with respect to the modulus. However, reduction by integer or polynomial division is computationally expensive. The Montgomery Multiplication transform and algorithm replace arbitrary division by the modulus with division by a power of two. Both hardware and software realizations of the Montgomery algorithm have been proposed over the past three decades. These range from serial algorithms that perform bit or digit level operations to large full word parallel architectures. A widely-adopted classification scheme categorizes and characterizes serial Montgomery architectures. This dissertation introduces the Serial Montgomery Model by fundamentally upgrading the existing scheme to accurately characterize a rich universe of architectures that employ digit level parallelism. Certain properties of the Montgomery computation present optimization opportunities that have been little noted by prior researchers. This dissertation presents a novel Rescheduled Montgomery Multiplication architecture that targets those opportunities to drive a new level of optimal tradeoffs between area cost and latency. The architecture exploits digit level parallelism and dependency scheduling to attain higher performance than is attainable with serial architectures while avoiding the high area cost associated with large parallel architectures.
dc.description.departmentElectrical and Computer Engineering
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/2152/88058
dc.identifier.urihttp://dx.doi.org/10.26153/tsw/14999
dc.language.isoen
dc.subjectModular arithmetic
dc.subjectMontgomery multiplication
dc.subjectDigit level parallelism
dc.subjectSerial Montgomery Model
dc.subjectRescheduled Montgomery Multiplication
dc.titleRescheduled Montgomery Multiplication : digit level parallelism in serial architectures
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentElectrical and Computer Engineering
thesis.degree.disciplineElectrical and Computer Engineering
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
GRALE-DISSERTATION-2021.pdf
Size:
3.87 MB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.45 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download

Collections

UT Electronic Theses and Dissertations