Patent Document ID: 8300807
Application ID: 12350222
Patent Status: 1

Claim One:
1. A computer-implemented process for generating a curve for use in cryptography, comprising: using a computer to perform the steps of: selecting a suitable large prime number from a predefined set of large prime numbers; generating an Igusa class polynomial over the rational numbers from Igusa class polynomials modulo small primes, comprising for a predefined set of small prime numbers, (a) selecting a small prime number from a predefined set of small prime numbers; (b) performing a single random search to identify a first root of an Igusa class polynomial modulo the selected small prime number; (c) computing a value of a small modular function using the first root; (d) applying an isogeny to the small modular function value to find a new value of the small modular function; (e) using the new value of the small modular function to find the next root of the Igusa class polynomial modulo the selected small prime number; (f) checking to determine if all of the roots of the Igusa class polynomial modulo the selected small prime are computed; and (g) if not, repeating process actions (d) through (f) until all roots are computed; (h) constructing a new Igusa class polynomial from the computed roots; (i) adding the new Igusa class polynomial to a set of Igusa class polynomials; and applying a Chinese remainder approach to construct an Igusa class polynomial over the rational numbers from the computed set of Igusa class polynomials modulo the small primes; using the selected large prime number and the Igusa class polynomial over the rational numbers to compute a root of the Igusa class polynomial modulo the selected large prime number; using the computed root to generate a genus 2 curve; and using the genus curve for a cryptographic application.