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...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 2l^100 to 2^1000. Furthermore, this new method can be generalized to any ECs characterized by any small prime number.展开更多
In this work, we use the finiteness of the Mordell-weil group and the Riemann Roch spaces to give a geometric parametrization of the set of algebraic points of any given degree over the field of rational numbers Q on ...In this work, we use the finiteness of the Mordell-weil group and the Riemann Roch spaces to give a geometric parametrization of the set of algebraic points of any given degree over the field of rational numbers Q on curve C<sub>3 </sub>(11): y<sup>11</sup> = x<sup>3</sup> (x-1)<sup>3</sup>. This result is a special case of quotients of Fermat curves C<sub>r,s </sub>(p) : y<sup>p</sup> = x<sup>r</sup>(x-1)<sup>s</sup>, 1 ≤ r, s, r + s ≤ p-1 for p = 11 and r = s = 3. The results obtained extend the work of Gross and Rohrlich who determined the set of algebraic points on C<sub>1</sub>(11)(K) of degree at most 2 on Q.展开更多
基金supported by the National Natura Science Foundation of China (Nos.61332019 61572304, 61272056, and 60970006)the Innovation Grant of Shanghai Municipal Education Commission (No.14ZZ089)Shanghai Key Laboratory of Specialty Fiber Optics and Optical Access Networks (No.SKLSFO2014-06)
文摘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 2l^100 to 2^1000. Furthermore, this new method can be generalized to any ECs characterized by any small prime number.
文摘In this work, we use the finiteness of the Mordell-weil group and the Riemann Roch spaces to give a geometric parametrization of the set of algebraic points of any given degree over the field of rational numbers Q on curve C<sub>3 </sub>(11): y<sup>11</sup> = x<sup>3</sup> (x-1)<sup>3</sup>. This result is a special case of quotients of Fermat curves C<sub>r,s </sub>(p) : y<sup>p</sup> = x<sup>r</sup>(x-1)<sup>s</sup>, 1 ≤ r, s, r + s ≤ p-1 for p = 11 and r = s = 3. The results obtained extend the work of Gross and Rohrlich who determined the set of algebraic points on C<sub>1</sub>(11)(K) of degree at most 2 on Q.
