Montgomery powering

T.Rex · 2006-04-17, 15:33

Hello,
I'm reading "Prime Numbers, A Computational Perspective, 2nd Edition" and I'm experimenting with the "Montgomery powering" explained in pages 447-450, and I fail with my example.

Let: $N=5, \ R=2^3, \ s=3, \ x=3, \ y=2$ . So: $R>N$ .

As explained in the book, I've computed: $N^{-1}=5 \ \pmod{R} , \ N'=(-R^{-1}) \ \pmod{8} = 3, \ R^{-1}=2 \ \pmod{8}$ .
I want to compute: $x^y \ \pmod{N}$ , with: $x=3, \ y=2$ .
I'm now using Th 9.2.6 based on (9.7): $y/R = (x+N \cdot ((x \cdot N')\&(R-1))) \gg s$ .

The binary bits of y are: $(1,0)$ .

Step 1 (Initialize):
$\overline{x}=(xR) \ \pmod{N} = (3 \cdot 8) \ \pmod{5} = 4$
$\overline{p}=R \ \pmod{N} = 8 \ \pmod{5} = 3$

Step 2 (Power ladder):
j=1 : $y_1=0 : \ \overline{p}=M(\overline{p},\overline{p})=M(3,3)=(9+5 \cdot ((9 \cdot 3 ) \& 7))) \gg 3 = 3$
j=0 : $y_0=1 : \ \overline{p}=M(\overline{p},\overline{p})=M(3,3)=3$ $\overline{p}=M(\overline{p},\overline{x})=M(3,4)=(12+5 \cdot ((12 \cdot 3)\& 7))) \gg 3 = 1$

Step 3 (Final extraction of power):
$M(\overline{p},1) = M(1,1)=(1+5 \cdot ((1 \cdot 3) \& 7))) \gg 3 = 2$

I expected to find 4 instead of 2.

OK, I'm wrong. Where ?

(In my opinion, a numerical example would help in the book ...).

My final goal is to search if a faster $x^2 \ \pmod{N}$ exists for $N = 4^3^n + 2^3^n + 1$ : 7, 73, 262657, ...

Thanks,
Tony

T.Rex · 2006-04-17, 16:24

A small mistake: $R^{-1}= 2 \ \pmod{5}$ . but this is not used.

I've used PARI/gp to check:

Code:

M(a,b)=shift((a*b+5*bitand(a*b*3,7))),-3)

and I've found another mistake: $M(3,4)=(12+5 \cdot ((12 \cdot 3)\& 7))) \gg 3 = 4$ . Not 1.

So, the last Step is now: $M(4,1)=(4+5 \cdot ((4 \cdot 3)\& 7))) \gg 3 = 3$ , which still is wrong ...

T.

T.Rex · 2006-04-17, 16:33

And another mistake in the text (but the value of N' is OK): $N'=(-N^{-1}) \ \pmod{R} = -5 \ \pmod{8} = 3$ .

T.

alpertron · 2006-04-17, 16:42

I wrote an article on Mersenne Wiki about Montgomery multiplication. Maybe it can help you.

T.Rex · 2006-04-17, 17:10

Quote:

Originally Posted by alpertron

I wrote an article on Mersenne Wiki about Montgomery multiplication. Maybe it can help you.

Thanks !
But I have problems with your Wiki explanations.
With: m=5 , n=3 , a=b = 3 , I have:
R=5 , 1/8 mod 5 = 2
a' = 8.3 (mod 5) = 4
x = a' . b' (mod 5) = 1
And I do not understand why you recompute m : $m = (x \,\bmod{2^n})R\,\bmod{2^n}$
Using m=5, I have a problem with: t = (x + mR)/(2^n) = (1+5.5)/8 = 26/8 . Not an integer ...
A mistake ?
T.

axn · 2006-04-17, 19:39

Quote:

Originally Posted by T.Rex

Step 2 (Power ladder):
j=1 : $y_1=0 : \ \overline{p}=M(\overline{p},\overline{p})=M(3,3)=(9+5 \cdot ((9 \cdot 3 ) \& 7))) \gg 3 = 3$
j=0 : $y_0=1 : \ \overline{p}=M(\overline{p},\overline{p})=M(3,3)=3$ $\overline{p}=M(\overline{p},\overline{x})=M(3,4)=(12+5 \cdot ((12 \cdot 3)\& 7))) \gg 3 = 1$

Hmmm... I think the problem is with exponentiation logic rather than the montgomery reduction. Since you are computing 3^2 = 3*3 (mod 5), at some point you should have a step of M(4,4) [since 4 = 3R (mod N)]. Instead you have M(3,3) which is equivalent to 1*1 (mod 5) and M(3,4) which is equivalent of 1*3 (mod 5).

I hope I am making some sense

axn · 2006-04-17, 19:57

Quote:

Originally Posted by T.Rex

Thanks !
But I have problems with your Wiki explanations.
With: m=5 , n=3 , a=b = 3 , I have:
R=5 , 1/8 mod 5 = 2
a' = 8.3 (mod 5) = 4
x = a' . b' (mod 5) = 1
And I do not understand why you recompute m : $m = (x \,\bmod{2^n})R\,\bmod{2^n}$
Using m=5, I have a problem with: t = (x + mR)/(2^n) = (1+5.5)/8 = 26/8 . Not an integer ...
A mistake ?
T.

Looks like there are some issues with the wiki explanation.

First, R should be the negative of modular inverse of M.

Second, x = a' * b' (mod m) should be just plain x = a' * b'.

