Microprocessor instructions for performing polynomial arithmetic operations

• US 7,711,763 B2
• Filed: 02/21/2001
• Issued: 05/04/2010
• Est. Priority Date: 02/21/2001
• Status: Active Grant

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Stribaek, Morten, Kissell, Kevin D., Paillier, Pascal
• Primary Examiner(s): Ellis, Richard
• Application Number:
  US09/788,684
• Publication Number:
  US 20020116428A1
• Time in Patent Office: 3,359 Days
• Field of Search: 708/492, 712/219, 712/218
• US Class Current: 708/492
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10
• CPC Class Codes: G06F 7/725 over elliptic curves

Abstract

Polynomial arithmetic instructions are provided in an instruction set architecture (ISA). A multiply-add-polynomial (MADDP) instruction and a multiply-polynomial (MULTP) instruction are provided.

Claims

1. A hardware microprocessor that executes an instruction having one or more opcodes, wherein execution of the instruction causes the microprocessor to perform a polynomial arithmetic operation, comprising:

a first register to store a first set of bits corresponding to coefficients of a binary representation of a first polynomial;

a second register to store a second set of bits corresponding to coefficients of a binary representation of a second polynomial;

a high-order result register to store a third set of bits corresponding to coefficients of a high-order portion of a binary representation of a third polynomial and a low-order result register to store a fourth set of bits corresponding to coefficients of a low-order portion of the binary representation of the third polynomial;

a shift register; and

logic configured to multiply the contents of the first and second registers using the shift register to obtain an intermediate value, and to add the contents of the high-order result register to a high-order portion of the intermediate value, and the contents of the low-order result register to a low-order portion of the intermediate value to obtain a result.

2. The hardware microprocessor of claim 1 wherein a high-order portion of the result is stored in the high-order result register and a low-order portion of the low-order result register.

3. The hardware microprocessor of claim 1 wherein the instruction is part of a RISC instruction set.

4. The hardware microprocessor of claim 1 wherein the multiplication is performed using modulo two arithmetic.

5. The hardware microprocessor of claim 1 wherein the addition is performed using modulo two arithmetic.

6. The hardware microprocessor of claim 1 wherein the multiplication and the addition are performed using modulo two arithmetic.

7. A method for performing polynomial arithmetic using an instruction, the method comprising:

storing in a first register a first set of bits corresponding to coefficients of a binary representation of a first polynomial;

storing in a second register a second set of bits corresponding to coefficients of a binary representation of a second polynomial;

receiving the instruction, the instruction including one or more opcodes identifying the instruction as an instruction for performing a polynomial arithmetic operation on polynomials represented by respective sets of binary polynomial coefficients

multiplying the contents of the first and second registers using a shift register to obtain an intermediate value in response to receiving the instruction;

adding the contents of a high-order result register having stored therein coefficients corresponding to a high-order portion of a binary representation of a third polynomial to a high-order portion of the intermediate value to obtain a high-order portion of the result; and

adding the contents of a low-order result register having stored therein coefficients corresponding to a low-order portion of the binary representation of the third polynomial to a low-order portion of the intermediate value to obtain a low-order portion of the result.

8. The method of claim 7 wherein the instruction is part of an instruction set, and the instruction set comprises a RISC instruction set.

9. The method of claim 7, further comprising performing the multiplication using modulo two arithmetic.

10. The method of claim 7, further comprising performing the addition using modulo two arithmetic.

11. The method of claim 7, further comprising;

performing the multiplication using modulo two arithmetic; and

performing the addition using modulo two arithmetic.

12. The method of claim 7, further comprising:

writing a high-order portion of the result to the high-order result register; and

writing a low-order portion of the result to the low-order result register.

13. A method for performing polynomial arithmetic in an encryption or decryption process, comprising:

storing in a first register a first set of bits corresponding to coefficients of a binary representation of a first polynomial;

storing in a second register a second set of bits corresponding to coefficients of a binary representation of a second polynomial;

multiplying the contents of the first and second registers using a shift register to obtain an intermediate value;

adding the intermediate value to the contents of a high-order result register and a low-order result register to obtain a result, the result comprising a set of bits that corresponds to coefficients of a binary representation of a polynomial that results from the multiplying and adding; and

reading the result for use in the encryption or decryption process.

14. The method of claim 13, further comprising executing an instruction that identifies the first and second registers, the execution of which performs the polynomial arithmetic, wherein the instruction is part of a RISC instruction set.

15. The method of claim 13, further comprising performing the multiplication using modulo two arithmetic.

16. The method of claim 13, further comprising performing the addition using modulo two arithmetic.

17. The method of claim 13, further comprising:

performing the multiplication using modulo two arithmetic; and

performing the addition using modulo two arithmetic.

18. The method of claim 13, further comprising:

writing a high-order portion of the result to the high-order result register; and

writing a low-order portion of the result to the low-order result register.

19. A hardware microprocessor that executes one or more instructions for performing polynomial arithmetic, the microprocessor comprising:

an execution unit that processes a fetched instruction; and

