Generating Hyperelliptic Curves of Genus 2 Suitable for Cryptography

摘要

This paper proposes some complementary techniques for speeding up the baby-step giant-step. By using these techniques, this paper also proposes an improvement of Elkies' point counting algorithm of the Jacobian of a genus 2 hyperelliptic curve defined over a finite field in a practical sense and introduces its experimental results. Our experimental results show that we can generate a cryptographic secure genus 2 hyperelliptic curve, where the order of its Jacobian is 160 bits and almost prime, in 2.5 minutes on average, on a 700MHz(x2) PentiumIII technology PC.