Method and integrated circuit for carrying out a multiplication modulo m

• US 20050223052A1
• Filed: 05/20/2003
• Published: 10/06/2005
• Est. Priority Date: 05/28/2002
• Status: Abandoned Application

• Current Assignee: Technische Universitat Munchen
• Original Assignee: Technische Universitat Munchen
• Inventors: Schimmler, Manfred, Bunimov, Viktor
• Application Number:
  US10/515,810
• Publication Number:
  US 20050223052A1
• Time in Patent Office: Days
• US Class Current: 708/492
• CPC Class Codes: G06F 7/722 Modular multiplication G06F7/724, G06F7/727, G06F7/728 take precedence

Abstract

The invention relates to a method for carrying out a multiplication modulo M of two n-digit digital numbers (X, Y) in relation to a radix m by means of an integrated circuit. The inventive method consists of the following steps: conventionally determined partial products I=X<SB>1</SB>*Y(0=1=n−1), beginning with the highest-ranking place, are formed; the partial product (I) is added (4) to a subtotal multiplied by m, in order to form a new subtotal; the summands (S, C) of the new subtotal are added (5) to a value from a plurality of pre-calculated values (A) which are attributed to classes, in order to form a new subtotal; the new subtotal is used for the addition (4) of the next step (I−1); the new subtotal is approximately compared with the pre-determined classes in order to establish in which class the new subtotal falls; and the pre-calculated value (A) pertaining to the determined class is used as a summand for the corresponding addition (5) of the next step (i−1).

Claims

1. A method for carrying out a module M multiplication of two n-digit digital numbers (X, Y)—

relative to a base m—

using an integrated circuit, where M<

mⁿ;

X, y<

M, said method having the following method steps;

conventional created partial products I−

X_i*Y (0≦

I≦

n−

1) are formed, beginning with the most significant digit

the partial product (I) is added (4) to a subtotal, which has been multiplied by m, in order to form a new subtotal

the new subtotal is added (5) to one of a number of precalculated values (A), which are associated with size classes, in order to form a new subtotal

the last n digits of the new subtotal are used for the addition (4) in the next iteration (I−

1)

the new subtotal is approximately compared with the predetermined size classes in order to determine the size class into which the new subtotal falls

the precalculated value (A) which belongs to the size class determined is used as a summand for the corresponding addition (5) in the next iteration (I−

1).

2. The method as claimed in claim 1, in which the precalculated values are multiples of mⁿ mod M, and the predetermined size classes are determined by lower limit values mⁿ which result in the multiples of mⁿ.

3. The method as claimed in claim 2, in which the approximate comparison with the sum of the two most significant places of the summands (S and C) is carried out using the values 0 to 5.

4. The method as claimed in claim 1, in which the partial product (I) is added, as a case distinction, during determination of the precalculated correction value (A) belonging to the size class determined, and the partial product (I) and the value (A) are added (4, 5) in a combined addition.

5. The method as claimed in claim 1, in which the computation is affected using binary numbers

6. An integrated circuit for carrying out a module M multiplication in accordance with the method as claimed in claim 1, said circuit containing a multiplier (1) for forming the partial products (I), at least one adder (4, 5), and an assessment stage (6) for forming a sum of the most significant places of the summands and for selecting a precalculated correction value (A).

7. The integrated circuit as claimed in claim 6, in which the sum of the two most significant places of the summands (S and C) is formed in the assessment stage.