a polynomial arithmetic unit used by the execution unit in processing the fetched instruction if the fetched instruction is one of the one or more instructions for performing polynomial arithmetic on polynomials represented by respective sets of binary polynomial coefficients, wherein each set of binary polynomial coefficients includes one or more bits with each bit in the set representing a different term of one of the polynomials and wherein the polynomial arithmetic unit is configured to perform a binary polynomial multiplication-addition operation by performing a binary polynomial multiplication using a shift register to determine an intermediate result and adding the intermediate result to contents of a high-order result register and a low-order result register to generate a result polynomial represented by a result set of binary polynomial coefficients that includes one or more bits with each bit in the result set representing a different term of the result polynomial,

wherein the fetched instruction comprises;

an opcode identifying the fetched instruction as an instruction for performing the binary polynomial multiplication-addition operation, and

two register identifiers associated with two respective registers of a register file that contain two respective polynomials, represented by respective sets of binary polynomial coefficients, multiplied in said binary polynomial multiplication.

20. The hardware microprocessor of claim 19 wherein the polynomial arithmetic unit is a component of a multiply/divide unit.

21. The hardware microprocessor of claim 19, wherein the fetched instruction is part of a RISC instruction set.

22. The hardware microprocessor of claim 19, wherein the binary polynomial multiplication is performed using modulo two arithmetic.

23. The hardware microprocessor of claim 19, wherein the addition is performed using modulo two arithmetic.

24. The hardware microprocessor of claim 19, wherein the binary polynomial multiplication and the addition are performed using modulo two arithmetic.

25. A computer-readable medium that comprises at least one of a semiconductor, a magnetic medium, and an optical medium, and having computer-readable program code stored thereon for enabling a computer to multiply a first and second polynomial to create an intermediate value and add the intermediate value to a third polynomial, the computer-readable program code comprising:

first computer-readable program code for causing the computer to load each of two sets of binary polynomial coefficients representing the first and second respective polynomials into two respective registers of a register file, wherein each set of binary polynomial coefficients includes one or more bits with each bit in the set representing a different term of one of the first and second polynomials;

second computer-readable program code including an instruction having;

one or more opcodes identifying the instruction as an instruction for performing a polynomial arithmetic operation on the first and second polynomials; and

two register identifiers specifying the two respective registers

wherein execution of the instruction by the computer causes the computer to multiply the first and second polynomials using a shift register to produce the intermediate value, add the intermediate value to a third polynomial to produce a result polynomial represented by a result bit set having a set of bits corresponding to coefficients of a binary representation of the result polynomial, and to write high-order portion of the result bit set to the high-order result register, and a low-order portion of the result bit set to the low-order result register.

26. The computer-readable medium of claim 25, wherein the instruction is part of a RISC instruction set.

27. The computer-readable medium of claim 25, wherein the multiplication is performed using modulo two arithmetic.

28. The computer-readable medium of claim 25, wherein the addition is performed using modulo two arithmetic.

29. The computer-readable medium of claim 25, wherein the multiplication and the addition are performed using modulo two arithmetic.

30. A hardware microprocessor that executes an instruction having one or more opcodes, wherein execution of the instruction causes the microprocessor to perform a polynomial arithmetic operation-comprising:

a first register to store a first set of bits corresponding to coefficients of a binary representation of a first polynomial;

a second register to store a second set of bits corresponding to coefficients of a binary representation of a second polynomial;

a high-order result register to store coefficients corresponding to a high-order portion of a binary representation of a third polynomial and a low-order result register to store coefficients corresponding to a low-order portion of the binary representation of the third polynomial, and

logic configured to perform an arithmetic operation on the contents of the first and second registers using a shift register to obtain an intermediate value and to add the contents of the high-order result register and the low-order result register to the intermediate value to obtain a result.

31. The hardware microprocessor of claim 30 wherein a high-order portion of the result is stored in the high-order result register and a low-order portion of the result is stored in the low-order result register.

32. The hardware microprocessor of claim 30 wherein the instruction set is part of a RISC instruction set.

33. The hardware microprocessor of claim 30, wherein the addition is performed using modulo two arithmetic.

34. A method for performing polynomial arithmetic using an instruction, the method comprising:

receiving the instruction, the instruction including one or more opcodes identifying the instruction as an instruction for performing a polynomial arithmetic operation;

storing in a first register a first set of bits corresponding to coefficients of a binary representation of a first polynomial;

storing in a second register a second set of bits corresponding to coefficients of a binary representation of a second polynomial;

performing an arithmetic operation on the contents of the first and second registers using a shift register to obtain an intermediate value;

adding the contents of a high-order result register and a low-order result register to the intermediate value to obtain a result; and

writing a high-order portion of the result to the high-order result register and a low-order portion of the result to the low-order result register, wherein the high-order result register contains a set of bits corresponding to a high-order portion of a binary representation of the result and the low-order result register contains a set of bits corresponding to a low-order portion of a binary representation of the result.

35. The method of claim 34 wherein the instruction is part of an instruction set, and the instruction set comprises a RISC instruction set.

