20100902, 17:48  #1 
Sep 2009
100100_{2} 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??? 
20100902, 18:05  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
18EB_{16} Posts 
No. 256999 divides 2^291 and is 2*4431*29+1, but is 233*1103
in general the product of factors of a Mersenne number satisfies your condition 
20100902, 18:15  #3  
Sep 2009
44_{8} Posts 
Quote:
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? 

20100902, 18:26  #4  
Oct 2007
Manchester, UK
2·3·223 Posts 
Quote:
*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 20100902 at 18:34 

20100902, 19:51  #5 
Oct 2007
Manchester, UK
2×3×223 Posts 
You may be interested in this post made in the OBD project forum:
http://www.mersenneforum.org/showpos...&postcount=429 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Checking that there are no prime factors up to x  CRGreathouse  Math  14  20170922 16:00 
Finding prime factors for 133bit number  noodles  YAFU  2  20170512 14:00 
Mersenne prime factors of very large numbers  devarajkandadai  Miscellaneous Math  15  20120529 13:18 
Prime factors of googolplex  10.  Arkadiusz  Factoring  6  20111210 15:16 
Distribution of Mersenne prime factors mod 6  alpertron  Math  0  20060623 20:07 