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

746010 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 2·3·13·137 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 7·23 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

11101001001002 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

2×3×13×137 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

22×5×373 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

101000012 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

1D2416 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×3×13×137 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) 16EE16 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

746010 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 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