Generating Secure Genus Two Hyperelliptic Curves Using Elkies' Point Counting Algorithm

Koh-ichi NAGAO
Shigenori UCHIYAMA

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A    No.4    pp.919-927
Publication Date: 2003/04/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
hyperelliptic curve,  BSGS,  point counting,  

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

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.

open access publishing via