mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2010-09-02, 17:48   #1
kurtulmehtap
 
Sep 2009

22×32 Posts
Default 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???
kurtulmehtap is offline   Reply With Quote
Old 2010-09-02, 18:05   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·3,191 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2010-09-02, 18:15   #3
kurtulmehtap
 
Sep 2009

3610 Posts
Default

Quote:
Originally Posted by fivemack View Post
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?
kurtulmehtap is offline   Reply With Quote
Old 2010-09-02, 18:26   #4
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

24748 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
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
lavalamp is offline   Reply With Quote
Old 2010-09-02, 19:51   #5
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

24748 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Checking that there are no prime factors up to x CRGreathouse Math 14 2017-09-22 16:00
Finding prime factors for 133bit number noodles YAFU 2 2017-05-12 14:00
Mersenne prime factors of very large numbers devarajkandadai Miscellaneous Math 15 2012-05-29 13:18
Prime factors of googolplex - 10. Arkadiusz Factoring 6 2011-12-10 15:16
Distribution of Mersenne prime factors mod 6 alpertron Math 0 2006-06-23 20:07

All times are UTC. The time now is 05:04.

Mon Mar 1 05:04:01 UTC 2021 up 88 days, 1:15, 0 users, load averages: 1.81, 1.83, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.