소피 제르맹 소수
틀:토막글
제르멩 소수에 넘겨주기
Sophie Germain Prime
소피 제르멩 소수는 2p+1이 소수가 되는 소수 p를 말한다. 독일의 여성 수학자 소피 제르멩이 페르마의 마지막 정리에서 이 조건을 만족하는 소수에 대해 증명했기에 이 이름이 붙었다.
특성
처음 10개의 소피 제르멩 소수는 다음과 같다. 일단 3n+1, 5n+2(2 제외)꼴의 소수는 소피 제르멩 소수가 될 수 없다. 2, 3, 5, 11, 23, 29, 41, 53, 89, 101 p가 소피 제르멩 소수일 경우 q=2p+1은 암호학에서 "안전한 소수(safe prime)"이라고 간주한다. 이 소수들은 자연스럽게 q-1이 "충분히 큰" 소인수 p를 갖게 되며, 이 중에서도 q+1이 충분히 큰 소수 q를 "강력한 소수(strong prime)이라고 부른다. 강력한 두 소수의 곱은 폴라드의 로 알고리즘[1]으로 쉽게 소인수분해할 수 없기 때문에 소인수분해의 난해함을 기반으로 하는 RSA 암호체계에서 사용하기 좋은 소수가 된다.