mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-04-17, 15:33   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

11100100102 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2006-04-17, 16:24   #2
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2×457 Posts
Default

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 is offline   Reply With Quote
Old 2006-04-17, 16:33   #3
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2×457 Posts
Default

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

T.
T.Rex is offline   Reply With Quote
Old 2006-04-17, 16:42   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

31·43 Posts
Default

I wrote an article on Mersenne Wiki about Montgomery multiplication. Maybe it can help you.
alpertron is offline   Reply With Quote
Old 2006-04-17, 17:10   #5
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16228 Posts
Default

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.
T.Rex is offline   Reply With Quote
Old 2006-04-17, 19:39   #6
axn
 
axn's Avatar
 
Jun 2003

22×32×131 Posts
Default

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 is offline   Reply With Quote
Old 2006-04-17, 19:57   #7
axn
 
axn's Avatar
 
Jun 2003

22×32×131 Posts
Default

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)
axn is offline   Reply With Quote
Old 2006-04-17, 20:06   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

31·43 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2006-04-17, 20:34   #9
axn
 
axn's Avatar
 
Jun 2003

22×32×131 Posts
Default

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.
axn is offline   Reply With Quote
Old 2006-04-17, 20:44   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

31×43 Posts
Default

I added the changes you wrote in you last post. Thanks.
alpertron is offline   Reply With Quote
Old 2006-04-18, 06:57   #11
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·457 Posts
Default

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
T.Rex is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 23:39.

Wed Oct 28 23:39:18 UTC 2020 up 48 days, 20:50, 1 user, load averages: 1.48, 1.56, 1.69

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.