In this thesis we present an improved algorithm for counting points on elliptic curves over finite fields. It is mainly based on Satoh-Skjernaa-Taguchi algorithm, and uses a Gaussian Normal Basis (GNB) of small type t≤4. In practice, about 42% (36% for prime N) of fields in cryptographic context (i.e., for p=2 and 160＜ N＜600) have such bases. They can be lifted from $\F_{p^N}$ to $\Z_{p^N}$ in a natural way. From the specific properties of GNBs, efficient multiplication and the Frobenius substitutions are available. Thus a fast norm computation algorithm is derived, which runs in $O(N^{2μ logN)$ with $O(N^2)$ space, where the time complexity of multiplying two n-bit objects is $O(n^μ)$. As a result, for all small characteristic p, we reduced the time complexity of the SST-algorithm from $O(N^{2μ+ 0.5})$ to $O(N^{2μ + \frac{1}{μ + 1}})$ and the space complexity still fits in $O(N^2)$.
타원곡선의 위수는 타원곡선 암호 시스템의 구현을 위한 기본 상수일 뿐만 아니라, 이산로그 문제의 안전성과도 밀접한 관련이 있다. 특히, 수학적으로도 많은 문제와 연관되어 있기 때문에 위수계산은 이론적으로도 매우 중요한 연구 과제이다.
본 논문에서는 타원곡선의 위수 계산 알고리즘 중 가장 좋은 복잡도를 갖고 있는 Satoh-Skjernna-Taguchi (SST) 알고리즘을 개량한다. 개량된 알고리즘은 type 4 이하의 Gaussion Normal Basis (GNB)를 갖는 유한체에서 적용가능 하며, SST 알고리즘보다 좋은 복잡도를 갖는다. 정규 기저(Normal Basis)의 특성을 이용한 p-adic Norm 계산 알고리즘을 적용해 SST 알고리즘의 복잡도 $O(N^{2μ + 0.5})$에서 $O(N^{2μ + \frac{1}{μ + 1}})$로 낮추었으며, 유한체에서 정의된 GNB의 p-adic 올림을 이용해 p-adic 수체에서의 빠른 곱연산을 유도하였다.
