# What happens if no final subtraction is done in Montgomery multiplication?

I'm doing Montgomery arithmetic modulo $N = 2^{255}-19$ for the Curve25519, picking $R = 2^{256}$ for Montgomery.

After multiplying two numbers $0 \leq A,B < N$ in the Montgomery representation using MonMul, I would normally obtain the result $0 \leq C < N$ also in the Montgomery representation.

However, if I forget the conditional subtraction in MonMul I obtain some $0 \leq C^{\prime} < 2N$. In other words, I basically ended up in a different representation which is not unique anymore.

I could live with that and do all the additions/subtractions modulo $2^{256}-38$ instead afterwards. That means I basically postponed the conditional subtraction until the end of my whole computation.

But my question is what happens if I have to do MonMul again somewhere during my computation? It would mean that one (or both) of the input numbers for MonMul could be in fact between $N$ and $2N$.

Do I have to make the conditional subtraction before doing the MonMul again (to put my numbers back in the right representation)? Or can I still postpone it until the end? I realized that not doing the subtraction before any repeated multiplication didn't spoil the computation so far. Does it really hold universally for my $N$?

• Stupid question: why are you using Montgomery Multiplication for $2^{255}-19$ in the first place? The reason we do Montgomery Multiplication is to make the modulo operation easier; however with $N=2^{255}-19$, it's already awfully easy, as $a \cdot 2^{255} + b \equiv a \cdot 19 + b \pmod{2^{255}-19}$ Jun 29 '15 at 17:54
• I expected that question :) Because Montgomery multiplication saves me some code memory which I am optimizing for. Doing A*B and then doing the full reduction using what you just said requires far more code than for example CIOS Montgomery multiplication. Jun 29 '15 at 17:56
• @NumberFour, as Poncho pointed out, the reduction process is obvious for this modulus format. Observe that $A \star B \; mod \; N \simeq \; A \star \; B \; - \; [High(A\star \;B)]\star N$. And this can also be optimised, without going to Montgomery arithmetic which necessitate additionnal pre and post process. Jun 30 '15 at 16:35
• I was already experimenting with all that. I am doing a specific implementation for a device with very restricted instruction set. For some reasons, I cannot optimize for speed but for code size and memory consumed. Montgomery comes out with least code size and memory requirements. Also the pre- and post- processing comes for free (in terms of extra memory) since MonPro could be used for this purpose as well. Jun 30 '15 at 17:23
• I don't expect your algorithm to work without exceptions. You mentioned result is below $2N$, so try to square, through montgomery multiplication, $2N-1$ and see if the result is above $2N$. Note, don't convert anything into/from montgomery, just compute MonMul(2N-1,2N-1). Jul 1 '15 at 8:51

Theorem 2 in [Dussé et al. 1991] states that, if we skip the final subtraction, then, for $$N < R / 4$$ and $$0 \leq A, B < 2 N$$, we have $$0 \leq C = \text{MonMul}(A B) < 2 N$$, while keeping $$C \equiv A B R^{-1} \pmod N$$. I think the condition $$N < R / 4$$ inherently holds in your case e.g. you are using larger $$R$$ value acutually.