mersenneforum.org > Math Montgomery powering
 Register FAQ Search Today's Posts Mark Forums Read

 2006-04-17, 15:33 #1 T.Rex     Feb 2004 France 11100100102 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((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.
 2006-04-17, 16:33 #3 T.Rex     Feb 2004 France 2×457 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 31·43 Posts I wrote an article on Mersenne Wiki about Montgomery multiplication. Maybe it can help you.
2006-04-17, 17:10   #5
T.Rex

Feb 2004
France

16228 Posts

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.

2006-04-17, 19:39   #6
axn

Jun 2003

22×32×131 Posts

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

2006-04-17, 19:57   #7
axn

Jun 2003

22×32×131 Posts

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)

 2006-04-17, 20:06 #8 alpertron     Aug 2002 Buenos Aires, Argentina 31·43 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 22×32×131 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 31×43 Posts I added the changes you wrote in you last post. Thanks.
2006-04-18, 06:57   #11
T.Rex

Feb 2004
France

2·457 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Computer Science & Computational Number Theory 3 2015-06-25 14:32 R.D. Silverman Factoring 8 2014-06-07 18:43 FactorEyes Factoring 23 2008-02-22 00:36 akruppa Hardware 1 2005-08-04 10:25 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