System and method for optimized reciprocal operations

• US 20070083586A1
• Filed: 10/12/2005
• Published: 04/12/2007
• Est. Priority Date: 10/12/2005
• Status: Abandoned Application

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Inventors: Chin, David, Luo, Jianjun
• Application Number:
  US11/249,655
• Publication Number:
  US 20070083586A1
• Time in Patent Office: Days
• US Class Current: 708/502
• CPC Class Codes: G06F 2207/5355 Using iterative approximation not using digit recurrence, e.g. Newton Raphson or Goldschmidt
• CPC Class Codes: G06F 2207/5356 Via reciprocal, i.e. calculate reciprocal only, or calculate reciprocal first and then the quotient from the reciprocal and the numerator
• CPC Class Codes: G06F 7/49942 Significance control
• CPC Class Codes: G06F 7/535 Dividing only
• CPC Class Codes: G06F 7/721 Modular inversion, reciprocal or quotient calculation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

A method and apparatus for calculating a reciprocal of an integer using a modified Newton Raphson method using one'"'"'s complements instead of two'"'"'s complements. The method includes determining a required precision; determining a number of iterations T responsive to the required precision; normalizing N into d; obtaining initial approximation of 1/d=R[0]; refining reciprocal approximation by the modified Newton Raphson operation using ones complements; truncating final iteration result R[T] responsive to the required precision; denormalizing R[T]; and outputting the reciprocal R.

Claims

1. A method for calculating a reciprocal R of an integer N of length k*256 bit, the method comprising:

determining a required precision;

determining a number of iterations T responsive to the required precision;

normalizing N into d so that N=d*2<sup>−

s</sup>*2^K, 1≦

d<

2 (d=1.b₁b₂b₃ . . . b_K), where N=(N<sub>k−

1</sub>N<sub>k−

2</sub> . . . N₀)_b is modulus before normalization, d is an intermediate result of modulus after normalization, and s is normalize shift count;

obtaining initial approximation of 1/d=R[0], where R is reciprocal at different iterations of a modified Newton Raphson operation;

refining reciprocal approximation by the modified Newton Raphson operation using ones complements;

truncating final iteration result R[T] responsive to the required precision;

denormalizing R[T]; and

outputting the reciprocal R.

2. The method of claim 1, wherein the initial approximation of 1/d is obtained from a midpoint reciprocal table.

3. The method of claim 2, wherein the initial approximation of 1/d has a 9-bit precision.

4. The method of claim 1, wherein d includes at least 512-bit fraction.

5. The method of claim 1, wherein the number of iterations T is determined from a relative error table and the required precision.

6. The method of claim 1, wherein the required precision is 1x for normal divisions used in Extended Euclid GCD modular inverse algorithm in a public key system.

7. The method of claim 1, wherein the required precision is 2x for most public key operations.

8. The method of claim 1, wherein the required precision is 3x for a RSA CRT operation.

9. The method of claim 1, wherein the required precision is 4x for a DSA operation.

10. A system for accelerating calculation of a reciprocal of an integer N comprising:

an input buffer for receiving an input including a long integer N and a required precision;

a parser for decoding the received input to determine the size of the integer N, the number of iterations of a modified Newton Raphson operation, and the number of truncations for each iteration;

a lookup table for obtaining an initial reciprocal seed 1/d;

a memory for storing the input integer N, intermediate normalized d of N, and intermediate and final results of the reciprocal calculation in pre-assigned locations;

a microcode generation module for generating microcode on the fly responsive to the required precision, the stored integer N, and the intermediate results;

an execution unit for executing the generated microcode in a single-cycle based pipeline structure to generate the reciprocal of the integer N; and

an output buffer for outputting the reciprocal.

11. The system of claim 10, wherein the execution unit comprises a first execution module for generating partial normalization shifting result, and a second execution module for arithmetic operations including multiplying and accumulating.

12. The system of claim 10, wherein d includes at least 512-bit fraction.

13. The system of claim 10, wherein the number of iterations T is determined from a relative error table and the required precision.

14. The system of claim 10, wherein the required precision is 1x for normal divisions used in Extended Euclid GCD modular inverse algorithm in a public key system.

15. The system of claim 10, wherein the required precision is 2x for most public key operations.

16. The system of claim 10, wherein the required precision is 3x for a RSA CRT operation.

17. The system of claim 10, wherein the required precision is 4x for a DSA operation.

18. A system for accelerating calculation of a reciprocal of an integer N comprising:

means for receiving an input including a long integer N and a required precision;

means for decoding the received input to determine the size of the integer N, the number of iterations of a modified Newton Raphson operation, and the number of truncations for each iteration;

means for obtaining an initial reciprocal seed 1/d;

means for storing the input integer N, intermediate normalized d of N, and intermediate and final results of the reciprocal calculation in pre-assigned locations;

means for generating microcode on the fly responsive to the required precision, the stored integer N, and the intermediate results;

means for executing the generated microcode in a single-cycle based pipeline structure to generate the reciprocal of the integer N; and

means for outputting the reciprocal.

19. The system of claim 18, wherein the initial approximation of 1/d is obtained from a midpoint reciprocal table.

20. The system of claim 18, wherein d includes at least 512-bit fraction.