In this paper, we describe the implementation of the elliptic curve point counting algorithm of Kim et al.. We survey the algorithms including the SST-algorithm proposed by Satoh et al., We also described the modified SST-algorithm by Kim et al. using the Gaussian normal basis, which is of the lowest time complexity of $O(N^{2μ+\frac{1}{μ+1}})$ where $O(N^μ)$ is the complexity of multiplying two N-bit numbers. All algorithms which is required for its implementation is fully given. Every step is explained in detail, and the actual running time result is also included.
이 논문에서는, Kim et al.이 제안한 타원 곡선 위수 계산 알고리즘의 구현을 다룬다. Satoh et al.에 의해 제안된 SST 알고리즘을 포함하여 전반적인 알고리즘에 대해 간략히 살펴본 뒤, Kim et al.에 의해 변형된 SST 알고리즘을 설명한다. 이 알고리즘은 GNB를 이용하며, $O(N^{2μ+\frac{1}{μ+1})$라는 현재까지 가장 낮은 시간복잡도를 보여준다. (단, 이 때 $O(N^μ)$는 두 개의 N비트 수를 곱할 때 요구되는 시간복잡도이다.) 이 알고리즘의 구현을 위해 필요한 모든 연산의 구현 방법을 자세하게 설명하며, 끝으로 실제 구현 결과를 첨부함으로써 실제로 Kim et al.이 제안한 방법이 가장 빠름을 보인다.
