# US 2025/0147732 A1 · Parallel polynomial modular multiplication using ntt and inverse ntt

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

- Number: US 2025/0147732 A1
- Document ID: US20250147732A1
- Status: Published application
- Kind: A1
- Application number: 18/500,670
- Filed: 2023-11-02
- Published: 2025-05-08
- Earliest claimed: 2023-11-02
- Applicants: Regents of the University of Minnesota; Clemson University Research Foundation
- Inventors: Keshab K. Parhi; Weihang Tan; Sin-Wei Chiu; Antian Wang; Yingjie Lao
- Web page: https://patentgrep.com/patent/US20250147732A1

## CPC

- G06F 7/722: {Modular multiplication (G06F7/724, G06F7/727, G06F7/728 take precedence)}
- G06F 7/728: {using Montgomery reduction}
- 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

A method comprises receiving a modulus for a number-theoretic transform of a polynomial and selecting a plurality of prime moduli whose product forms the modulus for the number-theoretic transform, wherein the plurality of prime moduli are selected by giving preference to prime moduli having fewer ones in a binary representation of the prime moduli. For each prime modulus in the plurality of prime moduli: dividing a coefficient of the polynomial into segments and performing modular reduction of the segments relative to the prime modulus. Performing the modular reduction of at least one segment comprises implementing a multiplication of a value by a modular reduction of a base value relative to the prime modulus using a shift-add-unit having a smaller area requirement than a modular multiplier. A modular reduction of the coefficient relative to the prime modulus is determined based on the modular reductions of the segments.

## Claims

### Claim 1

A method of reducing chip area required to perform a number-theoretic transform of a polynomial using parallel processing, the method comprising:
receiving the modulus for the number-theoretic transform;
selecting a plurality of prime moduli whose product forms the modulus for the number-theoretic transform, wherein the plurality of prime moduli are selected by giving preference to prime moduli having fewer ones in a binary representation of the prime moduli;
for each prime modulus in the plurality of prime moduli:
selecting a coefficient of the polynomial;
dividing the coefficient into segments;
performing modular reduction of the segments relative to the prime modulus, wherein performing the modular reduction of at least one segment comprises implementing a multiplication of a value by a modular reduction of a base value relative to the prime modulus using a shift-add-unit having a smaller area requirement than a modular multiplier; and
producing a modular reduction of the coefficient relative to the prime modulus based on the modular reductions of the segments.

### Claim 2 (depends on 1)

The method of claim 1 wherein performing the modular reduction of at least one segment comprises implementing a multiplication of a value by a square of a modular reduction of a base value relative to the selected prime modulus using two shift-add-units in series, each shift-add-unit having a smaller area requirement than a modular multiplier.

### Claim 3 (depends on 1)

The method of claim 1 further comprising:
grouping the segments into a plurality of blocks;
for each block, using a same circuit design to form a respective sum for the respective segments of the block, the circuit design comprising a plurality of shift-add-units.

### Claim 4 (depends on 3)

The method of claim 3 further comprising:
for at least one block, performing a modular reduction of the sum relative to the selected prime modulus and then multiplying the modular reduction of the sum by the modular reduction of the base value raised to a respective power designated for the block.

### Claim 5 (depends on 1)

The method of claim 1 further comprising:
performing the steps of selecting a coefficient, dividing the coefficient into segments performing modular reduction of the segments and producing a modular reduction coefficient for each coefficient in the polynomial to produce a modular reduction of the polynomial.

### Claim 6 (depends on 5)

The method of claim 5 further comprising performing a number-theoretic transform of the modular reduction of the polynomial to produce a transformed polynomial, performing a mathematical operation on the transformed polynomial to produce a result polynomial and performing an inverse number-theoretic transform of the result polynomial.

### Claim 7 (depends on 6)

The method of claim 6 wherein performing the number-theoretic transform of the modular reduction of the polynomial comprises using a first folding set and wherein performing the inverse number-theoretic transform of the modular reduction comprises using a second folding set, wherein the second folding set is different from the first folding set.

### Claim 8

