mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2019-08-10, 04:38   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default Does ECM at yoyo@home exploit base-2 arithmetic?

Quote:
Originally Posted by VBCurtis View Post
It has stalled twice in the last week, so I would say same as ever.
A Query about the YoYo ECM trials:

Is the base 2 modular arithmetic optimization turned on?

Also note that one can optimize arithmetic for 2LM as well. Does GMP-ECM do this?
It is very worthwhile.

e.g. to reduce C mod (2^n-1) put C = A*2^n + B = A*2^n - A + B + A ==
(B + A) mod (2^n-1). 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.
R.D. Silverman is offline   Reply With Quote
Old 2019-08-10, 10:48   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·3·13·137 Posts
Default

Moved here a) because of a request and b) it is more appropriate here anyway.
xilman is offline   Reply With Quote
Old 2019-08-11, 12:31   #3
mathwiz
 
Mar 2019

7·23 Posts
Default

Is this equivalent to asking whether the GMP-ECM binary is built using gwnum?
mathwiz is offline   Reply With Quote
Old 2019-08-11, 12:46   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by mathwiz View Post
Is this equivalent to asking whether the GMP-ECM binary is built using gwnum?
Total Non-sequitur. I can't imagine why one might think my question about the internal
ALGORITHM has anything to do with how the code is compiled.
R.D. Silverman is offline   Reply With Quote
Old 2019-08-11, 14:08   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×13×137 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Total Non-sequitur. I can't imagine why one might think my question about the internal ALGORITHM has anything to do with how the code is compiled.
I find it quite easy to imagine how one might think that the implementation of the arithmetic library may be relevant to your question.

If you want an authoritative answer I suggest that you contact the GMP-ECM developers.
xilman is offline   Reply With Quote
Old 2019-08-11, 15:13   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by xilman View Post
I find it quite easy to imagine how one might think that the implementation of the arithmetic library may be relevant to your question.
The question was not about the implementation of the library. It was about the
*building* of the library.

Quote:
If you want an authoritative answer I suggest that you contact the GMP-ECM developers.
This would not tell us whether YoYo invokes the existing "-base2 n" option when it
distributes its wu's.

It is clear that GMP-ECM does not have an option to speed 2LM arithmetic.
R.D. Silverman is offline   Reply With Quote
Old 2019-08-11, 15:38   #7
mathwiz
 
Mar 2019

101000012 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Total Non-sequitur. I can't imagine why one might think my question about the internal
ALGORITHM has anything to do with how the code is compiled.
Because my understanding was that gwnum implemented the optimizations you were talking about? See also: https://www.mersenneforum.org/showthread.php?t=14485
mathwiz is offline   Reply With Quote
Old 2019-08-11, 15:45   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by mathwiz View Post
Because my understanding was that gwnum implemented the optimizations you were talking about? See also: https://www.mersenneforum.org/showthread.php?t=14485
You asked about how the code was *built*. You did not ask about how it was
implemented.

IT *does* implement fast 2^n-1 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.
R.D. Silverman is offline   Reply With Quote
Old 2019-08-11, 17:44   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×13×137 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This would not tell us whether YoYo invokes the existing "-base2 n" option when it distributes its wu's.
Fair enough. Why don't you ask yoyo directly?
xilman is offline   Reply With Quote
Old 2019-08-11, 18:15   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

16EE16 Posts
Default

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.
henryzz is online now   Reply With Quote
Old 2019-08-11, 18:50   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by xilman View Post
Fair enough. Why don't you ask yoyo directly?
Ignorance. I do not know who YoYo is.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P73 found by a yoyo@home user yoyo GMP-ECM 3 2017-11-08 15:20
larger B1 for GMP-ECM in yoyo@home yoyo GMP-ECM 41 2017-01-04 05:53
yoyo@home and wikipedia Dubslow Factoring 1 2015-12-06 15:56
Base-6 speed for prime testing vs. base-2 jasong Conjectures 'R Us 36 2010-08-03 06:25
New Linux Local Root Exploit tinhnho Linux 0 2005-01-17 05:48

All times are UTC. The time now is 07:55.

Tue May 18 07:55:10 UTC 2021 up 40 days, 2:36, 0 users, load averages: 2.39, 2.17, 1.89

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.