mersenneforum.org Does ECM at yoyo@home exploit base-2 arithmetic?
 Register FAQ Search Today's Posts Mark Forums Read

2019-08-10, 04:38   #1
R.D. Silverman

Nov 2003

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

Quote:
 Originally Posted by VBCurtis 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.

 2019-08-10, 10:48 #2 xilman Bamboozled!     "πΊππ·π·π­" May 2003 Down not across 101001100101102 Posts Moved here a) because of a request and b) it is more appropriate here anyway.
 2019-08-11, 12:31 #3 mathwiz   Mar 2019 149 Posts Is this equivalent to asking whether the GMP-ECM binary is built using gwnum?
2019-08-11, 12:46   #4
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by mathwiz 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.

2019-08-11, 14:08   #5
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

1064610 Posts

Quote:
 Originally Posted by R.D. Silverman 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.

2019-08-11, 15:13   #6
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by xilman 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.

2019-08-11, 15:38   #7
mathwiz

Mar 2019

149 Posts

Quote:
 Originally Posted by R.D. Silverman 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.

2019-08-11, 15:45   #8
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
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

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.

2019-08-11, 17:44   #9
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2·5,323 Posts

Quote:
 Originally Posted by R.D. Silverman 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?

 2019-08-11, 18:15 #10 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 10110111000012 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.
2019-08-11, 18:50   #11
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by xilman Fair enough. Why don't you ask yoyo directly?
Ignorance. I do not know who YoYo is.

 Similar Threads Thread Thread Starter Forum Replies Last Post yoyo GMP-ECM 3 2017-11-08 15:20 yoyo GMP-ECM 41 2017-01-04 05:53 Dubslow Factoring 1 2015-12-06 15:56 jasong Conjectures 'R Us 36 2010-08-03 06:25 tinhnho Linux 0 2005-01-17 05:48

All times are UTC. The time now is 03:09.

Sat Apr 17 03:09:14 UTC 2021 up 8 days, 21:50, 0 users, load averages: 1.97, 2.23, 2.22

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.