Safe prime: Difference between revisions

Latest revision as of 22:11, 2 January 2012

This article defines a property that can be evaluated for a prime number. In other words, every prime number either satisfies this property or does not satisfy this property.
View other properties of prime numbers | View other properties of natural numbers

Definition

A prime number $p$ is termed a safe prime if $p$ is odd and $(p-1)/2$ is also a prime number.

The corresponding prime $(p-1)/2$ is termed a Sophie Germain prime.

Occurrence

Initial values

The ID of the sequence in the Online Encyclopedia of Integer Sequences is A005385

The first few safe primes are:

5, 7, 11, 23, 47, 59, 83, 107, 167, [SHOW MORE]

View list on OEIS

The first few primes that are not safe primes are: 2, 3, 13, 17, 19.

Density in primes

Cutoff $n$	Number of primes $\leq n$	Number of safe primes $\leq n$	Proportion of primes that are safe primes
10	4	2	$1/2=0.5$
100	25	7	$7/25=0.28$
1000	168	24	$25/168\approx 0.15$

Relation with other properties

Related properties of primes or pairs of primes

Sophie Germain prime is a prime $q$ such that $2q+1$ is also a prime.
Twin primes are primes that differ by two.

Related properties of longer chains of primes

Cunningham chain of the first kind is a chain of primes $q_{1}<q_{2}<\dots <q_{k}$ such that $q_{i+1}=2q_{i}+1$ .
Bitwin chain is a collection of multiple pairs of twin primes, each pair being double the previous one.

Facts

@@ Line 6: / Line 6: @@
 The corresponding prime <math>(p-1)/2</math> is termed a [[defining ingredient::Sophie Germain prime]].
+==Occurrence==
+===Initial values===
+{{oeis|A005385}}
+The first few safe primes are:
+<section begin="list"/>[[5]], [[7]], [[11]], [[23]], [[47]], [[59]], [[83]], [[107]], [[167]], <toggledisplay>179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2039, 2063, 2099, 2207, 2447, 2459, 2579, 2819, 2879, 2903</toggledisplay>[[Oeis:A005385|View list on OEIS]]<section end="list"/>
+The first few primes that are ''not'' safe primes are: 2, 3, 13, 17, 19.
+===Density in primes===
+{| class="wikitable" border="1"
+! Cutoff <math>n</math> !! Number of primes <math>\le n</math> !! Number of safe primes <math>\le n</math> !! Proportion of primes that are safe primes
+|-
+| 10 || 4 || 2 || <math>1/2 = 0.5</math>
+|-
+| 100 || 25 ||  7 || <math>7/25 = 0.28</math>
+|-
+| 1000 || 168 || 24 || <math>25/168 \approx 0.15</math>
+|}
+==Relation with other properties==
+===Related properties of primes or pairs of primes===
+* [[Sophie Germain prime]] is a prime <math>q</math> such that <math>2q + 1</math> is also a prime.
+* [[Twin primes]] are primes that differ by two.
+===Related properties of longer chains of primes===
+* [[Cunningham chain of the first kind]] is a chain of primes <math>q_1 < q_2 < \dots < q_k</math> such that <math>q_{i+1} = 2q_i + 1</math>.
+* [[Bitwin chain]] is a collection of multiple pairs of twin primes, each pair being double the previous one.
+==Facts==
+* [[Quadratic nonresidue that is not minus one is primitive root for safe prime]]
+* [[Safe prime has plus or minus two as a primitive root]]