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.