Factors for unique exponents?

[Dubslow]

I get the feeling there's a really simple answer to this, hence the forum. But, apparently if 2kp+1 is a factor of 2^p-1, it cannot be a factor of any other 2^q-1, q prime. I realize there are a ton of factors we know of, is there any way to automatically eliminate those in TF sieves? Just some database with all known factors. I also realize it would be hard to update clients, but a once a month check in could keep the files relatively up to date. (The speed up would be really really really small for each factor, so updates are not required often. On the other hand, between 0-50M, we know ~1-1.5 million factors...)

Mostly I just want a reality check, be I suspect this won't help. But best make sure.

[science_man_88]

http://www.mersenneforum.org/showthread.php?t=16019

it has been discussed before.

2*k*p+1
(2*k*p+1) mod 8= 1 or 7
(2*k*p+1) is prime ( aka if above 3, either 1 or 5 mod 6)

using this we can put conditions on k for a specific property of p.

[Dubslow]

Is it practical in any way to reduce TF work?

[Mini-Geek]

I seriously doubt it would provide a practical speedup. The cost of looking up whether a certain potential factor is a factor of any other Mersenne number, even if you were to store those ~1-1.5 million factors in memory, (or - to make it much better - only keep in memory the ones from the current bit level, or even a smaller portion. That would at least make the memory requirement closer to manageable) would probably be much higher than simply checking that factor. Then factor in that only primes of the form 2kpq+1 are possibilities for elimination, and it's looking even worse.
According to the Math page, the numbers are only sieved to about 40,000. I'd think it'd be quicker to sieve the numbers higher than to do a lookup in a huge table.

[Dubslow]

Cool, thanks guys.

[R.D. Silverman]

Originally Posted by Dubslow

I get the feeling there's a really simple answer to this, hence the forum. But, apparently if 2kp+1 is a factor of 2^p-1, it cannot be a factor of any other 2^q-1, q prime. I realize there are a ton of factors we know of, is there any way to automatically eliminate those in TF sieves? Just some database with all known factors. I also realize it would be hard to update clients, but a once a month check in could keep the files relatively up to date. (The speed up would be really really really small for each factor, so updates are not required often. On the other hand, between 0-50M, we know ~1-1.5 million factors...)

Mostly I just want a reality check, be I suspect this won't help. But best make sure.

I suggest that you study how TF is done now. Many of the trial factors
that are tested are not even prime. Think about why that is.

[science_man_88]

Originally Posted by R.D. Silverman

I suggest that you study how TF is done now. Many of the trial factors
that are tested are not even prime. Think about why that is.

I was thinking about something about why but it didn't make sense.

[Dubslow]

Originally Posted by R.D. Silverman

I suggest that you study how TF is done now. Many of the trial factors
that are tested are not even prime. Think about why that is.

Because a massive prime lookup table would be as bad as a massive "already a factor" table. (Right?)

[science_man_88]

Originally Posted by Dubslow

Because a massive prime lookup table would be as bad as a massive "already a factor" table. (Right?)

I was thinking composite = p*p etc. would allow a faster mod but that soon failed the logical test in my brain.

[Mr. P-1]

Originally Posted by science_man_88

I was thinking composite = p*p etc. would allow a faster mod but that soon failed the logical test in my brain.

Testing with composites is a waste of time. If Mp is divisable by a composite f, then it is divisable by the prime factors of f, and these will already have been found.

We nevertheless test some composites, because testing them to see if they are composite would take longer than testing to see if they divide Mp.

[TheJudger]

Originally Posted by Dubslow

I get the feeling there's a really simple answer to this, hence the forum. But, apparently if 2kp+1 is a factor of 2^p-1, it cannot be a factor of any other 2^q-1, q prime. I realize there are a ton of factors we know of, is there any way to automatically eliminate those in TF sieves? Just some database with all known factors. I also realize it would be hard to update clients, but a once a month check in could keep the files relatively up to date. (The speed up would be really really really small for each factor, so updates are not required often. On the other hand, between 0-50M, we know ~1-1.5 million factors...)

Mostly I just want a reality check, be I suspect this won't help. But best make sure.

For a given M_{[COLOR="Red"]p[/COLOR]}, how many of the 1-1.5 million known factors can be written as 2kp+1? For a p at the current TF wavefront (~54.000.000) I would say that the number is something near zero.

Oliver