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)

TAKENAKA MASAHIKO (JP)

Application Number:

PCT/JP2006/300396

Publication Date:

July 19, 2007

Filing Date:

January 13, 2006

Export Citation:

Assignee:

FUJITSU LTD (JP)

FURUKAWA KAZUYOSHI (JP)

TAKENAKA MASAHIKO (JP)

FURUKAWA KAZUYOSHI (JP)

TAKENAKA MASAHIKO (JP)

International Classes:

**G09C1/00**Foreign References:

JP2003114618A | 2003-04-18 | |||

JP2001318785A | 2001-11-16 | |||

JP2002215386A | 2002-08-02 | |||

JP2005209095A | 2005-08-04 | |||

JPH11212456A | 1999-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

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: