Communications of the
Korean Mathematical Society CKMS

몇몇 특수한 경우를 제외하고 타원곡선 이산로그문제를 푸는 준지수시간 알고리즘 (subexponential time algorithm)은 아직 알려지지 않고 있으나, 최근 타원곡선 올림을 이용한 새로운 공격방법이 제안되었다. 본 논문에서는 이 방법을 유한체 $\F_{p^n}$위에서 정의된 타원곡선에서 적용할 수 있도록 일반화 하였다. 또한, 환 $\Z /n \Z$위에서 정의된 타원곡선에 대한 올림을 구할 수 있는 경우, 타원곡선위의 한 점에 대한 위수를 구할 수 있음을 보이고, 이를 이용하여, 자연수 $n$을 소인수 분해할 수 있음을 보였다. 마지막으로, 올림문제에 대한 다각적인 분석을 제시한다.

Keywords: elliptic curves, discrete logarithm, lifting, heights, factorization

MSC numbers: 11G05, 11T71