Name
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 scheme for point counting of hyperelliptic curves. Their scheme consists of two parts: firstly to compute the residue modulo a positive 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 scheme. 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 rootm in square-root algorithms. Moreover, implementation results of the proposed algorithm is presented including a 135-bit prime order computed about 15 hours on Alpha 21264/667 MHz and a 160-bit order. |
Year | Venue | Keywords |
|---|---|---|
2003 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | hyperelliptic curve cryptosystems, hyperelliptic curves, point counting algorithms, baby step giant step algorithms, Gaudry-Harley scheme |
DocType | Volume | Issue |
Journal | E86A | 5 |
ISSN | Citations | PageRank |
0916-8508 | 3 | 0.46 |
References | Authors | |
7 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuto Matsuo | 1 | 62 | 6.44 |
| jinhui chao | 2 | 3 | 0.46 |
| Shigeo Tsujii | 3 | 598 | 131.15 |