Wheel factorization: Efficient?

[CRGreathouse]

Maybe we need to go in a different direction. sm88, suppose I gave you a prime p which I claimed was a Mersenne exponent. How would you prove that it was composite with your method? Feel free to give Pari code.

[science_man_88]

Originally Posted by CRGreathouse

Maybe we need to go in a different direction. sm88, suppose I gave you a prime p which I claimed was a Mersenne exponent. How would you prove that it was composite with your method? Feel free to give Pari code.

I don't have a code to prove that stuff yet but:

1) take (p-3)/2 to be the index to prove
2) use my sieve method (a formula linking this method to a proof for a index would be nice).

if it is shown to be eliminated it can't be prime if it isn't it MUST be prime.

one thing I found 24(85)+1 = 2047 prime it is found for 23 the bottom prime factor of that number.

so this eliminate some amount of checks.

[CRGreathouse]

Originally Posted by science_man_88

I don't have a code to prove that stuff yet but:

1) take (p-3)/2 to be the index to prove
2) use my sieve method (a formula linking this method to a proof for a index would be nice).

if it is shown to be eliminated it can't be prime if it isn't it MUST be prime.

So your idea is that, for a given exponent p, you have a set of divisors D such that if there is no d in D with d | (2^p - 1), 2^p - 1 is prime. (Presumably the breakthrough is that you can find a D that is much smaller than {3, 5, 7, 11, ..., sqrt(2^p)}.) Right?

[science_man_88]

Originally Posted by CRGreathouse

So your idea is that, for a given exponent p, you have a set of divisors D such that if there is no d in D with d | (2^p - 1), 2^p - 1 is prime. (Presumably the breakthrough is that you can find a D that is much smaller than {3, 5, 7, 11, ..., sqrt(2^p)}.) Right?

I must admit I know nothing of one part you are talking of:

d | (2^p - 1) <--have no idea what this means

well until I found out 24(85)+7 = 2047 and found with 23 I wasn't interested in factoring them at all actually.

[CRGreathouse]

Originally Posted by science_man_88

I must admit I know nothing of one part you are talking of

OK, so re-explain post #365. (My post was just trying to understand that post.) Try not to leave anything out.

Originally Posted by science_man_88

d | (2^p - 1) <--have no idea what this means

A number d divides 2^p - 1, that is, 2^p - 1 = kd for some integer k.

[3.14159]

Originally Posted by science_man_88

d | (2^p - 1) <--have no idea what this means

It means "d divides 2^p-1". Dammit, CRG beat me to it.

Originally Posted by CRGreathouse

So your idea is that, for a given exponent p, you have a set of divisors D such that if there is no d in D with d | (2^p - 1), 2^p - 1 is prime. (Presumably the breakthrough is that you can find a D that is much smaller than {3, 5, 7, 11, ..., sqrt(2^p)}.) Right?

It's impossible. Any prime can divide a Mersenne number. You would be forced to use the whole set of odd integers below the sqrt to ensure that it is prime. Trial division sucks because it's inefficient and slow. No amount of wishful or magical thinking changes this.

[science_man_88]

Originally Posted by CRGreathouse

OK, so re-explain post #365. (My post was just trying to understand that post.) Try not to leave anything out.



A number d divides 2^p - 1, that is, 2^p - 1 = kd for some integer k.

well basically what I was asking for is a pattern that can be used like every multiple of prime p is used in the sieve of Eratosthenes to sieve away a whole bunch of them, connected with the specific patterns.

if we find a way to sieve with it like this we can eliminate them like a sieve should without finding a factor though the first appearance of m is likely in the 2^p-1 possible factors which take the form 2kp+1.

of course in my idea's case it would hopefully be based on index and the index *2+3 is the prime exponent for the Mersenne prime.

[CRGreathouse]

Originally Posted by 3.14159

It's impossible. Any prime can divide a Mersenne number. You would be forced to use the whole set of odd integers below the sqrt to ensure that it is prime.

This is demonstrably false -- and not just in a trivial way. Do some experimentation on this.

Originally Posted by 3.14159

Trial division sucks because it's inefficient and slow. No amount of wishful or magical thinking changes this.

Yep, it's amazingly inefficient for this purpose, even though we *can* rule out large classes of primes as divisors.

[3.14159]

Originally Posted by science_man_88

well basically what I was asking for is a pattern that can be used like every multiple of prime p is used in the sieve of Eratosthenes to sieve away a whole bunch of them, connected with the specific patterns.

Mersenne numbers do not have any covering set of divisors. The divisors are random. So this sieve would be ineffective and useless.

Originally Posted by CRGreathouse

This is demonstrably false -- and not just in a trivial way. Do some experimentation on this.

Oh. Something about 2kp + 1 being the divisors of Mersenne numbers? This would shorten the divisions: But, what next? Divide by every single k possible before you find one? The Mersennes don't have any covering set of divisors.

[science_man_88]

(10:25) gp > for(p=5,30,for(n=1,20,if((6*n*p+p)%24==7 || (6*n*p-p)%24==7,print(floor((6*n*p-p)/24)","p))))
2,5
7,5
12,5
17,5
22,5
6,7
13,7
20,7
27,7
34,7
2,11
13,11
24,11
35,11
46,11
9,13
22,13
35,13
48,13
61,13
16,17
33,17
50,17
67,17
84,17
8,19
27,19
46,19
65,19
84,19
16,23
39,23
62,23
85,23
108,23
5,25
30,25
55,25
80,25
105,25
13,29
42,29
71,29
100,29
129,29

look at 5 for example starts at 2 in this case so c = 2 and adds p every time so it's p*x so the sequence fits 5x+2 we can tell what numbers follow this but can we link it to index of a number is the sequence if so then maybe we can find a pattern to show what indexes are wiped. if so we sieve them away.

[CRGreathouse]

Originally Posted by science_man_88

well basically what I was asking for is a pattern that can be used like every multiple of prime p is used in the sieve of Eratosthenes to sieve away a whole bunch of them

To what does "them" refer? For example, suppose you were trying to show that 2^696437724971 - 1 is composite; what are are "they" in this case?

Originally Posted by science_man_88

If we find a way to sieve with it like this we can eliminate them like a sieve should without finding a factor

If we can find a pattern (whatever that means) with certain unspecified properties, then you can eliminate... something... without finding a factor of the purported Mersenne prime.

Hmm... needs a lot of work.