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 arithmetic on multiprecision integers == Most cryptographic applications require numbers that are hundreds or even thousands of bits long. Such numbers are too large to be stored in a single machine word. Typically, the hardware performs multiplication mod some base {{mvar|B}}, so performing larger multiplications requires combining several small multiplications. The base {{mvar|B}} is typically 2 for microelectronic applications, 2<sup>8</sup> for 8-bit firmware,<ref name="kizhvatov" /> or 2<sup>32</sup> or 2<sup>64</sup> for software applications. The REDC algorithm requires products modulo {{mvar|R}}, and typically {{math|''R'' > ''N''}} so that REDC can be used to compute products. However, when {{mvar|R}} is a power of {{mvar|B}}, there is a variant of REDC which requires products only of machine word sized integers. Suppose that positive multi-precision integers are stored [[little endian]], that is, {{mvar|x}} is stored as an array {{math|''x''[0], ..., ''x''[β - 1]}} such that {{math|0 ≤ ''x''[''i''] < ''B''}} for all {{mvar|i}} and {{math|1=''x'' = ∑ ''x''[''i''] ''B<sup>i</sup>''}}. The algorithm begins with a multiprecision integer {{mvar|T}} and reduces it one word at a time. First an appropriate multiple of {{mvar|N}} is added to make {{mvar|T}} divisible by {{mvar|B}}. Then a multiple of {{mvar|N}} is added to make {{mvar|T}} divisible by {{math|''B''<sup>2</sup>}}, and so on. Eventually {{mvar|T}} is divisible by {{mvar|R}}, and after division by {{mvar|R}} the algorithm is in the same place as REDC was after the computation of {{mvar|t}}. '''function''' MultiPrecisionREDC '''is''' '''Input:''' Integer ''N'' with {{nowrap|1=gcd(''B'', ''N'') = 1}}, stored as an array of ''p'' words, Integer {{nowrap|1=''R'' = ''B''<sup>''r''</sup>}}, --thus, ''r'' = ''log''<sub>''B''</sub> ''R'' Integer ''N''′ in {{nowrap|[0, ''B'' − 1]}} such that {{nowrap|''NN''′ β‘ −1 (mod ''B'')}}, Integer ''T'' in the range {{nowrap|0 ≤ ''T'' < ''RN''}}, stored as an array of {{nowrap|''r'' + ''p''}} words. '''Output:''' Integer ''S'' in {{nowrap|[0, ''N'' − 1]}} such that {{nowrap|''TR''<sup>−1</sup> β‘ ''S'' (mod ''N'')}}, stored as an array of ''p'' words. Set {{nowrap|1=''T''[''r'' + ''p''] = 0}} ''(extra carry word)'' '''for''' {{nowrap|0 ≤ ''i'' < ''r''}} '''do''' ''--loop1- Make T divisible by {{nowrap|B<sup>i+1</sup>}}'' ''c'' ← 0 ''m'' ← {{nowrap|''T''[''i''] β ''N''′ mod ''B''}} '''for''' {{nowrap|0 ≤ ''j'' < ''p''}} '''do''' ''--loop2- Add the {{nowrap|m β N[j]}} and the carry from earlier, and find the new carry'' ''x'' ← {{nowrap|''T''[''i'' + ''j''] + ''m'' β ''N''[''j''] + ''c''}} ''T''[''i'' + ''j''] ← {{nowrap|''x'' mod ''B''}} ''c'' ← {{nowrap|β''x'' / ''B''β}} '''end for''' '''for''' {{nowrap|''p'' ≤ ''j'' ≤ ''r'' + ''p'' − ''i''}} '''do''' ''--loop3- Continue carrying'' ''x'' ← {{nowrap|''T''[''i'' + ''j''] + ''c''}} ''T''[''i'' + ''j''] ← {{nowrap|''x'' mod ''B''}} ''c'' ← {{nowrap|β''x'' / ''B''β}} '''end for''' '''end for''' '''for''' {{nowrap|0 ≤ ''i'' ≤ ''p''}} '''do''' ''S''[''i''] ← ''T''[''i'' + ''r''] '''end for''' '''if''' {{nowrap|''S'' ≥ ''N''}} '''then''' '''return''' {{nowrap|''S'' − ''N''}} '''else''' '''return''' {{var|S}} '''end if''' '''end function''' The final comparison and subtraction is done by the standard algorithms. The above algorithm is correct for essentially the same reasons that REDC is correct. Each time through the {{mvar|i}} loop, {{mvar|m}} is chosen so that {{math|''T''[''i''] + ''mN''[0]}} is divisible by {{mvar|B}}. Then {{mvar|mNB<sup>i</sup>}} is added to {{mvar|T}}. Because this quantity is zero mod {{mvar|N}}, adding it does not affect the value of {{math|''T'' mod ''N''}}. If {{mvar|m<sub>i</sub>}} denotes the value of {{mvar|m}} computed in the {{mvar|i}}th iteration of the loop, then the algorithm sets {{mvar|S}} to {{math|''T'' + (∑ ''m<sub>i</sub> B<sup>i</sup>'')''N''}}. Because MultiPrecisionREDC and REDC produce the same output, this sum is the same as the choice of {{mvar|m}} that the REDC algorithm would make. The last word of {{mvar|T}}, {{math|''T''[''r'' + ''p'']}} (and consequently {{math|''S''[''p'']}}), is used only to hold a carry, as the initial reduction result is bound to a result in the range of {{math|0 ≤ ''S'' < ''2N''}}. It follows that this extra carry word can be avoided completely if it is known in advance that {{math|''R'' ≥ ''2N''}}. On a typical binary implementation, this is equivalent to saying that this carry word can be avoided if the number of bits of {{mvar|N}} is smaller than the number of bits of {{mvar|R}}. Otherwise, the carry will be either zero or one. Depending upon the processor, it may be possible to store this word as a carry flag instead of a full-sized word. It is possible to combine multiprecision multiplication and REDC into a single algorithm. This combined algorithm is usually called Montgomery multiplication. Several different implementations are described by KoΓ§, Acar, and Kaliski.<ref>{{cite journal |author1=Γetin K. KoΓ§ |author2=Tolga Acar |author3=Burton S. Kaliski, Jr. |title=Analyzing and Comparing Montgomery Multiplication Algorithms |journal=[[IEEE Micro]] |date=June 1996 |volume=16 |number=3 |pages=26β33 |doi=10.1109/40.502403 |citeseerx=10.1.1.26.3120 |url=https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf}}</ref> The algorithm may use as little as {{math|''p'' + 2}} words of storage (plus a carry bit). As an example, let {{math|1=''B'' = 10}}, {{math|1=''N'' = 997}}, and {{math|1=''R'' = 1000}}. Suppose that {{math|1=''a'' = 314}} and {{math|1=''b'' = 271}}. The Montgomery representations of {{mvar|a}} and {{mvar|b}} are {{math|1=314000 mod 997 = 942}} and {{math|1=271000 mod 997 = 813}}. Compute {{math|1=942 β 813 = 765846}}. The initial input {{mvar|T}} to MultiPrecisionREDC will be [6, 4, 8, 5, 6, 7]. The number {{mvar|N}} will be represented as [7, 9, 9]. The extended Euclidean algorithm says that {{math|1=−299 β 10 + 3 β 997 = 1}}, so {{math|''N''′}} will be 7. i ← 0 m ← {{nowrap|1=6 β 7 mod 10 = 2}} j T c - ------- - 0 0485670 2 ''(After first iteration of first loop)'' 1 0485670 2 2 0485670 2 3 0487670 0 ''(After first iteration of second loop)'' 4 0487670 0 5 0487670 0 6 0487670 0 i ← 1 m ← {{nowrap|1=4 β 7 mod 10 = 8}} j T c - ------- - 0 0087670 6 ''(After first iteration of first loop)'' 1 0067670 8 2 0067670 8 3 0067470 1 ''(After first iteration of second loop)'' 4 0067480 0 5 0067480 0 i ← 2 m ← {{nowrap|1=6 β 7 mod 10 = 2}} j T c - ------- - 0 0007480 2 ''(After first iteration of first loop)'' 1 0007480 2 2 0007480 2 3 0007400 1 ''(After first iteration of second loop)'' 4 0007401 0 Therefore, before the final comparison and subtraction, {{math|1=''S'' = 1047}}. The final subtraction yields the number 50. Since the Montgomery representation of {{math|1=314 β 271 mod 997 = 349}} is {{math|1=349000 mod 997 = 50}}, this is the expected result. When working in base 2, determining the correct {{mvar|m}} at each stage is particularly easy: If the current working bit is even, then {{mvar|m}} is zero and if it's odd, then {{mvar|m}} is one. Furthermore, because each step of MultiPrecisionREDC requires knowing only the lowest bit, Montgomery multiplication can be easily combined with a [[carry-save adder]].
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)