타원곡선 소수판정법

타원곡선 소수판정법(Elliptic curve primality proving, ECPP)은 큰 자연수의 소수 여부를 알아내는 방법으로, 현재 가장 널리 쓰이고 있는 효율적인 알고리즘이다. 기본적으로 포클링턴-레머 소수판정법의 알고리즘을 확장한 형태를 하고 있으며, 포클링턴의 방법에 비해 일반적인 큰 수에 대해 유연하게 쓸 수 있다.

2022년 8월 13일까지 ECPP로 규명해낸 가장 큰 소수는 [math]\displaystyle{ 10^{50000}+65859 }[/math]로, 50001자리수이다.

진술

소수 여부를 가려낼 자연수 [math]\displaystyle{ N }[/math]이 있으면 [math]\displaystyle{ \mathbb{Z}/N\mathbb{Z} }[/math]위에서 정의된 특정 타원곡선 [math]\displaystyle{ E_{a, b}(N): y^2=x^3+ax+b }[/math]와 타원곡선 상의 점의 덧셈, 덧셈에 대한 항등원 [math]\displaystyle{ I }[/math]를 생각할 수 있다. 단, [math]\displaystyle{ \gcd(4a^3+27b^2, N)=1 }[/math]이다. 이 타원곡선에서 아래 조건을 만족하는 [math]\displaystyle{ m, q, P }[/math]가 존재하면 [math]\displaystyle{ N }[/math]은 소수이다.

• [math]\displaystyle{ p: \text{prime}, p\gt (\sqrt[4]{N}+1)^2 }[/math]
• [math]\displaystyle{ m=sp }[/math]
• [math]\displaystyle{ mP=I, sP \neq I }[/math]

증명

포클링턴-레머 소수판정법과 비슷한 방법으로 접근한다.

[math]\displaystyle{ N }[/math]이 소수가 아니라면 [math]\displaystyle{ q \mid N, q \leq \sqrt{N} }[/math]인 소인수가 존재하고, [math]\displaystyle{ \gcd(4a^3+27b^2, q)=1 }[/math]도 성립한다. 여기서 [math]\displaystyle{ q }[/math]를 법으로 하는 타원곡선[math]\displaystyle{ E_{a, b}(q) }[/math]를 생각할 수 있는데, 이 타원곡선의 점의 개수를 [math]\displaystyle{ m_q }[/math]라 한다. 하세의 정리에 의해 [math]\displaystyle{ |m_q-(q+1)| \leq 2\sqrt{q} }[/math]이고, 이에 따라 [math]\displaystyle{ m_q \leq q+2\sqrt{q}+1 \leq (\sqrt{q}+1)^2 }[/math]이다. 가정을 불러오면 [math]\displaystyle{ m_q \leq (\sqrt[4]{N}+1)^2 \lt p }[/math]이다.

여기서 [math]\displaystyle{ p }[/math]는 소수이므로 [math]\displaystyle{ m_q, p }[/math]는 서로소이다. 즉 합동식 [math]\displaystyle{ rp \equiv 1 \pmod{m_q} }[/math]를 만족하는 모듈러 역수 [math]\displaystyle{ r }[/math]이 존재하고, [math]\displaystyle{ m_q \mid rp-1 }[/math]이다.

한편 원래 타원곡선 [math]\displaystyle{ E_{a, b}(N) }[/math]의 한 점 [math]\displaystyle{ P }[/math]에 대응하는 [math]\displaystyle{ E_{a, b}q }[/math]상의 점 [math]\displaystyle{ Q }[/math]를 생각할 수 있고, 가정에 의해 [math]\displaystyle{ m_qQ=I, rpQ=Q }[/math]와 같이 쓸 수 있다. 또한 [math]\displaystyle{ E_{a, b}(N) }[/math]에서 가정한 진술의 셋째 조건인 [math]\displaystyle{ spP=I }[/math]를 [math]\displaystyle{ E_{a, b}(q) }[/math]로 옮기면 [math]\displaystyle{ spQ=I }[/math]이다. 이 점을 [math]\displaystyle{ r }[/math]번 더하면 [math]\displaystyle{ srpQ=I, sQ=I }[/math]가 된다.

하지만 진술의 또다른 셋째 조건인 [math]\displaystyle{ sP \neq I }[/math]는 [math]\displaystyle{ E_{a, b}(q) }[/math] 상에서는 [math]\displaystyle{ sQ \neq I }[/math]로, 바로 위 논리와 모순이다. 그러므로 [math]\displaystyle{ N }[/math]은 소수라는 결론에 도달한다.

실제 사용

ECPP는 밀러-라빈 소수판정법과 같은 타 방법보다 연산량이 훨씬 많다. 하지만 이 방법은 소수이기 위한 필요조건이 아닌 확실한 소수임을 결정하는 알고리즘이며, 모든 자연수에 대해 적용할 수 있다는 점에서 널리 스이고 있다.

어떤 큰 자연수가 소수인지를 알고 싶다면 먼저 페르마의 소정리와 같이 연산량이 적은 정리로 유력 소수 여부를 확인한다. 그리고 "이 수는 거의 확실히 소수일 것이다"라고 확신이 들 때 ECPP를 적용한다.

참고 자료

• Shafi Goldwasser, Primality Testing Using Elliptic Curves