Wheel factorization: Efficient?

[CRGreathouse]

Originally Posted by 3.14159

Oh. Something about 2kp + 1 being the smallest possible divisor?

That rules out prime divisors, but you can do *much* better than that.

[3.14159]

His sieve depends on a false idea: That the Mersenne numbers have a covering set of divisors. That is simply false. You would still have to do an endless search for divisors. Suppose you're trying to prove or disprove the primality of 2^56389762853-1. Would you search every single k from 1 to 10^16975010060?

[science_man_88]

Originally Posted by 3.14159

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



Oh. Something about 2kp + 1 being the smallest possible divisor?

from http://www.mersenne.org/various/math.php

"One very nice property of Mersenne numbers is that any factor q of 2P-1 must be of the form 2kp+1. Furthermore, q must be 1 or 7 mod 8. A proof is available. Finally, an efficient program can take advantage of the fact that any potential factor q must be prime."

[3.14159]

Originally Posted by science_man_88

"One very nice property of Mersenne numbers is that any factor q of 2P-1 must be of the form 2kp+1. Furthermore, q must be 1 or 7 mod 8. A proof is available. Finally, an efficient program can take advantage of the fact that any potential factor q must be prime."

Yes, but they do not have any covering set of divisors. This sieve is useless for any number larger than 20 digits.

[science_man_88]

Originally Posted by CRGreathouse

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?

them are indexes proven to hold composites

for 2^696437724971

p=696437724971
index = (p-3)/2

so if I can find out if index is eliminated as possibly prime without factoring by starting with the general equation 6np+/-p then I can prove without doubt if it's prime or not.

[CRGreathouse]

Originally Posted by science_man_88

look at 5 for example starts at 2 in this case so c = 2

I'm guessing that 5 is your p, that is, the exponent of your supposed Mersenne prime.

c, if your code is unerstood properly, starts at the smallest number C such that . You can get this rather more directly, if you like: just divide 7 by p, mod 24, add or subtract 1 as needed to make a multiple of 6, then divide by 6.

p=5;round(lift(Mod(7, 24)/p)/6)

Originally Posted by science_man_88

and adds p every time

So you're looking at the arithmetic sequence C, C+p, C+2p, ....

Originally Posted by science_man_88

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.

So you just constructed this without any idea of what to do with it?

[CRGreathouse]

Originally Posted by 3.14159

Yes, but they do not have any covering set of divisors. This sieve is useless for any number larger than 20 digits.

I said as much in post #371.

[CRGreathouse]

Originally Posted by 3.14159

His sieve depends on a false idea: That the Mersenne numbers have a covering set of divisors.

I don't think sm88 is suggesting that.

Edit: That is, I don't think that he is claiming that there is a *finite* set, which is what I assume you're claiming does not exist.

[science_man_88]

Originally Posted by CRGreathouse

I'm guessing that 5 is your p, that is, the exponent of your supposed Mersenne prime.

c, if your code is unerstood properly, starts at the smallest number C such that . You can get this rather more directly, if you like: just divide 7 by p, mod 24, add or subtract 1 as needed to make a multiple of 6, then divide by 6.

p=5;round(lift(Mod(7, 24)/p)/6)

So you're looking at the arithmetic sequence C, C+p, C+2p, ....



So you just constructed this without any idea of what to do with it?

no I have an idea just can't prove it. really all we have to do is prove if 6np+/-p can ever intercept 4n+1 and is that n a 4n+1 in the sequence if so the number is eliminated. but I wanted to use indexes.

[CRGreathouse]

Originally Posted by science_man_88

so if I can find out if index is eliminated as possibly prime without factoring by starting with the general equation 6np+/-p then I can prove without doubt if it's prime or not.

Ah. So your idea is that, if you find some way to tell if a Mersenne number is composite without factoring it, you'll be able to tell is Mersenne numbers are composite. Further, you think that some method may rely on the fact that composite Mersenne numbers are of the form .

[science_man_88]

Originally Posted by CRGreathouse

Ah. So your idea is that, if you find some way to tell if a Mersenne number is composite without factoring it, you'll be able to tell is Mersenne numbers are composite. Further, you think that some method may rely on the fact that composite Mersenne numbers are of the form .

is this the polite way of calling me an idiot if so I like it, hurts me a lot less.

look can you tell when 4x+1 = 6np+/-p ? if so is there a way to relate p with x so knowing a p we can prove if a x exist for that p in a quick manner if we can have a quick true false test for this we can figure this out.