Talk:Montgomery modular multiplication

Untitled

I think the final paragraph of this article looks suspiciously similar to part of the Handbook of Applied Cryptography's section on Montgomery reduction (chapter 14, section 14.3.2) Being a newbie, I'm not sure what the "right thing" to do about this is. AJR 01:05, 18 Apr 2005 (UTC)

There are via boards that do this in hardware. But, how to mention it without making it sound like an advert? 09:54, 16 November 2006 (UTC)

What is the algorithm?

We state that this is an algorithm, yet don't state what the algorithm is. Can someone add this info? --Doradus 16:47, 19 October 2007 (UTC)

Restore "Formal Statement" and "Use In Cryptography" ?

The latest edit removed the "Formal Statement" and "Use In Cyptography" sections, both of which I found useful when trying to actually implement this. Is there any reason these sections should not be restored? Esmerel (talk) 22:17, 6 April 2008 (UTC) Also, the new version no longer explains that the advantage of the Montgomery method is that the intermediate results are kept small. SpeakerOfPictish (talk) 22:24, 6 April 2008 (UTC)

It seems to me that this is an old issue that has in the mean time now been RESOLVED (since at present, both of the mentioned sections are in existence in the article).

(I added this comment to make it easier to myself, while editing the article, to see at one glance which are the currently open issues, that I may have to take into account, and which are the already-resolved ones, that I can ignore.) --MRaccoon (talk) 11:05, 14 April 2015 (UTC)

Residues

"It can be easily shown that there is a one-to-one mapping between numbers $a,b,\cdots$ and residues ${\bar {a}},{\bar {b}},\cdots$."

This is wrong, since residues as they are defined are from the finite set [0..N-1], while the numbers a, b are arbitrary integers. I'll comment that out. Could someone clarify what was the point, or even better show it, since it was supposed to be easy? Remember, in math always expect a mistake after phrases like "it can be easily shown"/"obviously"/etc. — Preceding unsigned comment added by 134.206.11.222 (talk) 12:08, 28 May 2013 (UTC)

I suspect that what the writer meant was something like,

"When numbers $a,b,\cdots$ are from the finite set [0..N-1], there is a one-to-one mapping between those numbers and the residues ${\bar {a}},{\bar {b}},\cdots$."

Does this help us understand Montgomery reduction? --DavidCary (talk) 18:49, 29 January 2014 (UTC)

I agree with DavidCary, I think that the purpose must have been as he describes.

I think that for describing the Montgomery multiplication method, it is vitally important to explain that it is all about two different REPRESENTATIONS of the integers modulo N, namely on the one side the "normal, intuitive" one, and on the other side the "Montgomery representation". (The latter is the variables with the bars above them.) And it is likewise IMO also vitally important information that every "code point" in the one representation corresponds one-to-one with a "code point" in the other representation. So I think a sentence near that point that states that this one-to-one mapping exists is actually very helpful for the reader.

The proper way to improve the text on this issue is IMO not to simply remove a sentence (that is maybe awkwardly formulated), regardless of the function of the sentence in the flow or logic of the exposition. Instead, it'd be better IMO to put in clear definitions and terms up front, allowing the sentence to be formulated precisely. And thereby preserve the information instead of throwing it out. I.e. explain up front that we're talking about on the one hand the "intuitive" representation of the numbers modulo N (and introduce a good term for this representation), and on the other hand the Montgomery representation of these same numbers. (By the way, Montgomery in his 1983 article seems to informally use the less than ideal term "N-residue" for the "Montgomery representation", and seems to use the term "integers" for the "intuitive" representation.) --MRaccoon (talk) 12:44, 25 March 2015 (UTC)

Attacks on Montgomery modular multiplication

Attacks on Montgomery modular multiplication are different from attacks on modular exponentiation.

[4] and [6] has nothing to do with attacks on Montgomery modular multiplication. They are about attacks on modular exponentiation.

Hers is a paper which describes attack on Montgomery modular multiplication: https://www.cdc.informatik.tu-darmstadt.de/reports/TR/TI-04-02.pdf

And this is (one way) how to avoid it.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.3181&rep=rep1&type=pdf

Please correct the Wiki.

Thank you — Preceding unsigned comment added by 75.80.164.200 (talk) 18:08, 8 April 2014 (UTC)

Is this true?

This appears on the page. "To define multiplication, define the modular inverse of R, R^{-1} such that

   RR^{-1} \equiv 1 \pmod {N}

in other words

   RR^{-1} = kN + 1

where k is a positive integer. "

Does k have to be a positive integer? or just an integer? - either positive or negative? I mean it seems to be the case in most crypto appplications, but it is not true in general.

Good point. In the article, that phrase "where k is a positive integer" at that point seems only to throw up questions, and not to contribute information.

Taken on its own and out of the context of the article, the statement $A\equiv B{\pmod {N}}$ means of course that A = B + kN for any integer k.

