An encryption device encrypts a message, and includes a function value output unit that calculates a function value of the message using a one-way converting function. The encryption device also includes a numerical array output unit having an initial array decision unit that generates an initial decision array V1 having n1 elements of 1, n2 elements of -1, and (n-n1-n2) elements of 0. Further, the numerical array output unit includes an array element replacement unit that changes the array element of the initial array V1 generated by the initial array decision unit according to an input integer X, and outputs the array V. The encryption device also includes a text generation unit that generates encrypted text, based on the message, according to a polynomial which corresponds to the array V.