权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Number theory for positive characteristics and its application to elliptic curve cryptography

正特征数论及其在椭圆曲线密码中的应用

基本信息

批准号：
12640009
负责人：
SATOH Takakazu
金额：
$ 2.43万
依托单位：
Saitama University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2002
项目状态：
已结题

项目摘要

We establish and develop a p-adic point counting algorithm for elliptic curves over finite fields of small characteristics. Let p be a fixed small prime and put q to be the N-th power of p. For a given ordinal elliptic curve E defined over the finite field k of q elements, we construct a fast algorithm to compute the number of k-rational points of E. When a small prime p is fixed and N tends to infinity, our algorithm is faster than the so-called SEA algorithm.Our algorithm is based on the canonical lifts of elliptic curves. First we lift a given ordinal elliptic curve to its canonical lift. We use the fact that two j-invariants of lifted curves are related by the p-th modular polynomial. So, construction of the canonical lifts is reduced to find a solution to a certain system of non-linear equations. Second, we compute the leading coefficient of the dual of the lift of the p-th Frobenius morphism. This should not be confused with the inverse Frobenius substitution, since we are working over the field of characteristic zero once the curve is lifted. Third, by looking at the action of the dual of the lifted Frobenius morphism, we can compute the trace of the q-th Frobenius endomorphism. Using well-known Hasse's equality, we obtain the number of the rational points and we are done.We further construct a faster algorithm, with some precomputations which depends on only on q. The precomputation is quite feasible for the case that N is less than, say, 500. Hence the cost of precomputation is no problem for practical applications. On the other hand, thanks to the precomputation, we can evaluate the Frobenius substitution quickly. This ameliorates the growth rate of time complexity with respect to a number of bit operations by a factor of at least the square root of N.

建立并发展了一个小特征有限域上椭圆曲线的p-adic点计数算法。设p是一个固定的小素数，q是p的N次幂，对于给定的定义在q元有限域k上的有序椭圆曲线E，我们构造了一个计算E的k-有理点数的快速算法.当小素数p固定且N趋于无穷大时，我们的算法比SEA算法更快。首先，我们提升一个给定的有序椭圆曲线，其典型的电梯。我们利用提升曲线的两个j-不变量由第p次模多项式相关的事实。因此，正则提升的构造被简化为找到某个非线性方程组的解。其次，我们计算了p阶Frobenius态射的提升的对偶的首系数。这不应该与逆弗罗贝纽斯替换混淆，因为一旦曲线被提升，我们就在特征零的域上工作。第三，通过观察提升的Frobenius态射的对偶的作用，我们可以计算第q个Frobenius自同态的迹。利用著名的Hasse等式，我们得到了有理点的个数，我们完成了。我们进一步构造了一个更快的算法，其中一些预计算只依赖于q。对于N小于500的情况，预先计算是非常可行的。因此，预计算的成本对于实际应用来说是没有问题的。另一方面，由于预先计算，我们可以快速评估Frobenius替换。这将时间复杂度相对于位操作的数量的增长率改善了至少N的平方根的因子。