MULTIPLIER AND MULTIPLICATION METHOD USING MONTGOMERY ALGORITHM OVER FINITE FIELDS

摘要

The present invention relates to a multiplier and a multiplication method using an Montgomery factor selected to implement the Montgomery multiplication easily and effectively on hardware. According to the present invention, the multiplication method selects a Montgomery factor, uses the Montgomery factor to derive a multiplication formula on the finite field GF(2m). The derived multiplication formula is separated into two formulas without data dependency to execute computations corresponding to the two formulas on a parallel basis. The present invention provides a novel multiplication method for the Montgomery multiplication based on a polynomial formula on the finite field GF(2m). The present invention can also provide a semi-systolic multiplier capable of parallel computation.