Montgomery division apparatus and the Montgomery inverse computing device as well as the Montgomery division method and Montgomery inverse calculation method

摘要

PROBLEM TO BE SOLVED: To provide a Montgomery division device capable of obtaining a divided result in a Montgomery arithmetic area at a high speed. ;SOLUTION: This Montgomery division device 200 for obtaining the divided result Y in the Montgomery arithmetic area to be Y=B.A' (-1).2 n mod N for the integer (n) of (n)≥L when a bit length at the time of binarily expressing N is defined as L for a positive integer N, the positive integer A (0≤AN and A and N are mutually prime) and the positive integer B is provided with a Montgomery inverse element calculation part 201 for inputting the integer A and a modulus N and obtaining an inverse element X=A (-1).2 (2n) mod N and a Montgomery multiplication part 202 for inputting the obtained inverse element X, the modulus N and the B and obtaining the divided result Y=B.X.2 (-n) mod N.;COPYRIGHT: (C)1998,JPO