Baby Step Giant Step Algorithms in Point Counting of Hyperelliptic Curves

Kazuto MATSUO  Jinhui CHAO  Shigeo TSUJII  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.5   pp.1127-1134
Publication Date: 2003/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
hyperelliptic curve cryptosystems,  hyperelliptic curves,  point counting algorithms,  baby step giant step algorithms,  Gaudry-Harley scheme,  

Full Text: PDF(264.1KB)>>
Buy this Article



Summary: 
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 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.