Third, m = (x mod 2^n)*R mod 2^n is confusing since it redefines m. m shouldn't change throughout the computation. Let's call that one m'.

Then the next line becomes t = (x + m*m')/(2^n)

alpertron · 2006-04-17, 20:06

I corrected the formulas (there were some errors) and I also included your example with a step-by-step solution. Please see the new version of the MersenneWiki page.

axn · 2006-04-17, 20:34

The third step should use 'm' instead of 'R' -- i.e. t = (x + s.m)/2^n

Also, the second step is defined as x*R mod 2^n with R itself defined as -m^-1 (mod 2^n). This way, the whole computation just uses unsigned multiplication.

alpertron · 2006-04-17, 20:44

I added the changes you wrote in you last post. Thanks.

T.Rex · 2006-04-18, 06:57

Quote:

Originally Posted by axn1

Hmmm... I think the problem is with exponentiation logic rather than the montgomery reduction. ... I hope I am making some sense

Thanks. I'll print all that thread and I'll quietly reread and recompute everything. At least, this has helped to improve the Wiki. I'll reread it also, to compare with the book.
Tony

2006-04-17, 15:33	#1
T.Rex Feb 2004 France 914₁₀ Posts	Montgomery powering Hello, I'm reading "Prime Numbers, A Computational Perspective, 2nd Edition" and I'm experimenting with the "Montgomery powering" explained in pages 447-450, and I fail with my example. Let: $N=5, \ R=2^3, \ s=3, \ x=3, \ y=2$ . So: $R>N$ . As explained in the book, I've computed: $N^{-1}=5 \ \pmod{R} , \ N'=(-R^{-1}) \ \pmod{8} = 3, \ R^{-1}=2 \ \pmod{8}$ . I want to compute: $x^y \ \pmod{N}$ , with: $x=3, \ y=2$ . I'm now using Th 9.2.6 based on (9.7): $y/R = (x+N \cdot ((x \cdot N')\&(R-1))) \gg s$ . The binary bits of y are: $(1,0)$ . Step 1 (Initialize): $\overline{x}=(xR) \ \pmod{N} = (3 \cdot 8) \ \pmod{5} = 4$ $\overline{p}=R \ \pmod{N} = 8 \ \pmod{5} = 3$ Step 2 (Power ladder): j=1 : $y_1=0 : \ \overline{p}=M(\overline{p},\overline{p})=M(3,3)=(9+5 \cdot ((9 \cdot 3 ) \& 7))) \gg 3 = 3$ j=0 : $y_0=1 : \ \overline{p}=M(\overline{p},\overline{p})=M(3,3)=3$ $\overline{p}=M(\overline{p},\overline{x})=M(3,4)=(12+5 \cdot ((12 \cdot 3)\& 7))) \gg 3 = 1$ Step 3 (Final extraction of power): $M(\overline{p},1) = M(1,1)=(1+5 \cdot ((1 \cdot 3) \& 7))) \gg 3 = 2$ I expected to find 4 instead of 2. OK, I'm wrong. Where ? (In my opinion, a numerical example would help in the book ...). My final goal is to search if a faster $x^2 \ \pmod{N}$ exists for $N = 4^3^n + 2^3^n + 1$ : 7, 73, 262657, ... Thanks, Tony Last fiddled with by T.Rex on 2006-04-17 at 15:37

2006-04-17, 16:24	#2
T.Rex Feb 2004 France 2·457 Posts	A small mistake: $R^{-1}= 2 \ \pmod{5}$ . but this is not used. I've used PARI/gp to check: Code: M(a,b)=shift((ab+5bitand(ab3,7))),-3) and I've found another mistake: $M(3,4)=(12+5 \cdot ((12 \cdot 3)\& 7))) \gg 3 = 4$ . Not 1. So, the last Step is now: $M(4,1)=(4+5 \cdot ((4 \cdot 3)\& 7))) \gg 3 = 3$ , which still is wrong ... T.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Peter Montgomery's Thesis	mickfrancis	Computer Science & Computational Number Theory	3	2015-06-25 14:32
Peter Montgomery (IMPORTANT)	R.D. Silverman	Factoring	8	2014-06-07 18:43
Brent-Montgomery-te Riele numbers	FactorEyes	Factoring	23	2008-02-22 00:36
VIA C7 Montgomery Multiplier?	akruppa	Hardware	1	2005-08-04 10:25
Montgomery Multiplication	dave_dm	Math	2	2004-12-24 11:00

2006-04-17, 16:33	#3
T.Rex Feb 2004 France 914₁₀ Posts	And another mistake in the text (but the value of N' is OK): $N'=(-N^{-1}) \ \pmod{R} = -5 \ \pmod{8} = 3$ . T.

2006-04-17, 16:42	#4
alpertron Aug 2002 Buenos Aires, Argentina 17·79 Posts	I wrote an article on Mersenne Wiki about Montgomery multiplication. Maybe it can help you.

2006-04-17, 20:06	#8
alpertron Aug 2002 Buenos Aires, Argentina 17·79 Posts	I corrected the formulas (there were some errors) and I also included your example with a step-by-step solution. Please see the new version of the MersenneWiki page.

2006-04-17, 20:34	#9
axn Jun 2003 4,861 Posts	The third step should use 'm' instead of 'R' -- i.e. t = (x + s.m)/2^n Also, the second step is defined as x*R mod 2^n with R itself defined as -m^-1 (mod 2^n). This way, the whole computation just uses unsigned multiplication.

2006-04-17, 20:44	#10
alpertron Aug 2002 Buenos Aires, Argentina 17·79 Posts	I added the changes you wrote in you last post. Thanks.