DISCRETE LOGARITHM PROCESSING DEVICE, CENTER DEVICE IN PUBLIC KEY CRYPTOSYSTEM, AND PROGRAM FOR DISCRETE LOGARITHM PROCESSING

摘要

PROBLEM TO BE SOLVED: To make a scale of a table small when solving a discrete logarithm problem by Baby step/Giant step methods, and to reduce a frequency of referring to the table.;SOLUTION: The table describing candidates for values of (i) satisfying y g^-i=Gⁱ is created when defining (a) bit string of lower rank 2 bits of y g^-1 as (a), and using (a) as an address. The table is made to describe two or more candidates for the values of (i) to each address, and the candidates for the values of (i) are described in the blank spaces on and after the address (a) when creating the table. When referring to the table, the candidates for the values of (i) until a blank arises starting with the address (a) are read out, and Gⁱ is calculated, and what is coincident with y g^-i is output as a value of (i).;COPYRIGHT: (C)2007,JPO&INPIT