|
New frameworks for Montgomery's modular multiplication method
Author(s):
Philip
B.
McLaughlin Jr..
Journal:
Math. Comp.
73
(2004),
899-906.
MSC (2000):
Primary 11-04, 11Y16;
Secondary 11A07, 11T55
Posted:
May 7, 2003
MathSciNet review:
2031414
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We present frameworks for fast modular multiplication based on a modification of Montgomery's original method. For (fixed) large integers, our algorithms may be significantly faster than conventional methods. Our techniques may also be extended to modular polynomial arithmetic.
References:
-
- 1.
- Richard Crandall and Barry Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994), 305-324. MR 94c:11123
- 2.
- Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.), Addison-Wesley, Boston, MA, 1998. MR 83i:68003
- 3.
- Peter L. Montgomery, Modular multiplication without trial division, Math. Comp. 44 (1985), 519-521. MR 86e:11121
- 4.
- Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), 243-264. MR 88e:11130
- 5.
- H. J. Nussbaumer, Fast Fourier Transform and Convolution Algorithms, (2nd ed.), Springer-Verlag, New York, 1982. MR 83e:65219
Similar Articles:
Retrieve articles in Mathematics of Computation
with
MSC (2000):
11-04, 11Y16,
11A07, 11T55
Retrieve articles in all Journals with
MSC (2000):
11-04, 11Y16,
11A07, 11T55
Additional Information:
Philip
B.
McLaughlin
Jr.
Affiliation:
237 N. Harris Avenue, Tucson, Arizona 85716
Email:
pbmcl@netscape.net
DOI:
10.1090/S0025-5718-03-01543-6
PII:
S 0025-5718(03)01543-6
Keywords:
Modular arithmetic,
multiplication,
factorization,
primality testing,
polynomial arithmetic,
public-key cryptography
Received by editor(s):
May 5, 2000
Received by editor(s) in revised form:
July 2, 2002
Posted:
May 7, 2003
Copyright of article:
Copyright
2003,
American Mathematical Society
|
