Idea about 10,000,000 digit attempt.

[jasong]

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?

[axn]

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

[cheesehead]

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.

[R.D. Silverman]

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.

[Prime95]

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.