Are all factors prime?

[kurtulmehtap]

If P divides 2^q -1 and P is in the form 2kq +1, is P definitely a prime?
If yes, is this not another primality test???

[fivemack]

No. 256999 divides 2^29-1 and is 2*4431*29+1, but is 233*1103

in general the product of factors of a Mersenne number satisfies your condition

[kurtulmehtap]

Originally Posted by fivemack

No. 256999 divides 2^29-1 and is 2*4431*29+1, but is 233*1103

in general the product of factors of a Mersenne number satisfies your condition

Yes, but 233 and 1103 are in the form of 2kq + 1 and are primes.
So if we start from k=1 and check if 2kq +1 divides 2^q -1, then will we get a prime? ( a sophie germain prime).
Can this be a primality test to find Sophie Germain primes?

[lavalamp]

Originally Posted by kurtulmehtap

Yes, but 233 and 1103 are in the form of 2kq + 1 and are primes.
So if we start from k=1 and check if 2kq +1 divides 2^q -1, then will we get a prime? ( a sophie germain prime).
Can this be a primality test to find Sophie Germain primes?

If you are checking values for k in order, and you find a factor of 2^p - 1, then yes, you can be sure* that the factor is prime. Providing you either didn't find any smaller factors before it, or if you did, that this new factor isn't divisible by any of those smaller factors.

*Of course, if at any point your CPU made a mistake and missed a factor, it might not be prime.

Generally there are much faster methods for primality testing of numbers, rather than simply trial dividing, even though in this case you know a potential factor must be of a certain form. While it would be pretty quick to trial divide up to the square root of the potentially prime factor, it would still be even quicker to run a primality test on it. For the size of the factors found with trial division, a few prp tests or even a full deterministic primality test wouldn't even take a millisecond.

[lavalamp]

You may be interested in this post made in the OBD project forum:
http://www.mersenneforum.org/showpos...&postcount=429