Montgomery MultiplicationDuncan A. BuellOctober 11, 2005AbstractWe describe Montgomery multiplication.1 Montgomery MultiplicationPeter Montgomery has devised a way to speed up arithmetic in a contextin which a single modulus is used for a long-running computation [Mon85].This method has also been explored as a hardware o peration [BD97, EW93].The basic idea goes back to a standard trick that has been used forarithmetic modulo Mersenne n umbers.Let Mn=2n−1bethen-th Mersenne number. Assume that we are doingarithmetic modulo Mn. The crucial operation is multiplication: if A and Bare integers modulo Mn,thatistosay,n-bit numbers, then the productC = A · B can be written a s C = C1· 2n+ C0; C1and C0are the digits ofthe product C written with radix 2n.The trick is to observe the following.C = C1· 2n+ C0= C1· 2n− C1+ C1+ C0= C1· (2n− 1) + C1+ C0= C1· Mn+ C1+ C0≡ C1+ C0(mod Mn)So instead of having to divide by Mnin order to produce the remainder,we only need to add the left half of a product to the right half of the product.Montgomery Multiplication Page 2For example, let’s do the arithmetic modulo basen− 1forbase = 10.Specifically, let’s do arithmetic this w ay modulo 99 = 102− 1. Take 53 · 77 =4081, say. This is4081 = 40 · 100 + 81=40· 100 − 40 + 40 + 81=40· 99 + 40 + 81≡ 121 (mod 99).In this case, we happen to get a sum larger than the modulus, and we haveto subtract 99 from 121 to get the final result of 22. But one addition andpossibly one subtraction is a major advantage over a full multiprecise divide.So now let’s see how to do this for an arbitrary integer and not just forbasen− 1.Assume we’re going to do a lot of arithmetic modulo some fixed N.Choose R =2k>N for a suitable k. Assuming that R and N are relativelyprime (and if not, bump k by one and we should be able to get an R that isrelatively prime), then we can solve for Rand Nsuch that RR− NN=1.What we will do is multiply everything by R. All the constants, all thenumbers, etc. So instead of doing arithmetic with integers a and b,say,wewill be doing arithmetic with integers aR and bR. At the very end of thecomputation, we multiply any result by R.SinceRR≡ 1(modN), werecover the result we would have Addition and subtraction are fine, sincea + b = c ⇔ aR + bR = cR.The problem is with multiplication:aR · bR = abR2which means that we have an extra factor of R. Whatwewanttodoishave a function to which we can pass the product abR2and that will returnabR. We could do this by multiplying modulo N by R, but that would be amultiplication modulo N, and it’s exactly that that we are trying to avoid.Here’s how we do it. Start with T = abR2.m ← (T (mod R)) · N(mod R)t ← (T + mN)/Rand we return either t or t − N, whichever lies in the range 0 to N − 1.Montgomery Multiplication Page 3Example: Let N = 79, and instead of using a power of 2 for R , we’ll useR = 100 for readability. We find that 64 · 100 − 81 · 79 = 1, so we haveR = 100, R= 64, N = 79, N= 81.Now let’s say that we multiply a =17timesb = 26 to get 442. Thenumber 17 is really a· 100 modulo 79 for some a. Multiplying 17 · 64 ≡ 61(mod 79), we find that a= 61. Similarly, 26 · 64 ≡ 5 (mod 79). So whenwe multiply 17 and 26 in this representation, we’re really trying to multiply61 · 5 = 305 ≡ 68 (mod 79).Knowing that we can in fact work modulo 79, we know that what we haveis17 · 26 = 442 ≡ (61 · 100) · (5 · 100)≡ 305 · 100 · 100≡ 68 · 100 · 100 (mod 79)and if we multiply by 64 and reduce modulo 79 we should get the rightanswer:442 · 64 ≡ 28288 ≡ 6 ≡ 68 · 100 (mod 79).The function we want is the function that will take as input the 442 andreturn 6. And the function described above does exactly that:m = (442 (mod 100)) · 81 (mod 100)=42· 81 (mod 100)= 3402 (mod 100)≡ 2 (mo d 100)t = (442 + 2 · 79)/100= (442 + 158)/100= 600/100=6and we return t = 6 as the result.Proof that the algorithm works: We assume that value T is a product, andhence is double length. Since we choose R>Nbut not too much bigger,the products can be taken to be double length in R.The first modular reduction simply converts T to a single length numbermodulo R. Again modulo R,wehavethatm = TN.ThusmN ≡ TNN ≡−T (mod R).Montgomery Multiplication Page 4So when we take T + mN we get an integer that is zero modulo R and wecan legitimately divide out the R and get an integer quotient for t.Now the fact that we get the right quotient comes from the fact thattR = T + mN ≡ T (mod N)so that modulo N we have t ≡ TR.Montgomery Multiplication Page 5References[BD97] Jean-Claude Bajard and Laurent-St´ephane Dider. An RNS Mont-gomery modular multiplication a lgorithm. Proceedings, IEEE Sym-posium on Computer Arithmetic, pages 234–239, 1997.[EW93] Stephen E. Eldridge and Colin D. Walter. Hardware implemen-tation of Montgomery’s modular multiplication algorithm. IEEETransactions on Computers, 42:693–699, 1993.[Mon85] Peter L. Montgomery. Modular multiplication without trial divi-sion. Mathematics of Computation, 44:519–521,