International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Imaginary quadratic orders with given prime factor of class number

Authors:
Alexander Rostovtsev
Download:
URL: http://eprint.iacr.org/2008/180
Search ePrint
Search Google
Abstract: Abelian class group Cl(D) of imaginary quadratic order with odd squarefree discriminant D is used in public key cryptosystems, based on discrete logarithm problem in class group and in cryptosystems, based on isogenies of elliptic curves. Discrete logarithm problem in Cl(D) is hard if #Cl(D) is prime or has large prime divisor. But no algorithms for generating such D are known. We propose probabilistic algorithm that gives discriminant of imaginary quadratic order O_D with subgroup of given prime order l. Algorithm is based on properties of Hilbert class field polynomial H_D for elliptic curve over field of p^l elements. Let trace of Frobenius endomorphism is T, discriminant of Frobenius endomorphism D = T^2-4p^l and j is not in prime field. Then deg(H_D) = #Cl(O_D) and #Cl(D)=0 (mod l). If Diophantine equation D = T^2-4p^l with variables l<O(|D|^(1/4)), prime p and T has solution only for l=1, then class number is prime.
BibTeX
@misc{eprint-2008-17857,
  title={Imaginary quadratic orders with given prime factor of class number},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / elliptic curve cryptosystem, number theory},
  url={http://eprint.iacr.org/2008/180},
  note={ rostovtsev@ssl.stu.neva.ru 13987 received 18 Apr 2008},
  author={Alexander Rostovtsev},
  year=2008
}