Apparatus and method for a number theoretic transform instruction

A method, comprising:

• decoding, by a decoder of a processor, an instruction having fields for an opcode, and identifiers for a first source packed data operand corresponding to a first plurality of source packed data elements, a second source packed data operand corresponding to a second plurality of source packed data elements, a third source packed data operand corresponding to a third plurality of source packed data elements, and a destination packed data operand corresponding to a plurality of result packed data elements;
• wherein the first, second, and third plurality of source packed data elements and the result packed data elements are to be stored in one or more packed data registers;
• and
• executing the instruction by execution circuitry of the processor to perform a plurality of butterfly operations to implement a forward Number Theoretic Transform (NTT), the plurality of butterfly operations to (1) perform Montgomery multiplications of the second plurality of source packed data elements and corresponding data elements of the third plurality of source packed data elements using a modulus value and an inverse of the modulus value to generate a plurality of products;
• (2) generate a first subset of the plurality of result data elements by adding the products to corresponding source packed data elements of the first plurality of source packed data elements;
• and (3) generate a second subset of the plurality of result data elements by subtracting the products from the corresponding source packed data elements of the first plurality of source packed data elements.

A machine-readable medium having program code stored thereon which, when executed by a processor, causes the processor to perform operations comprising:

• decoding an instruction having fields for an opcode, and identifiers for a first source packed data operand corresponding to a first plurality of source packed data elements, a second source packed data operand corresponding to a second plurality of source packed data elements, a third source packed data operand corresponding to a third plurality of source packed data elements, and a destination packed data operand corresponding to a plurality of result packed data elements;
• wherein the first, second, and third plurality of source packed data elements and the result packed data elements are to be stored in one or more packed data registers;
• and
• executing the instruction by execution circuitry of the processor to perform a plurality of butterfly operations to implement a forward Number Theoretic Transform (NTT), each butterfly operation to (1) perform a Montgomery multiplication of a source packed data element of the second plurality of source packed data elements and a corresponding source packed data element of the third plurality of source packed data elements using a modulus value or an inverse of the modulus value to generate a product;
• (2) generate a first result data element of the plurality of result data elements by adding the product to a corresponding source packed data element of the first plurality of source packed data elements;
• and (3) generate a second result data element of the plurality of result data elements by subtracting the product from the corresponding source packed data element of the first plurality of source packed data elements.