====== ECPP ======

Elliptic curve primality proving. [[소수증명]] 알고리즘으로 일반적인 형태의 숫자가 소수임을 증명할 수 있다.

"아마도" [[다항시간]]에 수행되는 알고리즘일 거라는 얘기가 있지만 정확한 수행시간이 알려진 [[AKS]]와는 달리 완벽한 증명은 되어 있지 않다.((둘의 수행시간은 각각 $$O\!\left((\log n)^{5+\epsilon}\right)$$(추측)과 $$O\!\left((\log n)^{6+\epsilon}\right)$$임)) 그래도 AKS보단 빠르다.

{{tag>수학}}