Article Contentsp. 519p. 520p. 521Issue Table of ContentsMathematics of Computation, Vol. 44, No. 170 (Apr., 1985), pp. 283-577+S17-S25Volume Information [pp. 575 - 577]Front MatterSome A Posteriori Error Estimators for Elliptic Partial Differential Equations [pp. 283 - 301]Mixed Finite Element Methods for Quasilinear Second-Order Elliptic Problems [pp. 303 - 320]Improved Accuracy by Adapted Mesh-Refinements in the Finite Element Method [pp. 321 - 343]Finite Element Methods of Optimal Order for Problems with Singular Data [pp. 345 - 360]Convenient Stability Criteria for Difference Approximations of Hyperbolic Initial-Boundary Value Problems [pp. 361 - 377]The Convergence of Galerkin Approximation Schemes for Second-Order Hyperbolic Equations With Dissipation [pp. 379 - 390]Variable Step Size Predictor-Corrector Schemes for Second Kind Volterra Integral Equations [pp. 391 - 404]On the Steady States of Finitely Many Chemical Cells [pp. 405 - 415]Conjugate Gradient-Like Algorithms for Solving Nonsymmetric Linear Systems [pp. 417 - 424]On Polynomial Approximation in the Complex Plane with Application to Conformal Mapping [pp. 425 - 433]On the Differential-Difference Properties of the Extended Jacobi Polynomials [pp. 435 - 441]The Generalized Integro-Exponential Function [pp. 443 - 458]Rational Approximations for the Fresnel Integrals [pp. 459 - 461]Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis [pp. 463 - 471]On the Conjecture of Birch and Swinnerton-Dyer for an Elliptic Curve of Rank 3 [pp. 473 - 481]Elliptic Curves Over Finite Fields and the Computation of Square Roots $\operatorname{mod} p$ [pp. 483 - 494]On Totally Real Cubic Fields [pp. 495 - 518]Modular Multiplication Without Trial Division [pp. 519 - 521]Some Periodic Continued Fractions With Long Periods [pp. 523 - 532]2000000 Steiner Triple Systems of Order 19 [pp. 533 - 535]Computing $\pi(x)$: The Meissel-Lehmer Method [pp. 537 - 560]Averaging Effects on Irregularities in the Distribution of Primes in Arithmetic Progressions [pp. 561 - 571]Reviews and Descriptions of Tables and Booksuntitled [pp. 573 - 574]untitled [p. 574]Supplement to the Convergence of Galerkin Approximation Schemes for Second-Order Hyperbolic Equations With Dissipation [pp. S17 - S25]Back MatterModular Multiplication Without Trial DivisionAuthor(s): Peter L. MontgomerySource: Mathematics of Computation, Vol. 44, No. 170 (Apr., 1985), pp. 519-521Published by: American Mathematical SocietyStable URL: http://www.jstor.org/stable/2007970Accessed: 09/02/2010 12:13Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available athttp://www.jstor.org/page/info/about/policies/terms.jsp. JSTOR's Terms and Conditions of Use provides, in part, that unlessyou have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and youmay use content in the JSTOR archive only for your personal, non-commercial use.Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained athttp://www.jstor.org/action/showPublisher?publisherCode=ams.Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printedpage of such transmission.JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range ofcontent in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new formsof scholarship. For more information about JSTOR, please contact [email protected] Mathematical Society is collaborating with JSTOR to digitize, preserve and extend access toMathematics of Computation.http://www.jstor.orgMATHEMATICS OF COMPUTATION VOLUME 44, NUMBER 170 APRIL, 1985, PAGES 519-521 Modular Multiplication Without Trial Division By Peter L. Montgomery Abstract. Let N > 1. We present a method for multiplying two integers (called N-residues) modulo N while avoiding division by N. N-residues are represented in a nonstandard way, so this method is useful only if several computations are done modulo one N. The addition and subtraction algorithms are unchanged. 1. Description. Some algorithms [1], [2], [4], [5] require extensive modular arith- metic. We propose a representation of residue classes so as to speed modular multiplication without affecting the modular addition and subtraction algorithms. Other recent algorithms for modular arithmetic appear in [3], [6]. Fix N > 1. Define an N-residue to be a residue class modulo N. Select a radix R coprime to N (possibly the machine word size or a power thereof) such that R > N and such that computations modulo R are inexpensive to process. Let R' and N' be integers satisfying 0 < R-1 < N and 0 < N' < R and RR-' - NN' = 1. For 0 < i < N, let i represent the residue class containing iR'- mod N. This is a complete residue system. The rationale behind this selection is our ability to quickly compute TR-1 mod N from T if 0 < T < RN, as shown in Algorithm REDC: function REDC(T) m *- (Tmod R)N'mod R [so O < m < R] t --(T + mN)/R if t > N then return t - N else return t U To validate REDC, observe mN TN'N -Tmod R, so t is an integer. Also, tR Tmod N so t TR-' mod N. Thirdly, 0 < T + mN < RN + RN, so O < t < ,2N. If R and N are large, then T + mN may exceed the largest double-precision value. One can circumvent this by adjusting m so -R < m < 0. Given two numbers x and y between 0 and N - 1 inclusive, let z = REDC(xy). Then z (xy)R-1 mod N, so (xR-1)(yR-1) zR-1 mod N. Also, 0 < z < N, so z is the product of x and y in this representation. Other algorithms for operating on N-residues in this representation can be derived from the algorithms normally used. The addition algorithm is unchanged, since xR' + yR' zR'- mod N if and only if x + y z mod N. Also unchanged are Received December 19, 1983. 1980 Mathematics Subject Classification. Primary 1OA30; Secondary 68C05. Key words and phrases. Modular arithmetic, multiplication. ?1985 American Mathematical Society 0025-5718/85 $1.00 + $.25 per page 519520 PETER L. MONTGOMERY the algorithms for subtraction, negation, equality/inequality test, multiplication by an integer, and greatest common divisor with N. To convert an integer x to an N-residue, compute xR mod N. Equivalently, compute REDC((x mod