Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
An Improved Baby Step Giant Step Algorithm for Point Counting of Hyperelliptic Curves over Finite Fields
| |
|
An Improved Baby Step Giant Step Algorithm for Point Counting of Hyperelliptic Curves over Finite Fields
Kazuto Matsuo5  , Jinhui Chao6 and Shigeo Tsujii7
| (5) |
Research and Development Initiative, Chuo University, 42-8 Ichigaya Honmuracho, Shinjuku-ku, Tokyo 162-8473, Japan |
| (6) |
Dept. of Electrical, Electronic and Communication Engineering, Chuo University, 1-13-27 Kasuga, Bunkyo-ku, Tokyo 112-8851, Japan |
| (7) |
Dept. of Information and System Engineering, Chuo University, 1-13-27 Kasuga, Bunkyo-ku, Tokyo 112-8851, Japan |
Abstract
Counting the number of points of Jacobian varieties of hyperelliptic curves over finite fields is necessary for construction
of hyperelliptic curve cryptosystems. Recently Gaudry and Harley proposed a practical algorithm for point counting of hyperelliptic
curves. Their algorithm consists of two parts: firstly to compute the residue modulo an integer m of the order of a given Jacobian variety, and then search for the order by a square-root algorithm. In particular, the parallelized
Pollard’s lambda—method was used as the square-root algorithm, which took 50CPU days to compute an order of 127 bits.
This paper shows a new variation of the baby step giant step algorithm to improve the square—root algorithm part in the Gaudry-Harley
algorithm. With knowledge of the residue modulo m of the characteristic polynomial of the Frobenius endomorphism of a Jacobian variety, the proposed algorithm provides a speed
up by a factor m, instead of √m in square—root algorithms. Moreover, implementation results of the proposed algorithm is presented including a 135-bit prime
order computed in 16 hours on Alpha 21264/667MHz.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|