System and method for multi-precision division

• US 7,738,657 B2
• Filed: 08/31/2006
• Issued: 06/15/2010
• Est. Priority Date: 08/31/2006
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wolrich, Gilbert M., Gopal, Vinodh, Gaubatz, Gunnar, Bace, Matt
• Primary Examiner(s): Moazzami; Nasser
• Assistant Examiner(s): LEWIS, LISA C
• Application Number:
  US11/469,243
• Publication Number:
  US 20080069337A1
• Time in Patent Office: 1,384 Days
• Field of Search: 380/28, 708650-654
• US Class Current: 380/28
• CPC Class Codes: G06F 2207/3896 Bit slicing
• CPC Class Codes: G06F 7/535 Dividing only

Abstract

The present disclosure provides a system and method for performing multi-precision division. A method according to one embodiment may include generating a first product by multiplying a modulus having a most significant bit and/or a least significant bit equal to one and a quotient approximation of the modulus. The method may also include generating the 1'"'"'s complement of the first product, generating a second product by multiplying the 1'"'"'s complement and the quotient approximation, normalizing and truncating the second product to obtain a quotient, and storing the quotient in memory. Of course, many alternatives, variations and modifications are possible without departing from this embodiment.

Claims

1. A method for multi-precision division, comprising:

generating a first product using an integrated circuit by multiplying a modulus having a most significant bit and/or a least significant bit equal to one and a quotient approximation of the modulus;

generating the 1'"'"'s complement of the first product using said integrated circuit;

generating a second product by multiplying the 1'"'"'s complement and the quotient approximation using said integrated circuit;

normalizing and truncating the second product to obtain a quotient using said integrated circuit; and

storing the quotient in memory.

2. The method of claim 1, further comprising:

generating a public key based on, at least in part, a remainder extracted from the quotient using said integrated circuit.

3. The method of claim 1, wherein:

generating a quotient approximation includes a plurality of bit-serial calculations of reciprocal of the modulus using said integrated circuit.

4. The method of claim 3, wherein:

said bit-serial calculations are monotonic, and all intermediate results of said bit-serial calculations are non-negative integers.

5. The method of claim 1, wherein:

said modulus is selected from the group of a National Institute of Standards and Technology (NIST) modulus and a random modulus.

6. The method of claim 1, wherein:

said normalizing said second product includes shifting said second product by one bit.

7. An apparatus, comprising:

an integrated circuit (IC) configured to generate a first product by multiplying a modulus having a most significant bit and/or a least significant bit equal to one and a quotient approximation of the modulus, generate the 1'"'"'s complement of the first product;

generate a second product by multiplying the 1'"'"'s complement and the quotient approximation, normalize and truncate the second product to obtain a quotient, and store the quotient in memory.

8. The apparatus of claim 7, wherein:

the IC is further configured to generate moduli used in RSA and/or Diffie-Helman key negotiation protocols.

9. The apparatus of claim 7, wherein:

the IC is further configured to generate a public key based on, at least in part, a remainder extracted from the quotient.

10. The apparatus of claim 7, wherein:

the IC is further configured to generate the quotient approximation using a plurality of bit-serial calculations of reciprocal of the modulus.

11. The apparatus of claim 10, wherein:

said bit-serial calculations are monotonic, and all intermediate results of said bit-serial calculations are non-negative integers.

12. The apparatus of claim 7, wherein:

said modulus is selected from the group of a National Institute of Standards and Technology (NIST) modulus and a random modulus.

13. The apparatus of claim 7, wherein:

the IC is further configured to normalize said second product by shifting the second product by one bit.

14. A computer readable storage medium comprising instructions stored thereon that when executed by a computer result in the following:

generating a first product by multiplying a modulus having a most significant bit and/or a least significant bit equal to one and a quotient approximation of the modulus;

generating the 1'"'"'s complement of the first product;

generating a second product by multiplying the 1'"'"'s complement and the quotient approximation;

normalizing and truncating the second product to obtain a quotient; and

storing the quotient in memory.

15. The computer readable storage medium of claim 14, further comprising generating a public key based on, at least in part, a remainder extracted from the quotient.

16. The computer readable storage medium of claim 14, wherein:

generating a quotient approximation includes a plurality of bit-serial calculations of reciprocal of the modulus.

17. The computer readable storage medium of claim 16, wherein:

said bit-serial calculations are monotonic, and all intermediate results of said bit-serial calculations are non-negative integers.

18. The computer readable storage medium of claim 14, wherein:

said modulus is selected from the group of a National Institute of Standards and Technology (NIST) modulus and a random modulus.

19. The computer readable storage medium of claim 14, wherein:

said normalizing said second product includes shifting said second product by one bit.

20. A system comprising:

a plurality of line cards and a switch fabric interconnecting said plurality of line cards, at least one line card comprising;

at least one physical layer component (PHY); and

an integrated circuit (IC) configured to generate a first product by multiplying a modulus having a most significant bit and/or a least significant bit equal to one and a quotient approximation of the modulus, generate the 1'"'"'s complement of the first product;

generate a second product by multiplying the 1'"'"'s complement and the quotient approximation, normalize and truncate the second product to obtain a quotient, and store the quotient in memory.

21. The system of claim 20, wherein:

the IC is further configured to generate moduli used in RSA and/or Diffie-Helman key negotiation protocols.

22. The system of claim 20, wherein:

the IC is further configured to generate a public key based on, at least in part, a remainder extracted from the quotient.

23. The system of claim 20, wherein:

the IC is further configured to generate the quotient approximation using a plurality of bit-serial calculations of reciprocal of the modulus.

24. The system of claim 23, wherein:

said bit-serial calculations are monotonic, and all intermediate results of said bit-serial calculations are non-negative integers.

25. The system of claim 20, wherein:

said modulus is selected from the group of a National Institute of Standards and Technology (NIST) modulus and a random modulus.

26. The system of claim 20, wherein:

the IC is further configured to normalize said second product by shifting the second product by one bit.