SYSTEM AND METHOD FOR MULTI-PRECISION DIVISION

• US 20080069337A1
• Filed: 08/31/2006
• Published: 03/20/2008
• Est. Priority Date: 08/31/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wolrich, Gilbert M., Gopal, Vinodh, Gaubatz, Gunnar, Bace, Matt
• Granted Patent: US 7,738,657 B2
• Time in Patent Office: Days
• 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 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.

2. The method of claim 1, further comprising:

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

3. The method of claim 1, wherein:

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

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 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 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. An article comprising a storage medium having stored thereon instructions that when executed by a machine 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 article of claim 14, further comprising generating a public key based on, at least in part, a remainder extracted from the quotient.

16. The article of claim 14, wherein:

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

17. The article 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 article of claim 14, wherein:

said modulus is selected from the group of a NIST modulus and a random modulus.

19. The article 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 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.