# US 2026/0133761 A1 · Systems And Methods For Calculating Large Polynomial Multiplications

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

- Number: US 2026/0133761 A1
- Document ID: US20260133761A1
- Status: Published application
- Kind: A1
- Application number: 19/385,873
- Filed: 2025-11-11
- Published: 2026-05-14
- Earliest claimed: 2021-12-23
- Assignees: Altera Corporation
- Applicants: Altera Corporation
- Inventors: Martin Langhammer; Bogdan Pasca
- Web page: https://patentgrep.com/patent/US20260133761A1

## CPC

- G06F 7/5324: {partitioned, i.e. using repetitively a smaller parallel parallel multiplier or using an array of such smaller multipliers}
- G06F 7/722: {Modular multiplication (G06F7/724, G06F7/727, G06F7/728 take precedence)}
- H04L 9/008: {involving homomorphic encryption}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

This disclosure is directed to multiplier circuitry that includes a multiplier that is configurable to generate a plurality of subproducts by performing a plurality of multiplication operations involving values having a first precision using a recursive multiplication process in which a second multiplier of the multiplier performs a second plurality of multiplication operations involving values having a second precision that are derived from the values having the first precision.

## Claims

### Claim 1

A method comprising:
receiving a first input polynomial and a second input polynomial; and
multiplying the first input polynomial and the second input polynomial based on a recursive decomposition scheme comprising:
generating sub-polynomials based on the first input polynomial and the second input polynomial;
determining a coefficient count for each of the sub-polynomials;
extending at least one of the sub-polynomials to create a common data width for each of the sub-polynomials; and
performing operations on the sub-polynomials.

### Claim 2 (depends on 1)

The method of claim 1, wherein extending the at least one sub-polynomial comprises adding a zero-valued coefficient to the at least one sub-polynomial.

### Claim 3 (depends on 2)

The method of claim 2, wherein extending the at least one sub-polynomial causes the at least one sub-polynomial to have an even coefficient count.

### Claim 4 (depends on 1)

The method of claim 1, wherein performing the operations on the sub-polynomials comprises providing the sub-polynomials to a plurality of operand circuits, the operand circuits comprising multipliers, adders, and subtractors.

### Claim 5 (depends on 4)

The method of claim 4, wherein the operand circuits correspond to a common degree.

### Claim 6 (depends on 1)

The method of claim 1, wherein the recursive decomposition scheme implements a Karatsuba-Ofman algorithm.

### Claim 7 (depends on 1)

The method of claim 1, wherein generating the sub-polynomials comprises splitting each of the first input polynomial and the second input polynomial into upper half coefficients and lower half coefficients.

### Claim 8

Polynomial multiplication circuitry comprising:
a plurality of N-degree multipliers; and
a plurality of N-degree adders, wherein the polynomial multiplication circuitry is configured to implement a recursive decomposition technique comprising extending sub-polynomials to N+1 coefficients.

### Claim 9 (depends on 8)

The polynomial multiplication circuitry of claim 8 comprising a plurality of N-degree subtractors.

### Claim 10 (depends on 9)

The polynomial multiplication circuitry of claim 9, comprising data buses to couple the plurality of N-degree multipliers, the plurality of N-degree adders, and the plurality of N-degree subtractors, wherein the data buses are a same width.

### Claim 11 (depends on 10)

The polynomial multiplication circuitry of claim 10, wherein the same width is N+1 data elements.

### Claim 12 (depends on 8)

The polynomial multiplication circuitry of claim 8, wherein the sub-polynomials comprise upper half coefficients and lower half coefficients derived from input polynomials.

### Claim 13 (depends on 12)

The polynomial multiplication circuitry of claim 12, wherein the polynomial multiplication circuitry is configured to extend a set of the sub-polynomials based on the set of sub-polynomials having an odd number of coefficients.

### Claim 14 (depends on 12)

The polynomial multiplication circuitry of claim 12, wherein the input polynomials are degree 127 polynomials, degree 255 polynomials, or degree 511 polynomials.

### Claim 15

A system comprising:
a polynomial multiplication circuit configured to multiply input polynomials based on a recursive algorithm, the polynomial multiplication circuit comprising:
a plurality of multipliers;
a plurality of adders; and
a plurality of subtractors; and
data buses configured to route sub-polynomials having a common coefficient count to the plurality of multipliers, the plurality of adders, and the plurality of subtractors.

### Claim 16 (depends on 15)

The system of claim 15, wherein the plurality of multipliers, the plurality of adders, and the plurality of subtractors correspond to a common degree.

### Claim 17 (depends on 15)

The system of claim 15, wherein the polynomial multiplication circuit is configured to generate the sub-polynomials having the common coefficient count by adding a zero-value coefficient to a set of the sub-polynomials.

### Claim 18 (depends on 17)

The system of claim 17, wherein the common coefficient count is a power of two coefficient count.

### Claim 19 (depends on 18)

The system of claim 18, wherein the recursive algorithm comprises evaluating coefficient counts of the sub-polynomials at each stage of a recursive decomposition and extending the sub-polynomials having non-standard coefficient counts.

### Claim 20 (depends on 15)

The system of claim 15 wherein the polynomial multiplication circuit and the data buses are defined in programmable logic circuitry of a field programmable gate array (FPGA).
