A parameter generating device includes an input receiving unit that receives a degree n of an algebraic torus T including a group G in which a cryptosystem used in a torus-compressed public key cryptosystem is defined, a size W of a finite field F, and a size S of the group G, an extension-degree determining unit that determines an extension degree m of a finite field Fpm in which the algebraic torus T is defined, a first prime-number search unit that searches for a prime number p, a second prime-number search unit that searches for a prime number q, a test unit that checks whether a multiplication value nm is divisible by the prime number q, a security determining unit that determines that the cryptosystem is secure based on the multiplication value nm, and an output unit that outputs parameters when it is determined that the cryptosystem is secure.