However, Montgomery in his 1983 paper restricts k to be 0 < k < R. (He uses the notation N' for k.) And then in his description of the Redc() function he writes N' where the Wikipedia article uses $-N^{-1}$. I.e., Montgomery uses one and the same quantity (N') for what in the Wikipedia article as it is now is described as two independent quantities, k and $-N^{-1}$.

I suspect that the phrase "where k is a positive integer" could have originated from a somewhat literal "copying" of Montgomery's paper. Since the Wikipedia article doesn't use k in its definition of the Redc() function, I don't see how it matters in the "Rationale" section whether k is positive or not. The restriction of k = N' = $-N^{-1}$ to the interval 0 < N' < R seems to me irrelevant in the "Rationale" section, and seems to me not to contribute to that section. I'd propose that that interval restriction, if it's important at all and can not simply be left unspecified, better be moved to the section "Description of Algorithm" (and there be phrased in terms of $-N^{-1}$ and not k).

In the section "Rationale", the phrase "$RR^{-1}=kN+1$ where k is [a positive] integer" seems to have as its only function to put $RR^{-1}\equiv 1{\pmod {N}}$ in the form of the "Bezout's identity" theorem, which doesn't restrict the coefficient k to be positive. So I'd say that inside the section "Rationale" it would create a more understandable text if the phrase "where k is a positive integer" is replaced by "where k is any integer" or "an integer", or if it is left out altogether. --MRaccoon (talk) 19:08, 24 March 2015 (UTC)

Proposal: Change article title to "Montgomery multiplication"

I think that the title of the article should be changed from "Montgomery reduction" to "Montgomery multiplication".

One of the largest problems with this article is IMO the confusion between the following terms:

• Montgomery algorithm;
• The Redc() function (or algorithm);
• Montgomery step;
• Montgomery multiplication.

Clearly, Montgomery multiplication is the topic that the whole thing is about. The purpose of the Redc() function and all the Montgomery stuff is to speed up multiplication (without damaging other operations like addition). That the purpose is to speed up multiplication is also clear from Montgomery's 1983 paper (which is not only about the Redc() reduction function, but also about the complete fast multiplication design as a whole).

The Montgomery reduction -- i.e. the theoretical $TR^{-1}modN$ or its calculation via the Redc() algorithm -- is only a part of the Montgomery multiplication "package". (It is an important part, but it is only a part.) "Montgomery reduction" makes sense only as a part of Montgomery multiplication, as a "subroutine" inside the Montgomery multiplication "application". It is not an algorithm that you can take out of Montgomery multiplication and apply elsewhere.

To explain Montgomery reduction, you cannot avoid explaining Montgomery multiplication as a whole (as the article already does). So a logical and instructive exposition has to have as its scope: Montgomery multiplication as a whole. To make things easier to understand and follow for the reader (and to avoid instilling misunderstandings), this scope has to be reflected in the article title.

At present, the article explains both Montgomery multiplication and Montgomery reduction (which is entirely right). But it does so under the label of "Montgomery reduction". It is as if on the animal species of the Sardinian Dwarf Mammoth, there existed no article with the title "Sardinian Dwarf Mammoth", but only an article with the title "Intestines of the Sardinian Dwarf Mammoth", with the latter article explaining everything about this Mammoth, including its intestines, but also everything else. The article is about the whole, but the title confusingly gives the impression that the article is only about one part.

Incidentally: There is also confusion about the term "Montgomery algorithm". The subject matter includes TWO algorithms, inside each other. One is the Redc() algorithm, which is an inner subroutine, used inside the larger "Montgomery multiplication step" algorithm. Both of these are algorithms. To talk about "THE" Montgomery algorithm (unqualifiedly) is ambiguous and therefore confusing. The article should explicitly state this fact that the subject matter includes two algorithms (one inside the other), and should identify each of these two algorithms explicitly (and should use clear and unambiguous names for each of the two algorithms). --MRaccoon (talk) 22:14, 24 March 2015 (UTC)

This issue has now been RESOLVED. The article has been renamed, as discussed in Wikipedia_talk:WikiProject_Mathematics#Article_.22Montgomery_reduction.22:_Change_its_presentation_to_.22Montgomery_multiplication.22. I am currently in the process of rewriting the lead text. I will make sure that no information is lost by my edits. --MRaccoon (talk) 10:56, 14 April 2015 (UTC)

Error?

09:27, 29 October 2015 (UTC)~ Propose to correct carry in first iteration of first loop with example of Multiprecision Mont multply 210.75.225.12 (talk) 09:27, 29 October 2015 (UTC)

I suspect there are errors with carry value in the example to showcase "function MultiPrecisionREDC" "As an example, let B = 10, N = 997, and R = 1000. Suppose that a = 314 and b = 271. The Montgomery representations..., " "(After first iteration of first loop)", at least the first 3 carry, i.e. lower boundary of [x/B], should be [20/10]=2, rather than 1. Zeng,xuewen

It looks strange to me too, but I don't have time right now to check the whole loop. I will look at it more later. Or, if you think you know how to correct the example, you can edit the article yourself. Ozob (talk) 13:45, 29 October 2015 (UTC)

Many of the carries were wrong, but the rest of the computation appears to have been correct. I believe I have fixed the article. Please let me know if you encounter any more problems. Ozob (talk) 02:34, 30 October 2015 (UTC)