Patent ID: 8090099

Claim:
A non-transitory computer-readable recording medium recording a program for encryption/decryption with a Cyclic Vector Multiplication Algorithm which is configured, letting two elements A={a 0 , a 1 , a 2 , . . . , a m−1 } and B={b 0 , b 1 , b 2 , . . . , b m−1 } in an extension field F p m of extension degree m with a prime number p as characteristic be plaintext data and an encryption key, or ciphertext data and a decryption key, to generate an element C={c 0 , c 1 , c 2 , . . . , c m−1 } of ciphertext data by multiplying the plaintext and the encryption key using an electronic computer, or to generate an element C={c 0 , c 1 , c 2 , . . . , c m−1 } of plaintext data by multiplying the ciphertext data and the decryption key, using an electronic computer, the program for encryption/decryption comprising: a first step of determining a positive integer k satisfying conditions that km+1 is a prime number and p is a primitive element in a finite field F km+1 with (km+1) elements; a second step of multiplying said two elements A and B, regarding said two elements A and B as two elements in an extension field F p km of extension degree km with a prime number p as characteristic using the positive integer k; and a third step of obtaining a result of multiplication in an element of the extension field F p m of extension degree m which is a subfield of the extension field F p km , using the result of multiplication obtained in the second step, wherein letting i, j, and t be integers, a i , b i , and c i be coefficients of the elements A, B, and C respectively, M be a variable, K[t] be a t-th element of an array, q[<x>] be a <x>-th element of an array, <x> denoting x modulo (km+1), and ← be an assignment operator, the second step includes: a step of obtaining respective K[t]←<p mt > for 0≦t≦k−1; a step of setting q[<i>]←0 respectively for 0≦i≦km; a step of obtaining q[<p i >]←a i ·b i modulo p respectively for 0≦i≦m−1; and a step of obtaining M←(a i −a j )·(b i −b j ) modulo p respectively for 0≦i<j≦m−1 and adding M to q[<p i +(p j ·K[t])>] respectively for 0≦t≦k−1.