CryptoDB
Imaginary quadratic orders with given prime factor of class number
Authors: | |
---|---|
Download: | |
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 }