A specialized circuit for performing a number-theoretic transform, the specialized circuit comprising:
a decomposition circuit for decomposing a coefficient of a polynomial into a plurality of values for a plurality of segments of the coefficient;
a plurality of identical circuit blocks;
parallel sets of conductors connecting the decomposition circuit to the plurality of identical circuit blocks, each set of conductors carrying a respective value of the plurality of segments, wherein multiple respective sets of conductors are connected to each identical circuit block; and
wherein each identical circuit block comprises at least one shift-add-unit.

### Claim 9 (depends on 8)

The specialized circuit of claim 8 wherein each identical circuit block provides a sum at an output of the identical circuit block, each sum representing a sum of modular reductions of the segments provided to the identical circuit block.

### Claim 10 (depends on 9)

The specialized circuit of claim 9 further comprising additional elements to produce modular reduction of the coefficient from the outputs of the identical blocks.

### Claim 11 (depends on 10)

The specialized circuit of claim 10 further comprising a decomposition circuit, a plurality of identical circuit blocks, parallel sets of conductors, and additional elements for each coefficient of the polynomial such that a modular reduction of each coefficient of polynomial is produced.

### Claim 12 (depends on 11)

The specialized circuit of claim 11 further comprising a number-theoretic transform circuit that receives the modular reductions of each coefficient and that comprises a plurality of stages, each stage comprising a processing element and a delay-switch-delay circuit, wherein the delay-switch-delay circuits are controlled to implement folding sets for transforming the modular reductions of each coefficient into number-theoretic transform coefficients.

### Claim 13 (depends on 12)

The specialized circuit of claim 12 further comprising an operation circuit that performs a pointwise operation with the number-theoretic transform coefficients.

### Claim 14 (depends on 13)

The specialized circuit of claim 13 further comprising an inverse number-theoretic transform circuit that receives the results of the pointwise operation and that comprises a plurality of stages, each stage comprising a processing element and a delay-switch-delay circuit, wherein the delay-switch-delay circuit of the inverse number-theoretic transform circuit are controlled to implement a different folding set from the folding set of the number-theoretic transform.

### Claim 15

A circuit comprising:
a partial number-theoretic transform circuit comprising a plurality of stages, each stage comprising a respective processing element and a respective delay-switch-delay circuit, wherein together, the respective delay-switch-delay circuits are controlled to implement a first folding set;
a transition and operator circuit coupled to the partial number-theoretic transform circuit and providing:
a final stage of the number-theoretic transform circuit,
a pointwise operation on outputs of the number-theoretic transform circuit and,
a first stage of an inverse number-theoretic transform circuit; and
a partial inverse number-theoretic transform circuit receiving values from the first stage of the inverse number-theoretic transform circuit and comprising a plurality of stages, each stage comprising a respective processing element and a respective delay-switch-delay circuit, wherein together, the respective delay-switch-delay circuits of the inverse number-theoretic transform circuit are controlled to implement a second folding set different from the first folding set.

### Claim 16 (depends on 15)

The circuit of claim 15 wherein the partial number-theoretic transform circuit comprises a first plurality of stages for a first set of coefficients and a second plurality of stages for a second set of coefficients, wherein the delay-switch-delay circuits for the first plurality of stages and the second plurality of stages implement the first folding set.

### Claim 17 (depends on 16)

The circuit of claim 16 wherein the transition circuit comprises a final stage for the first set of coefficients comprising a first instance of a final stage processing element and the transition circuit comprises a final stage for the second set of coefficients comprising a second instance of the final stage processing element and wherein an output of the first instance of the final stage processing element and an output of the second instance of the final stage processing element are provided to a pointwise operator to perform the pointwise operation.

### Claim 18 (depends on 17)

The circuit of claim 17 wherein the first stage of the inverse number-theoretic transform circuit comprises a processing element and an output of the pointwise operator is connected to an input of the processing element.

### Claim 19 (depends on 18)

The circuit of claim 18 wherein the pointwise operator begins performing the pointwise operation on values at the output of the first instance and second instance of the final stage processing element during a next clock cycle after the values appear at the outputs of the first instance and second instance of the final stage processing element.

### Claim 20 (depends on 18)

The circuit of claim 18 wherein the processing element of the first stage of the inverse number-theoretic transform begins processing a value at the output of the pointwise operator at a next clock cycle after the value appears at the output of the pointwise operator.
