Factors for unique exponents?
 

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.

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

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.

Is it practical in any way to reduce TF work?

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 [URL="http://www.mersenne.org/various/math.php"]the Math[/URL] 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.

Cool, thanks guys.

[QUOTE=Dubslow;274547]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.[/QUOTE]

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.

[QUOTE=R.D. Silverman;274618]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.[/QUOTE]

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

[QUOTE=R.D. Silverman;274618]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.[/QUOTE]
Because a massive prime lookup table would be as bad as a massive "already a factor" table. (Right?)

[QUOTE=Dubslow;274668]Because a massive prime lookup table would be as bad as a massive "already a factor" table. (Right?)[/QUOTE]

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

[QUOTE=science_man_88;274677]I was thinking composite = p*p etc. would allow a faster mod but that soon failed the logical test in my brain.[/QUOTE]

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.

[QUOTE=Dubslow;274547]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.[/QUOTE]

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

Oliver