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

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

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.