서지주요정보
Elliptic curve point counting = 타원곡선의 위수 계산
서명 / 저자 Elliptic curve point counting = 타원곡선의 위수 계산 / Hae-Young Kim.
발행사항 [대전 : 한국과학기술원, 2002].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8013615

소장위치/청구기호

학술문화관(문화관) 보존서고

DMA 02012

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

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 수체에서의 빠른 곱연산을 유도하였다.

서지기타정보

서지기타정보
청구기호 {DMA 02012
형태사항 [ii], 38 p. ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 김해영
지도교수의 영문표기 : Sang-Geun Hahn
지도교수의 한글표기 : 한상근
수록잡지명 : "Fast elliptic curve point counting using gaussian normal basis". Algorithmic number theory(ANT) -V, 2002 July, pp. 100-115 (2002)
학위논문 학위논문(박사) - 한국과학기술원 : 수학전공,
서지주기 Reference : p. 35-37
주제 elliptic curve
Gaussian normal basis
order counting
타원곡선
위수 계산
QR CODE qr code