36. The method of claim 34, further comprising performing the arithmetic operation on the contents of the first and second registers using modulo two arithmetic.

37. The method of claim 34, further comprising performing the addition using modulo two arithmetic.

38. The method of claim 34, further comprising:

performing the arithmetic operation on the contents of the first and second registers using modulo two arithmetic; and

performing the addition using modulo two arithmetic.

39. A method for performing polynomial arithmetic in an encryption or decryption process, comprising:

storing in a first register a first set of bits corresponding to coefficients of a binary representation of a first polynomial;

storing in a second register a second set of bits corresponding to coefficients of a binary representation of a second polynomial;

performing an arithmetic operation on the contents of the first and second registers using a shift register to obtain an intermediate value;

adding the intermediate value to the contents of a high-order result register and a low-order result register to obtain a result, the result comprising a set of bits that corresponds to coefficients of a binary representation of a polynomial that results from the multiplying and adding; and

reading the result for use in the encryption or decryption process.

40. The method of claim 39, further comprising executing an instruction that identifies the first and second registers, the execution of which performs the polynomial arithmetic, wherein the instruction is part of an instruction set, and the instruction set comprises a RISC instruction set.

41. The method of claim 39, further comprising performing the arithmetic operation on the contents of the first and second registers using modulo two arithmetic.

42. The method of claim 39, further comprising performing the addition using modulo two arithmetic.

43. The method of claim 39, further comprising:

performing the arithmetic operation on the contents of the first and second registers using modulo two arithmetic; and

performing the addition using modulo two arithmetic.

44. The method of claim 39, further comprising:

writing a high-order portion of the result in the high-order result register; and

writing a low-order portion of the result in the low-order result register.

45. A hardware microprocessor that executes one or more instructions for performing polynomial arithmetic, the microprocessor comprising:

an execution unit that processes a fetched instruction; and

a polynomial arithmetic unit used by the execution unit in processing the fetched instruction if the fetched instruction is one of the one or more instructions for performing polynomial arithmetic on polynomials represented by respective sets of binary polynomial coefficients, wherein each set of binary polynomial coefficients includes one or more bits with each bit in the set representing a different term of one of the polynomials and wherein the polynomial arithmetic unit is configured to perform a polynomial arithmetic operation using a shift register to determine an intermediate value, followed by an addition of the intermediate value to a third polynomial to produce a result polynomial, the result polynomial comprising a high-order portion having bits corresponding to coefficients of a high-order portion of a binary representation of the result polynomial and a low-order portion having bits corresponding to coefficients of a low-order portion of the binary representation of the result polynomial,

wherein the fetched instruction comprises;

an opcode identifying the fetched instruction as an instruction for performing the polynomial arithmetic operation; and

two register identifiers associated with two respective registers of a register file used in said polynomial arithmetic operation.

46. The hardware microprocessor of claim 45 wherein the polynomial arithmetic unit is a component of a multiply/divide unit.

47. The hardware microprocessor of claim 45, wherein the fetched instruction is part of a RISC instruction set.

48. The hardware microprocessor of claim 45, wherein the polynomial arithmetic operation is performed using modulo two arithmetic.

49. The hardware microprocessor of claim 45, wherein the addition is performed using modulo two arithmetic.

50. The hardware microprocessor of claim 45, wherein the polynomial arithmetic operation and the addition are performed using modulo two arithmetic.

51. A computer-readable medium that comprises at least one of a semiconductor, a magnetic medium, and an optical medium, and having computer-readable program code stored thereon for enabling a computer to perform a polynomial arithmetic operation on a first and second polynomial to create an intermediate value and add the intermediate value to a third polynomial, the computer-readable program code comprising:

first computer-readable program code for causing the computer to load each of two sets of binary polynomial coefficients representing the first and second respective polynomials into two respective registers of a register file, wherein each set of binary polynomial coefficients includes one or more bits with each bit in the set representing a different term of one of the first and second polynomials;

second computer-readable program code including an instruction having;

one or more opcodes identifying the instruction as an instruction for performing the polynomial arithmetic operation on the first and second polynomials; and

two register identifiers specifying the two respective registers that contain the sets of binary polynomial coefficients representing the first and second respective polynomials,

wherein execution of the instruction by the computer causes the computer to perform the polynomial arithmetic operation on the first and second polynomials using a shift register to produce the intermediate value, to add the intermediate value to a third polynomial to create a result polynomial represented by a result bit set having bits corresponding to coefficients of a binary representation of the result polynomial, and to write bits of the result bit set corresponding to high-order coefficients of the result polynomial to a high-order result register and bits corresponding to low-order coefficients of the result polynomial to a low-order result register.

52. The computer-readable medium of claim 51, wherein the instruction is part of a RISC instruction set.

53. The computer-readable medium of claim 51, wherein the polynomial arithmetic operation on the first and second polynomials is performed using modulo two arithmetic.

54. The computer-readable medium of claim 51, wherein the addition is performed using modulo two arithmetic.

55. The computer-readable medium of claim 51, wherein the polynomial arithmetic operation on the first and second polynomials and the addition are performed using modulo two arithmetic.