View previous topic :: View next topic |
Author |
Message |
Amitabh Just Arrived
Joined: 24 Aug 2004 Posts: 0 Location: Australia
|
Posted: Wed Dec 21, 2005 10:58 pm Post subject: Infinite primes of the type q=2p+1? |
|
|
I think this is a known result. Are there infinite prime pairs (p, q) of the type q=2p+1 ?
Last edited by Amitabh on Sat Dec 24, 2005 12:41 pm; edited 1 time in total |
|
Back to top |
|
|
Groovicus Trusted SF Member
Joined: 19 May 2004 Posts: 9 Location: Centerville, South Dakota
|
Posted: Wed Dec 21, 2005 11:26 pm Post subject: |
|
|
2(7) +1 = 15..not prime at all..
2(13) + 1 = 27.. not prime..
Am I missing something in your question?Or are you asking if the list of primes generated by that combination is infinite?
|
|
Back to top |
|
|
Amitabh Just Arrived
Joined: 24 Aug 2004 Posts: 0 Location: Australia
|
Posted: Wed Dec 21, 2005 11:31 pm Post subject: |
|
|
I dont mean all primes are of this form but there are certainly some of them.. eg 23=2*11+1
|
|
Back to top |
|
|
Groovicus Trusted SF Member
Joined: 19 May 2004 Posts: 9 Location: Centerville, South Dakota
|
Posted: Wed Dec 21, 2005 11:56 pm Post subject: |
|
|
Not being a mathematics whiz, I would say that just by the two cases I presented, we are already at infinity minus 2, and if we continue with our series:
2(17) + 1 = 35
2(19) + 1 = 39
2(31) + 1 = 63
2(37) + 1 = 74
So out of the first 13 primes, 6 of them are themselves prime. If that pattern holds, then infinity divided by two is still infinity, so I would say the answer to your question is yes, although not every case.
Good question though.
|
|
Back to top |
|
|
Amitabh Just Arrived
Joined: 24 Aug 2004 Posts: 0 Location: Australia
|
Posted: Thu Dec 22, 2005 12:17 am Post subject: |
|
|
I think this would be a known result because DSA uses primes of this form.. they present interesting homomorphic structure.. since phi(phi(q))=phi(p)
UPDATE: From http://mathworld.wolfram.com/SophieGermainPrime.html
It is still an open question if there are infinite..
|
|
Back to top |
|
|
Groovicus Trusted SF Member
Joined: 19 May 2004 Posts: 9 Location: Centerville, South Dakota
|
Posted: Thu Dec 22, 2005 3:21 am Post subject: |
|
|
It is a question of semantics IMHO. If every prime fit the formula as you have given, then it would be an infinite series. I think that since it appears that roughly n/2 -1 actually form new primes, that it isn't an infinite series....
Alternatively though, in my previous example, even half of infinity is still infinity... I'm going to look a bit more, but I think that the question that is being asked is that after some period, no more primes are generated by following the formula. As far as I can see, that is sort of a BS question because questions with no finite limits can not be definatively solved...
Stuff that makes my head ache
|
|
Back to top |
|
|
Amitabh Just Arrived
Joined: 24 Aug 2004 Posts: 0 Location: Australia
|
Posted: Thu Dec 22, 2005 7:07 am Post subject: |
|
|
I have a scheme that requires such primes. what is the best way to generate Sophie Germain primes ~ 100 digits?
|
|
Back to top |
|
|
data Forum Fanatic
Joined: 08 May 2004 Posts: 16777211 Location: India
|
Posted: Thu Dec 22, 2005 5:18 pm Post subject: |
|
|
Any prime of the form 2k+1 is also of the form 4k+1. Look for primes p==1 mod 4, using any primality test.Yes ,100 digits is attainable, try Miller-Rabin.Less than 2-3 minutes on a reasonably fast desktop, if properly coded.
|
|
Back to top |
|
|
data Forum Fanatic
Joined: 08 May 2004 Posts: 16777211 Location: India
|
Posted: Sun Dec 25, 2005 10:22 am Post subject: |
|
|
Try this primality test for Sophie-Germain here.
|
|
Back to top |
|
|
|