Modular exponentiation via the explicit Chinese remainder theorem

Daniel J Bernstein; Jonathan P Sorenson

doi:10.1090/S0025-5718-06-01849-7

Modular exponentiation via the explicit Chinese remainder theorem

Daniel J Bernstein
, Jonathan P Sorenson

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper we consider the problem of computing xe mod m for large integers x, e, and m. This is the bottleneck in Rabin’s algorithm for testing primality, the Diffie-Hellman algorithm for exchanging cryptographic keys, and many other common algorithms.

Original language	American English
Journal	Scholarship and Professional Work - LAS
Volume	76
Issue number	257
DOIs	https://doi.org/10.1090/S0025-5718-06-01849-7
State	Published - Jan 1 2007

Keywords

Chinese remainder theorem
Diffie-Hellman
Rabin
algorithm
modular exponentiation

Disciplines

Applied Mathematics
Computer Sciences
Theory and Algorithms

Access to Document

10.1090/S0025-5718-06-01849-7License: Unspecified

Modular exponentiation via the explicit Chinese remainder theoremFinal published version, 5.92 MBLicense: Unspecified

Cite this

@article{05c935b19f9143ac8eb27370f881931e,

title = "Modular exponentiation via the explicit Chinese remainder theorem",

abstract = " In this paper we consider the problem of computing xe mod m for large integers x, e, and m. This is the bottleneck in Rabin{\textquoteright}s algorithm for testing primality, the Diffie-Hellman algorithm for exchanging cryptographic keys, and many other common algorithms.",

keywords = "Chinese remainder theorem, Diffie-Hellman, Rabin, algorithm, modular exponentiation",

author = "Bernstein, \{Daniel J\} and Sorenson, \{Jonathan P\}",

note = "Daniel J. Bernstein and Jonathan P. Sorenson. {"}Modular exponentiation via the explicit Chinese remainder theorem{"} Mathematics of Computaion 76.257 (2007): 443-454.",

year = "2007",

month = jan,

day = "1",

doi = "10.1090/S0025-5718-06-01849-7",

language = "American English",

volume = "76",

journal = "Scholarship and Professional Work - LAS",

number = "257",

}

TY - JOUR

T1 - Modular exponentiation via the explicit Chinese remainder theorem

AU - Bernstein, Daniel J

AU - Sorenson, Jonathan P

N1 - Daniel J. Bernstein and Jonathan P. Sorenson. "Modular exponentiation via the explicit Chinese remainder theorem" Mathematics of Computaion 76.257 (2007): 443-454.

PY - 2007/1/1

Y1 - 2007/1/1

N2 - In this paper we consider the problem of computing xe mod m for large integers x, e, and m. This is the bottleneck in Rabin’s algorithm for testing primality, the Diffie-Hellman algorithm for exchanging cryptographic keys, and many other common algorithms.

AB - In this paper we consider the problem of computing xe mod m for large integers x, e, and m. This is the bottleneck in Rabin’s algorithm for testing primality, the Diffie-Hellman algorithm for exchanging cryptographic keys, and many other common algorithms.

KW - Chinese remainder theorem

KW - Diffie-Hellman

KW - Rabin

KW - algorithm

KW - modular exponentiation

UR - https://digitalcommons.butler.edu/facsch_papers/96

U2 - 10.1090/S0025-5718-06-01849-7

DO - 10.1090/S0025-5718-06-01849-7

M3 - Article

VL - 76

JO - Scholarship and Professional Work - LAS

JF - Scholarship and Professional Work - LAS

IS - 257

ER -

Modular exponentiation via the explicit Chinese remainder theorem

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this