20060417, 15:33  #1 
Feb 2004
France
1110010010_{2} 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 447450, and I fail with my example. Let: . So: . As explained in the book, I've computed:. I want to compute: , with: . I'm now using Th 9.2.6 based on (9.7): . The binary bits of y are:. Step 1 (Initialize): Step 2 (Power ladder): j=1 : j=0 : Step 3 (Final extraction of power): 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 exists for : 7, 73, 262657, ... Thanks, Tony Last fiddled with by T.Rex on 20060417 at 15:37 
20060417, 16:24  #2 
Feb 2004
France
2×457 Posts 
A small mistake: . 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) So, the last Step is now: , which still is wrong ... T. 
20060417, 16:33  #3 
Feb 2004
France
2×457 Posts 
And another mistake in the text (but the value of N' is OK): .
T. 
20060417, 16:42  #4 
Aug 2002
Buenos Aires, Argentina
31·43 Posts 
I wrote an article on Mersenne Wiki about Montgomery multiplication. Maybe it can help you.

20060417, 17:10  #5  
Feb 2004
France
1622_{8} Posts 
Quote:
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 : 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. 

20060417, 19:39  #6  
Jun 2003
2^{2}×3^{2}×131 Posts 
Quote:
I hope I am making some sense 

20060417, 19:57  #7  
Jun 2003
2^{2}×3^{2}×131 Posts 
Quote:
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) 

20060417, 20:06  #8 
Aug 2002
Buenos Aires, Argentina
31·43 Posts 
I corrected the formulas (there were some errors) and I also included your example with a stepbystep solution. Please see the new version of the MersenneWiki page.

20060417, 20:34  #9 
Jun 2003
2^{2}×3^{2}×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. 
20060417, 20:44  #10 
Aug 2002
Buenos Aires, Argentina
31×43 Posts 
I added the changes you wrote in you last post. Thanks.

20060418, 06:57  #11  
Feb 2004
France
2·457 Posts 
Quote:
Tony 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Peter Montgomery's Thesis  mickfrancis  Computer Science & Computational Number Theory  3  20150625 14:32 
Peter Montgomery (IMPORTANT)  R.D. Silverman  Factoring  8  20140607 18:43 
BrentMontgomeryte Riele numbers  FactorEyes  Factoring  23  20080222 00:36 
VIA C7 Montgomery Multiplier?  akruppa  Hardware  1  20050804 10:25 
Montgomery Multiplication  dave_dm  Math  2  20041224 11:00 