# US 2026/0093485 A1 · Apparatus and method for a number theoretic transform instruction

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2026/0093485 A1
- Document ID: US20260093485A1
- Status: Published application
- Kind: A1
- Application number: 18/900,724
- Filed: 2024-09-28
- Published: 2026-04-02
- Earliest claimed: 2024-09-28
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: Kirk S. Yap; Erdinc Ozturk; Dan Zimmerman; Wajdi K. Feghali; Regev Shemy; Manoj Sastry; Santosh Ghosh; Vinodh Gopal
- Web page: https://patentgrep.com/patent/US20260093485A1

## CPC

- G06F 9/3001: {Arithmetic instructions}
- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- G06F 9/3016: {Decoding the operand specifier, e.g. specifier format}
- G06F 9/30185: {according to one or more bits in the instruction, e.g. prefix, sub-opcode}
- G06F 9/3887: {controlled by a single instruction for multiple data lanes [SIMD]}
- G06F 17/10: Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)}
- G06F 17/14: Fourier, Walsh or analogous domain transformations {, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms (for correlation function computation G06F17/156; spectrum analysers G01R23/16)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An instruction is executed for performing a number theoretic transform (NTT). For example, one embodiment includes decode circuitry to decode the instruction; one or more packed data registers to store a first, a second, and a third plurality of source packed data elements and corresponding result packed data elements; and execution circuitry to perform the NTT using a butterfly operation including: 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. The product is added to a corresponding source packed data element of the first plurality for a first result and is subtracted from the corresponding source packed data element of the first plurality for the second result.

## Claims

### Claim 1

A processor, comprising:
decode circuitry to decode 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;
one or more packed data registers to store the first, second, and third plurality of source packed data elements and the result packed data elements; and
execution circuitry 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.

### Claim 2 (depends on 1)

The processor of claim 1, wherein the first and second plurality of result data elements are to be stored in corresponding locations of a destination register associated with the destination packed data operand.

### Claim 3 (depends on 1)

The processor of claim 1, wherein each packed data register of the one or more packed data registers comprises a 128-bit, 256-bit, or 512-bit register.

### Claim 4 (depends on 3)

The processor of claim 3, wherein each data element of the first and second plurality of source packed data elements and the result packed data elements comprise 32-bit data elements.

### Claim 5 (depends on 1)

The processor of claim 1, wherein the plurality of butterfly operations are to be performed in parallel across a corresponding plurality of lanes with a corresponding subset of the first, second, and third plurality of source packed data elements.

### Claim 6 (depends on 1)

The processor of claim 1, wherein one of the fields of the instruction is to store an immediate value, the execution circuitry to select a particular subset of data elements of the first, second, and third plurality of source packed data elements for performing the Montgomery multiplication, subtraction, and addition operations based on the immediate value.

### Claim 7 (depends on 6)

The processor of claim 6, wherein, based on the immediate value, the execution circuitry is to determine whether the Montgomery multiplication is to be performed with the modulus value and/or the inverse of the modulus value to generate the plurality of products.

### Claim 8

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.

### Claim 9 (depends on 8)

The method of claim 8, wherein the first and second subsets of result data elements are to be stored in corresponding locations of a destination register associated with the destination packed data operand.

### Claim 10 (depends on 8)

The method of claim 8, wherein each packed data register of the one or more packed data registers comprises a 128-bit, 256-bit, or 512-bit register.

### Claim 11 (depends on 10)

The method of claim 10, wherein each data element of the first and second plurality of source packed data elements and the result packed data elements comprise 32-bit data elements.

### Claim 12 (depends on 8)

The method of claim 8, wherein the plurality of butterfly operations are to be performed in parallel across a corresponding plurality of lanes with a corresponding subset of the first, second, and third plurality of source packed data elements.

### Claim 13 (depends on 8)

The method of claim 8, wherein one of the fields of the instruction is to store an immediate value, the method further comprising:
selecting, by the execution circuitry, a particular subset of data elements of the first, second, and third plurality of source packed data elements for performing the Montgomery multiplication, subtraction, and addition operations based on the immediate value.

### Claim 14 (depends on 13)

The method of claim 13, further comprising:
determining, by the execution circuitry, based on the immediate value, whether the Montgomery multiplication is to be performed with the modulus value and/or the inverse of the modulus value to generate the plurality of products.

### Claim 15

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.

### Claim 16 (depends on 15)

The machine-readable medium of claim 15, wherein the first and second subsets of result data elements are to be stored in corresponding locations of a destination register associated with the destination packed data operand.

### Claim 17 (depends on 15)

The machine-readable medium of claim 15, wherein each packed data register of the one or more packed data registers comprises a 128-bit, 256-bit, or 512-bit register.

### Claim 18 (depends on 17)

The machine-readable medium of claim 17, wherein each data element of the first and second plurality of source packed data elements and the result packed data elements comprise 32-bit data elements.

### Claim 19 (depends on 15)

The machine-readable medium of claim 15, wherein the plurality of butterfly operations are to be performed in parallel across a corresponding plurality of lanes with a corresponding subset of the first, second, and third plurality of source packed data elements.

### Claim 20 (depends on 15)

The machine-readable medium of claim 15, wherein one of the fields of the instruction is to store an immediate value, the machine-readable medium further comprising program code to cause the processor to perform the operations of:
selecting a particular subset of data elements of the first, second, and third plurality of source packed data elements for performing the Montgomery multiplication, subtraction, and addition operations based on the immediate value.
