For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Generating Secure Genus Two Hyperelliptic Curves Using Elkies' Point Counting Algorithm
Naoki KANAYAMA Koh-ichi NAGAO Shigenori UCHIYAMA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/04/01
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
hyperelliptic curve, BSGS, point counting,
Full Text: PDF(279.8KB)>>
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.