Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Montgomery modular multiplication
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Montgomery form == If {{mvar|a}} and {{mvar|b}} are integers in the range {{math|[0, ''N'' − 1]}}, then their sum is in the range {{math|[0, 2''N'' − 2]}} and their difference is in the range {{math|[−''N'' + 1, ''N'' − 1]}}, so determining the representative in {{math|[0, ''N'' − 1]}} requires at most one subtraction or addition (respectively) of {{mvar|N}}. However, the product {{math|''ab''}} is in the range {{math|[0, ''N''<sup>2</sup> − 2''N'' + 1]}}. Storing the intermediate integer product {{math|''ab''}} requires twice as many bits as either {{mvar|a}} or {{mvar|b}}, and efficiently determining the representative in {{math|[0, ''N'' − 1]}} requires division. Mathematically, the integer between 0 and {{math|''N'' − 1}} that is congruent to {{math|''ab''}} can be expressed by applying the [[Euclidean division#Statement of the theorem|Euclidean division theorem]]: :<math>ab = qN + r,</math> where {{mvar|q}} is the quotient <math>\lfloor ab / N \rfloor</math> and {{mvar|r}}, the remainder, is in the interval {{math|[0, ''N'' − 1]}}. The remainder {{mvar|r}} is {{math|''ab'' mod ''N''}}. Determining {{mvar|r}} can be done by computing {{mvar|q}}, then subtracting {{math|''qN''}} from {{math|''ab''}}. For example, again with <math>N=17</math>, the product {{math|{{overline|7}} β {{overline|15}}}} is determined by computing <math>7 \cdot 15 = 105</math>, dividing <math>\lfloor 105 / 17 \rfloor = 6</math>, and subtracting <math>105 - 6 \cdot 17 = 105 - 102 = 3</math>. Because the computation of {{mvar|q}} requires division, it is undesirably expensive on most computer hardware. Montgomery form is a different way of expressing the elements of the ring in which modular products can be computed without expensive divisions. While divisions are still necessary, they can be done with respect to a different divisor {{mvar|R}}. This divisor can be chosen to be a power of two, for which division can be replaced by shifting, or a whole number of machine words, for which division can be replaced by omitting words. These divisions are fast, so most of the cost of computing modular products using Montgomery form is the cost of computing ordinary products. The auxiliary modulus {{mvar|R}} must be a positive integer such that {{math|1=gcd(''R'', ''N'') = 1}}. For computational purposes it is also necessary that division and reduction modulo {{mvar|R}} are inexpensive, and the modulus is not useful for modular multiplication unless {{math|''R'' > ''N''}}. The ''Montgomery form'' of the residue class {{math|{{overline|''a''}}}} with respect to {{mvar|R}} is {{math|''aR'' mod ''N''}}, that is, it is the representative of the residue class {{math|{{overline|''aR''}}}}. For example, suppose that {{math|1=''N'' = 17}} and that {{math|1=''R'' = 100}}. The Montgomery forms of 3, 5, 7, and 15 are {{math|1=300 mod 17 = 11}}, {{math|1=500 mod 17 = 7}}, {{math|1=700 mod 17 = 3}}, and {{math|1=1500 mod 17 = 4}}. Addition and subtraction in Montgomery form are the same as ordinary modular addition and subtraction because of the distributive law: :<math>aR + bR = (a + b)R,</math> :<math>aR - bR = (a - b)R.</math> Note that doing the operation in Montgomery form does not lose information compared to doing it in the quotient ring {{math|'''Z'''/''N'''''Z'''}}. This is a consequence of the fact that, because {{math|1=gcd(''R'', ''N'') = 1}}, multiplication by {{mvar|R}} is an [[isomorphism]] on the additive group {{math|'''Z'''/''N'''''Z'''}}. For example, {{math|1=(7 + 15) mod 17 = 5}}, which in Montgomery form becomes {{math|1=(3 + 4) mod 17 = 7}}. Multiplication in Montgomery form, however, is seemingly more complicated. The usual product of {{math|''aR''}} and {{math|''bR''}} does not represent the product of {{mvar|a}} and {{mvar|b}} because it has an extra factor of {{mvar|R}}: :<math>(aR \bmod N)(bR \bmod N) \bmod N = (abR)R \bmod N.</math> Computing products in Montgomery form requires removing the extra factor of {{mvar|R}}. While division by {{mvar|R}} is cheap, the intermediate product {{math|(''aR'' mod ''N'')(''bR'' mod ''N'')}} is not divisible by {{mvar|R}} because the modulo operation has destroyed that property. So for instance, the product of the Montgomery forms of 7 and 15 modulo 17, with {{math|1=''R'' = 100}}, is the product of 3 and 4, which is 12. Since 12 is not divisible by 100, additional effort is required to remove the extra factor of {{mvar|R}}. Removing the extra factor of {{mvar|R}} can be done by multiplying by an integer {{math|''R''′}} such that {{math|''RR''′ ≡ 1 (mod ''N'')}}, that is, by an {{math|''R''′}} whose residue class is the [[modular inverse]] of {{mvar|R}} mod {{mvar|N}}. Then, working modulo {{mvar|N}}, :<math>(aR \bmod N)(bR \bmod N)R' \equiv (aR)(bR)R^{-1} \equiv (ab)R \pmod{N}.</math> The integer {{math|''R''′}} exists because of the assumption that {{mvar|R}} and {{mvar|N}} are coprime. It can be constructed using the [[extended Euclidean algorithm]]. The extended Euclidean algorithm efficiently determines integers {{math|''R''′}} and {{math|''N''′}} that satisfy [[BΓ©zout's identity]]: {{math|0 < ''R''′ < ''N''}}, {{math|0 < ''N''′ < ''R''}}, and: :<math>RR' - NN' = 1.</math> This shows that it is possible to do multiplication in Montgomery form. A straightforward algorithm to multiply numbers in Montgomery form is therefore to multiply {{math|''aR'' mod ''N''}}, {{math|''bR'' mod ''N''}}, and {{math|''R''′}} as integers and reduce modulo {{mvar|N}}. For example, to multiply 7 and 15 modulo 17 in Montgomery form, again with {{math|1=''R'' = 100}}, compute the product of 3 and 4 to get 12 as above. The extended Euclidean algorithm implies that {{math|1=8β 100 − 47β 17 = 1}}, so {{math|1=''R''′ = 8}}. Multiply 12 by 8 to get 96 and reduce modulo 17 to get 11. This is the Montgomery form of 3, as expected.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)