소피 제르맹 소수

소피 제르맹 소수(Sophie Germain primes)는 프랑스의 수학자 소피 제르맹이 정의한 소수(素數)로, 어떤 소수 $p$에 대해서, $2p+1$도 소수가 되는 수 $p$를 말한다.

예시

예를 들어 23은 소수이고, 2×23+1=47도 소수이기에 23은 소피 제르맹 소수다.

암호학에서는 $p$와 $2p+1$이 모두 소수일 때, $p$를 소피 제르맹 소수라고 부르고, $2p+1$을 안전 소수(safe prime)라고 부른다.

현재까지 알려진 가장 큰 소피 제르맹 소수는 2016년 2월에 발견된 2618163402417×^1290000-1 (388342자리)이다. 소피 제르맹 소수는 무한히 존재할 것이라고 추측되지만, 아직 증명이 되진 않았다.

1000보다 작은 소피 제르맹 소수는 다음과 같다. (OEIS의 수열 A005384)

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, …

관련 성질

• 안전 소수 (safe prime)

안전 소수는 $p$와 $2p+1$이 모두 소수일 때 $2p+1$을 칭하는 용어다. 2000보다 작은 안전 소수는 다음과 같다. (OEIS의 수열 A005385)

5, 7, 11, 23, 47, 59, 83, 107, 167, 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, …

• 안전 소수를 겸하는 소피 제르맹 소수

1만보다 작은 자연수 중 소피 제르맹 소수이면서 안전 소수인 수는 다음과 같다. (OEIS의 수열 A059455)

5, 11, 23, 83, 179, 359, 719, 1019, 1439, 2039, 2063, 2459, 2819, 2903, 2963, 3023, 3623, 3779, 3803, 3863, 4919, 5399, 5639, 6899, 6983, 7079, 7643, 7823, …

같이 보기

• 쌍둥이 소수
• RSA 암호