mersenneforum.org > Math Are all factors prime?
 Register FAQ Search Today's Posts Mark Forums Read

 2010-09-02, 17:48 #1 kurtulmehtap   Sep 2009 3610 Posts Are all factors prime? 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???
 2010-09-02, 18:05 #2 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 18EB16 Posts 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
2010-09-02, 18:15   #3
kurtulmehtap

Sep 2009

448 Posts

Quote:
 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?

2010-09-02, 18:26   #4
lavalamp

Oct 2007
Manchester, UK

2×3×223 Posts

Quote:
 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.

Last fiddled with by lavalamp on 2010-09-02 at 18:34

 2010-09-02, 19:51 #5 lavalamp     Oct 2007 Manchester, UK 24728 Posts You may be interested in this post made in the OBD project forum: http://www.mersenneforum.org/showpos...&postcount=429

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Math 14 2017-09-22 16:00 noodles YAFU 2 2017-05-12 14:00 devarajkandadai Miscellaneous Math 15 2012-05-29 13:18 Arkadiusz Factoring 6 2011-12-10 15:16 alpertron Math 0 2006-06-23 20:07

All times are UTC. The time now is 09:58.

Tue Jan 26 09:58:33 UTC 2021 up 54 days, 6:09, 0 users, load averages: 2.01, 2.00, 1.88