20190810, 04:38  #1  
Nov 2003
16444_{8} Posts 
Does ECM at yoyo@home exploit base2 arithmetic?
Quote:
Is the base 2 modular arithmetic optimization turned on? Also note that one can optimize arithmetic for 2LM as well. Does GMPECM do this? It is very worthwhile. e.g. to reduce C mod (2^n1) put C = A*2^n + B = A*2^n  A + B + A == (B + A) mod (2^n1). Thus, modular reduction only takes a shift and an add. For C mod (2^n+1) one gets B  A. to reduce C mod (2^x + 2^y + 1) put C = A*2^x + B. Now add and subtract A*2^y and add and subtract A: C = A*2^x + A*2^y + A + B 2^y A  A. Thus C mod (2^x + 2^y + 1) == B  A*2^y  A. This is much faster than Montgomery multiplication. 

20190810, 10:48  #2 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10100110010110_{2} Posts 
Moved here a) because of a request and b) it is more appropriate here anyway.

20190811, 12:31  #3 
Mar 2019
149 Posts 
Is this equivalent to asking whether the GMPECM binary is built using gwnum?

20190811, 12:46  #4 
Nov 2003
1D24_{16} Posts 

20190811, 14:08  #5  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10646_{10} Posts 
Quote:
If you want an authoritative answer I suggest that you contact the GMPECM developers. 

20190811, 15:13  #6  
Nov 2003
16444_{8} Posts 
Quote:
*building* of the library. Quote:
distributes its wu's. It is clear that GMPECM does not have an option to speed 2LM arithmetic. 

20190811, 15:38  #7  
Mar 2019
149 Posts 
Quote:


20190811, 15:45  #8  
Nov 2003
2^{2}·5·373 Posts 
Quote:
implemented. IT *does* implement fast 2^n1 and 2^n+1 modular reductions. But that does not tell us whether YoYo *invokes* the option. I specifically asked about YoYo's use. It does not seem to implement fast 2LM arithmetic. Indeed. Fast 2LM arithmetic can be generalized to fast modular reductions for any moduli with very low Hamming weight. 

20190811, 17:44  #9 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2·5,323 Posts 

20190811, 18:15  #10 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
1011011100001_{2} Posts 
I believe that it can autodetect that the base 2 code is needed. I don't know how good it is at that for cofactors.

20190811, 18:50  #11 
Nov 2003
2^{2}×5×373 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
P73 found by a yoyo@home user  yoyo  GMPECM  3  20171108 15:20 
larger B1 for GMPECM in yoyo@home  yoyo  GMPECM  41  20170104 05:53 
yoyo@home and wikipedia  Dubslow  Factoring  1  20151206 15:56 
Base6 speed for prime testing vs. base2  jasong  Conjectures 'R Us  36  20100803 06:25 
New Linux Local Root Exploit  tinhnho  Linux  0  20050117 05:48 