Keywords
Elliptic Curves (ECs), Pascal’s triangle, Weil theorem
Abstract
How to quickly compute the number of points on an Elliptic Curve (EC) has been a longstanding challenge. The computational complexity of the algorithm usually employed makes it highly inefficient. Unlike the general EC, a simple method called the Weil theorem can be used to compute the order of an EC characterized by a small prime number, such as the Kobltiz EC characterized by two. The fifteen secure ECs recommended by the National Institute of Standards and Technology (NIST) Digital Signature Standard contain five Koblitz ECs whose maximum base domain reaches 571 bits. Experimental results show that the computation speed decreases for base domains exceeding 600 bits. In this paper, we propose a simple method that combines the Weil theorem with Pascals triangle, which greatly reduces the computational complexity. We have validated the performance of this method for base fields ranging from 2100 to 21000. Furthermore, this new method can be generalized to any ECs characterized by any small prime number.
Publisher
Tsinghua University Press
Recommended Citation
Feng Hu, Chao Wang, Huanguo Zhang et al. Simple Method for Realizing Weil Theorem in Secure ECC Generation. Tsinghua Science and Technology 2017, 22(5): 511-519.