Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
MONTGOMERY’S ALGORITHM MULTIPLICATION REMAINDER CALCULATOR
Document Type and Number:
WIPO Patent Application WO/2007/080652
Kind Code:
A1
Abstract:
REDC(A×B) is calculated for A and B both of r-nary numbers by the Montgomery algorithm REDC. A processor including a product-sum calculation circuit having three inputs and two outputs is used. The part A×B of when the REDC is decomposed into calculation of each digit of an r-nary number is calculated by the product-sum calculation circuit. The first digit ai of A represented by the r-nary notation, the first digit of bj of B, and the carry number c1 are inputted into the product-sum calculation circuit, and ai×bj+c1 is calculated. The upper-order digit of the two-digit r-nary number of the result is used as the carry number c1, and the lower digit is used for later calculations. The first digit ni of the base N for the REDC, a predetermined number m, and a carry number c2 are inputted into the product-sum calculation circuit, and m×ni+c2 is calculated. The upper digit is used as the carry number c2, and the lower digit is used for the later calculation. The algorithm is constituted by the product-sum calculations of three inputs and two outputs. Therefore, the product-sum calculation circuit is effectively utilized and the processing is can be done at high speed. If two product-sum calculation circuits are provided, the calculation can be done at higher speed.

Inventors:
FURUKAWA KAZUYOSHI (JP)
TAKENAKA MASAHIKO (JP)
Application Number:
PCT/JP2006/300396
Publication Date:
July 19, 2007
Filing Date:
January 13, 2006
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
FUJITSU LTD (JP)
FURUKAWA KAZUYOSHI (JP)
TAKENAKA MASAHIKO (JP)
International Classes:
G09C1/00
Foreign References:
JP2003114618A2003-04-18
JP2001318785A2001-11-16
JP2002215386A2002-08-02
JP2005209095A2005-08-04
JPH11212456A1999-08-06
Other References:
See also references of EP 1975906A4
PETER L. MONTGOMERY: "Modulo Multiplication Without Trial Division", MATHEMATICS OF COMPUTATION, vol. 44, no. 170, April 1985 (1985-04-01), pages 519 - 528, XP000747434
Attorney, Agent or Firm:
OSUGA, Yoshiyuki (Nibancho Bldg. 8-20, Nibancho, Chiyoda-k, Tokyo 84, JP)
Download PDF: