소피 제르맹 소수

소피 제르맹 소수(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자리)이다. 소피 제르맹 소수는 무한히 존재할 것이라고 추측되지만, 아직 증명이 되진 않았다.

처음 몇 개의 소피 제르맹 소수는 다음과 같다.

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, … (OEIS의 수열 A005384)

안전 소수

안전 소수(safe prime)는 $p$와 $2p+1$이 모두 소수일 때 $2p+1$을 칭하는 용어다.

처음 몇 개의 안전 소수는 다음과 같다.

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, … (OEIS의 수열 A005385)

또한, 소피 제르맹 소수이면서 안전 소수인 자연수는 다음과 같다.

5, 11, 23, 83, 179, 359, 719, 1019, 1439, 2039, 2063, 2459, 2819, 2903, 2963, …

같이 보기

• 쌍둥이 소수
• RSA 암호