Fast computation of canonical lifts of elliptic curves and its application to point counting
- 作者：Satoh ; Takakazu ; Skjernaa ; Berit ; Taguchi ; Yuichiro
- 关键词：Elliptic curves ; Canonical lifts ; Frobenius substitutions
- 刊名：Finite Fields and Their Applications
- 出版年：2003
- 期刊代码：66_10715797
- 类别：mt
- 出版时间：January, 2003
- 卷：9
- 期：1
- 页码：89-101
- 文件大小：191 K
摘要
Let p be a fixed small prime. We give an algorithm with preprocessing to compute the j-invariant of the canonical lift of a given ordinary elliptic curve E/Fq (q=pN, j(E)
Fp2) modulo pN/2+O(1) in O(N2μ+1/μ+1) bit operations (assuming the time complexity of multiplying two n-bit objects is O(nμ)) using O(N2) memory, not including preprocessing. This is faster than the algorithm of Vercauteren et al. [14] by a factor of Nμ/μ+1. Let K be the unramified extension field of degree N over Qp. We also develop an algorithm to compute NK/Qp(x)modpN/2+O(1) with O(N2μ+0.5) bit operations and O(N2) memory when x
K satisfies certain conditions, which are always satisfied when applied to our point counting algorithm. As a result, we get an O(N2μ+0.5) time, O(N2) memory algorithm for counting the Fq-rational points on E/Fq, which turns out to be very fast in practice for cryptographic size elliptic curves.
Fp2) modulo pN/2+O(1) in O(N2μ+1/μ+1) bit operations (assuming the time complexity of multiplying two n-bit objects is O(nμ)) using O(N2) memory, not including preprocessing. This is faster than the algorithm of Vercauteren et al. [14] by a factor of Nμ/μ+1. Let K be the unramified extension field of degree N over Qp. We also develop an algorithm to compute NK/Qp(x)modpN/2+O(1) with O(N2μ+0.5) bit operations and O(N2) memory when xK satisfies certain conditions, which are always satisfied when applied to our point counting algorithm. As a result, we get an O(N2μ+0.5) time, O(N2) memory algorithm for counting the Fq-rational points on E/Fq, which turns out to be very fast in practice for cryptographic size elliptic curves.