MULTIPLICATION RESIDUE ARITHMETIC METHOD AND MULTIPLICATION RESIDUE CIRCUIT

摘要

PROBLEM TO BE SOLVED: To enable operation which is versatile and fast since operation of an arbitrary degree is possible by providing a specific operation process for a method which performs multiplication residue operation for two elements on two extension fields represented by a polynomial base and an irreducible polynomial. ;SOLUTION: In multiplication residue operation a(x)×b(x)modf(x), a multiplication part 11 performs (m)-bit×(m)-bit multiplication between a(x) and b(x) and sends the term of the product a(x)×b(x) above the (m)th order to a multiplication part 12. The multiplication part 12 performs multiplication previously calculated f'(x) and the term of the product a(x)×b(x) above the (m)th order. A multiplication part 13 performs multiplication between f(x) and the term of the multiplication result of the multiplication part 12 above the (m)th order. An addition part 14 adds the multiplication result of the multiplication part 13 and the multiplication result of the multiplication part 11 together. The term of the addition result of the addition part 14 above the (m)th order is canceled and the output c(x) from the addition part 14 is a multiplication residue of a(x) and b(x).;COPYRIGHT: (C)2001,JPO