mersenneforum.org Idea about 10,000,000 digit attempt.
 Register FAQ Search Today's Posts Mark Forums Read

 2005-11-29, 04:43 #1 jasong     "Jason Goatcher" Mar 2005 66638 Posts Idea about 10,000,000 digit attempt. First let me say, I don't come here often, so if my idea is already used or been discussed please send me a PM about it and lock the thread. Anyhow, I didn't want to have to deal with Mr. Silverman, and I figured people in this forum would have a better idea about this than the regular math folks(mind you I've forgotten everything I've even learned about programming). But, as to my idea:I'm of the opinion that people are sieving and checking 2^n-1 in their attempt to collect the money(or simply be in the record books). But isn't it true that when it comes to LLR, when you do k*2^n-1, k's from 1 to 31 don't change the time taken much at all? So you would have 31 times as many opportunities for the same amount of work. Am I missing something?
2005-11-29, 05:22   #2
axn

Jun 2003

28×3×7 Posts

Quote:
 Originally Posted by jasong But, as to my idea:I'm of the opinion that people are sieving and checking 2^n-1 in their attempt to collect the money(or simply be in the record books). But isn't it true that when it comes to LLR, when you do k*2^n-1, k's from 1 to 31 don't change the time taken much at all? So you would have 31 times as many opportunities for the same amount of work.
I don't have any specific benchmarks, but I believe there is a significant speed difference between 2^n-1 and k*2^n-1, even for such small k's. Also k=1,2,4,8 and 16 belong to the 2^n-1 family only

2005-11-29, 11:23   #3

"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts

Quote:
 Originally Posted by jasong But isn't it true that when it comes to LLR, when you do k*2^n-1, k's from 1 to 31 don't change the time taken much at all?
Doesn't "don't change the time" apply to each individual k, rather than to all k collectively? That is, 3*2^n-1 takes the same time as 5*2^n-1, but not the same time as 3*2^n-1 AND 5*2^n-1 together.

Perhaps I'm overlooking something myself, but I think that, in general, sieving on 2^n-1 does not help factor 3*2^n-1 or 5*2^n-1 or any other k*2^n-1 with odd k.

Last fiddled with by cheesehead on 2005-11-29 at 11:25

2005-11-29, 15:59   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×5×373 Posts

Quote:
 Originally Posted by cheesehead Doesn't "don't change the time" apply to each individual k, rather than to all k collectively? That is, 3*2^n-1 takes the same time as 5*2^n-1, but not the same time as 3*2^n-1 AND 5*2^n-1 together. Perhaps I'm overlooking something myself, but I think that, in general, sieving on 2^n-1 does not help factor 3*2^n-1 or 5*2^n-1 or any other k*2^n-1 with odd k.
You are correct. Processing k*2^n - 1 for small odd k is just slightly slower
than 2^n-1. Reducing a product mod k*2^n-1 requires a single
multiplication of half of the product by k, followed by a subtraction.

But one must check eack k.

2005-11-29, 22:24   #5
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

2·32·439 Posts

Quote:
 Originally Posted by R.D. Silverman Reducing a product mod k*2^n-1 requires a single multiplication of half of the product by k, followed by a subtraction.
You can even use a DWT. This adds log2(k) bits per double. So for very small k, 2^n-1 and k*2^n-1 often use the same FFT length. That is, at equal speed to an LL test.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 8 2017-04-07 00:23 wildrabbitt Hardware 0 2016-05-22 17:22 jasong Lounge 29 2007-01-01 19:00 jasong Math 5 2006-06-07 10:39 JHansen Factoring 34 2005-05-27 19:24

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

Wed Jun 29 07:28:41 UTC 2022 up 76 days, 5:30, 1 user, load averages: 1.33, 1.10, 0.98