A storing device stores a plurality of remainder tables which respectively hold corresponding remainder information strings by using a plurality of unit information strings as indexes. A table looking-up device obtains a plurality of remainder information strings by partitioning a target information string, which is processed with a loop process performed once, into a plurality of unit information strings and by referring to the plurality of remainder tables with the use of the unit information strings as indexes. A calculating device calculates an exclusive OR of the obtained plurality of remainder information strings and the first information string of an unprocessed portion of an input information string. The table looking-up device repeats a reference of the plurality of remainder tables a predetermined number of times by using the obtained information string of the exclusive OR as a target information string in the next loop process.