Safe Primes

[copperwindow]

Wikipedia claims that 7 is a safe prime. Can someone please explain to me how 7 is considered a safe prime?

[Dewey_Finn]

Wikipedia explains that a safe prime “is a prime number of the form 2p + 1, where p is also a prime.”

[copperwindow]

@Dewey_Finn

Wikipedia explains that a safe prime “is a prime number of the form 2p + 1, where p is also a prime.”

2x7+14. 14+1=15. 15 is not a prime number.

[Captain_Carrot]

@copperwindow

2x7+14. 14+1=15. 15 is not a prime number.

p is not 7. 7 is a prime of the form 2p+1. p=3, which is also a prime.

[Dewey_Finn]

I don’t think the article is saying that all numbers of the form 2p + 1 are prime numbers, just that those prime numbers that are of the form 2p + 1, where p is also a prime are safe primes.

[Henrichek]

@copperwindow

2x7+14. 14+1=15. 15 is not a prime number.

You got the idea backwards. 7 = 2p + 1 yields p = 3 which is prime, thus, 7 is a safe prime.

Edit: Beaten by 2 minutes

[Dahu]

@copperwindow

2x7+14. 14+1=15. 15 is not a prime number.

No but if p=3 (prime)
then 2x3=6 6+1=7

[j666]

So, what is the significance of safe primes?

[sailor]

@j666

So, what is the significance of safe primes?

Safe and Sophie Germain primes - Wikipedia

[ultrafilter]

@j666

So, what is the significance of safe primes?

It’s cryptography related. From the Wikipedia article:

These primes are called “safe” because of their relationship to strong primes. A prime number q is a strong prime if q+1 and q−1 both have large prime factors. The running times of some methods of factoring a number with q as a prime factor depend partly on the size of the prime factors of q−1. This is true, for instance, of the Pollard rho +1 and −1 methods. Although the most efficient known integer factorization methods do not depend on the size of the prime factors of q−1, this is nonetheless considered important in cryptography: for instance, the ANSI X9.31 standard mandates that strong primes be used for RSA moduli.

Safe primes are also important in cryptography because of their use in discrete logarithm-based techniques like Diffie-Hellman key exchange. If 2p+1 is a safe prime, the multiplicative group of numbers modulo 2p+1 has a subgroup of large prime order. It is usually this prime-order subgroup that is desirable, and the reason for using safe primes is so that the modulus is as small as possible relative to p.

Basically, a safe prime is suitable for use in cryptographic algorithms that are based on prime factorization.

[j666]

@ultrafilter

…
Basically, a safe prime is suitable for use in cryptographic algorithms that are based on prime factorization.

Thank you.

I read that quote four times, and I still don’t understand, but I now accept that safe primes do have some significance.

(Is there any way a better understanding of cryptographic principles will enhance my understanding of the universe or myself, or can I accept this gaping hole in my knowledge?)

[copperwindow]

@Henrichek

You got the idea backwards. 7 = 2p + 1 yields p = 3 which is prime, thus, 7 is a safe prime.

Edit: Beaten by 2 minutes

Getting mixed up safe primes with Sofie Jermain prime:smack:

[Derleth]

@j666

(Is there any way a better understanding of cryptographic principles will enhance my understanding of the universe or myself, or can I accept this gaping hole in my knowledge?)

I always thought number theory was beautiful in its own right, but if you insist on mere utility I shall give you an obol and send you read about the warning signs of cryptographic snakeoil. Schneier has it in a more conversational form, and he’s a good source of a lot more information about crypto as well.

[Sapo]

Is there a further category of “safer” primes?

Something like 2p+1 where p is a safe prime?

[Half_Man_Half_Wit]

@Sapo

Is there a further category of “safer” primes?

Something like 2p+1 where p is a safe prime?

Do you mean whether they exist or whether they have a separate name? If the former, then yes: 22 + 1 = 5, 25 + 1 = 11 (and we can even go one step further with 211 + 1 = 23); if a prime p is such that 2p + 1 is prime as well, it’s a Sophie Germain prime (as mentioned above), wikipedia tells me, so what you’re looking for are safe primes that are also Sophie Germain primes; strings of such consecutive nearly-doubled primes are called Cunningham chains.

[Sapo]

cool, yeah I meant with a name. The wiki entry is a bit over my head, but I think I got your explanation.

[copperwindow]

@Derleth

I always thought number theory was beautiful in its own right, but if you insist on mere utility I shall give you an obol and send you read about the warning signs of cryptographic snakeoil. Schneier has it in a more conversational form, and he’s a good source of a lot more information about crypto as well.

Wow, I am really glad you showed me these sites, ty!!!

[j666]

@Derleth

I always thought number theory was beautiful in its own right, but if you insist on mere utility …

I don’t think understanding the universe, or, for that matter, myself, is particularly useful; both will do what they do.

I will explore your links.