Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer SciencesVol.E86-ANo.4pp.919-927 Publication Date: 2003/04/01 Online ISSN: DOI: Print ISSN: 0916-8508 Type of Manuscript: PAPER Category: Information Security Keyword: hyperelliptic curve, BSGS, point counting,
Full Text: PDF(279.8KB)>>
Summary: This paper proposes an improvement of Elkies' point counting algorithm for the Jacobian of a genus 2 hyperelliptic curve defined over a finite field in a practical sense and introduces experimental results. Our experimental results show that we can generate a cryptographic secure genus 2 hyperelliptic curve, where the order of its Jacobian is a 160-bit prime number in about 8.1 minutes on average, on a 700 MHz PentiumIII level PC. We improve Elkies' algorithm by proposing some complementary techniques for speeding up the baby-step giant-step.