New frameworks for Montgomery’s modular multiplication method
HTML articles powered by AMS MathViewer
- by Philip B. McLaughlin Jr. PDF
- Math. Comp. 73 (2004), 899-906 Request permission
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
- Richard Crandall and Barry Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994), no. 205, 305–324. MR 1185244, DOI 10.1090/S0025-5718-1994-1185244-1
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Peter L. Montgomery, Modular multiplication without trial division, Math. Comp. 44 (1985), no. 170, 519–521. MR 777282, DOI 10.1090/S0025-5718-1985-0777282-X
- Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7
- Henri J. Nussbaumer, Fast Fourier transform and convolution algorithms, Springer Series in Information Sciences, vol. 2, Springer-Verlag, Berlin-New York, 1981. MR 606376
Additional Information
- Philip B. McLaughlin Jr.
- Affiliation: 237 N. Harris Avenue, Tucson, Arizona 85716
- Email: pbmcl@netscape.net
- Received by editor(s): May 5, 2000
- Received by editor(s) in revised form: July 2, 2002
- Published electronically: May 7, 2003
- © Copyright 2003 American Mathematical Society
- Journal: Math. Comp. 73 (2004), 899-906
- MSC (2000): Primary 11-04, 11Y16; Secondary 11A07, 11T55
- DOI: https://doi.org/10.1090/S0025-5718-03-01543-6
- MathSciNet review: 2031414