• RSS
  • Twitter
  • FaceBook

Security Forums

Log in

FAQ | Search | Usergroups | Profile | Register | RSS | Posting Guidelines | Recent Posts

Infinite primes of the type q=2p+1?

Users browsing this topic:0 Security Fans, 0 Stealth Security Fans
Registered Security Fans: None
Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

View previous topic :: View next topic  
Author Message
Amitabh
Just Arrived
Just Arrived


Joined: 24 Aug 2004
Posts: 0
Location: Australia

Offline

PostPosted: Wed Dec 21, 2005 10:58 pm    Post subject: Infinite primes of the type q=2p+1? Reply with quote

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
View user's profile Send private message Visit poster's website
Groovicus
Trusted SF Member
Trusted SF Member


Joined: 19 May 2004
Posts: 9
Location: Centerville, South Dakota

Offline

PostPosted: Wed Dec 21, 2005 11:26 pm    Post subject: Reply with quote

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? Confused
Back to top
View user's profile Send private message Visit poster's website
Amitabh
Just Arrived
Just Arrived


Joined: 24 Aug 2004
Posts: 0
Location: Australia

Offline

PostPosted: Wed Dec 21, 2005 11:31 pm    Post subject: Reply with quote

I dont mean all primes are of this form but there are certainly some of them.. eg 23=2*11+1
Back to top
View user's profile Send private message Visit poster's website
Groovicus
Trusted SF Member
Trusted SF Member


Joined: 19 May 2004
Posts: 9
Location: Centerville, South Dakota

Offline

PostPosted: Wed Dec 21, 2005 11:56 pm    Post subject: Reply with quote

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. Very Happy
Back to top
View user's profile Send private message Visit poster's website
Amitabh
Just Arrived
Just Arrived


Joined: 24 Aug 2004
Posts: 0
Location: Australia

Offline

PostPosted: Thu Dec 22, 2005 12:17 am    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Groovicus
Trusted SF Member
Trusted SF Member


Joined: 19 May 2004
Posts: 9
Location: Centerville, South Dakota

Offline

PostPosted: Thu Dec 22, 2005 3:21 am    Post subject: Reply with quote

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 Razz
Back to top
View user's profile Send private message Visit poster's website
Amitabh
Just Arrived
Just Arrived


Joined: 24 Aug 2004
Posts: 0
Location: Australia

Offline

PostPosted: Thu Dec 22, 2005 7:07 am    Post subject: Reply with quote

I have a scheme that requires such primes. what is the best way to generate Sophie Germain primes ~ 100 digits?
Back to top
View user's profile Send private message Visit poster's website
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Thu Dec 22, 2005 5:18 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website Yahoo Messenger
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Sun Dec 25, 2005 10:22 am    Post subject: Reply with quote

Try this primality test for Sophie-Germain here.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
Display posts from previous:   

Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security All times are GMT + 2 Hours
Page 1 of 1


 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Community Area

Log in | Register