이것은 문서의 이전 버전입니다!


ECPP

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

"아마도" 다항시간에 수행되는 알고리즘일 거라는 얘기가 있지만 정확한 수행시간이 알려진 AKS와는 달리 완벽한 증명은 되어 있지 않다.1) 그래도 AKS보단 빠르다.

1) 둘의 수행시간은 각각 O\!\left((\log n)^{5+\epsilon}\right)(추측)과 O\!\left((\log n)^{6+\epsilon}\right)

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기