An integer partitioning unit inputs an order p of a finite group G and an integer e, and calculates an integer e1 and an integer e2 that satisfy e1·e≡e2 (mod p) based on the order p of the finite group G and the integer e which are input. A verification value calculation unit inputs an element s of the finite group G and an element h of the finite group G, and calculates an element a (=e1·h−e2·s) of the finite group G based on the element s and the element h which are input and the integer e1 and the integer e2 which are calculated by the integer partitioning unit in the integer partitioning process. A verification judging unit judges, based on the element a calculated by the verification value calculation unit, whether or not the element a is an identity element O of the finite group G. Hence, whether or not h =e·s is judged at high speed.