# US 2021/0334334 A1 · Twiddle factor generating circuit for an ntt processor

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

- Number: US 2021/0334334 A1
- Document ID: US20210334334A1
- Status: Published application
- Kind: A1
- Application number: 17/259,065
- Filed: 2019-07-09
- Published: 2021-10-28
- Earliest claimed: 2018-07-10
- Assignees: Commissariat A L'energie Atomique Et Aux Energies Alternatives
- Applicants: Commissariat A L'energie Atomique Et Aux Energies Alternatives
- Inventors: Joel CATHEBRAS; Alexandre CARBON; Renaud SIRDEY; Nicolas VENTROUX
- Web page: https://patentgrep.com/patent/US20210334334A1

## CPC

- G06F 9/3001: {Arithmetic instructions}
- G06F 17/142: {Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm}
- G06F 7/722: {Modular multiplication (G06F7/724, G06F7/727, G06F7/728 take precedence)}
- G06F 7/724: {Finite field arithmetic (for error detection or correction in general H03M13/00, in computers G06F11/10)}
- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- G06F 9/3885: {using a plurality of independent parallel functional units}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A circuit for generating twiddle factors for an NTT processor. The circuit includes a cache management manager, a modular multipliers bank, and a central controller. The cache management module includes a local controller and a cache memory in which operands are stored for calculating future twiddle factors. The modular multipliers bank includes an interconnection matrix at the input distributing operands on the modular multiplier inputs. The circuit can be configured to minimise the size of the cache memory and/or reduce the latency of the twiddle factor sequence calculation. Finally, the generating circuit may include several calculation management modules sharing the same modular multipliers bank to generate sequences of twiddle factors on several finite fields.

## Claims

### Claim 1

A circuit generating twiddle factors (400) on at least one finite field (Zp), for an NTT stream processor, said generating circuit being designed to generate at least one sequence of N twiddle factors {ψ0, ψ1, ψ2, . . . , ψN−1} wherein ψ is a root of unity in this field, wherein:
at least one cache management module comprising a cache memory and a local controller controlling write and read in the cache memory;
a modular multipliers bank comprising a plurality of W modular multipliers operating in parallel, each modular multiplier performing one multiplication on said field of two operands derived from a word read from the cache memory;
a central controller initialising the cache memory with the G first twiddle factors of the sequence and controlling the cache manager so as, in each calculation cycle of a plurality T=N/W of calculation cycles, to supply a word read from the cache memory to the modular multipliers bank, to write a word into the cache memory at the end of each calculation cycle except for the last of said plurality, comprising the W results output from said modular multipliers, and to provide these W results at the end of each calculation cycle at the output from the generator, as W consecutive twiddle factors of said series.

### Claim 2 (depends on 1)

The circuit generating twiddle factors according to claim 1, wherein the bank of W modular multipliers performs the R0=U0U1 mod p; R1=U0U2 mod p; . . . , ; RW−1=U0UW mod p multiplications respectively, wherein U0U1 . . . UW is the word read from the cache memory and Uw, w=0, . . . , W are the operands input to the modular multipliers bank and Rw, w=0, . . . , W−1 are the W output results from these multipliers.

### Claim 3 (depends on 2)

The circuit generating twiddle factors according to claim 2, wherein the cache memory comprises a first part with size W and a second part with size LatMM+1 wherein LatMM is the latency of the modular multipliers bank, the central controller initialising the content of the first part of the cache memory with ψ1, ψ2, . . . , ψW and the second part with ψW, the word read from the cache memory for the first calculation cycle being U0U1 . . . UW=ψWψ1ψ2 . . . ψW.

### Claim 4 (depends on 3)

The circuit generating twiddle factors according to claim 3, wherein, each time that a twiddle factor calculated by the modular multipliers bank is a multiple of W, an address is incremented in the second part of the cache memory and the twiddle factor is stored at the address thus incremented.

### Claim 5 (depends on 4)

The circuit generating twiddle factors according to claim 4, wherein the cache memory also comprises an address pointer (Ind) pointing to the address at which the value of U0 should be read for the next calculation cycle, the values of U1 . . . UW being read from the first part and the word U0U1 . . . UW formed from the concatenation of these values being supplied to the modular multipliers bank for the next calculation cycle.

### Claim 6 (depends on 1)

The circuit generating twiddle factors according to claim 1, wherein the bank of W modular multipliers performs the R0=U0U1 mod p; R1=U1U1 mod p; R1=U1U2 mod p . . . ;
R
W
-
1
=
U
W
2
⁢
U
W
2
mop p multiplications respectively, wherein
U
0
⁢
U
1
⁢
⁢
…
⁢
⁢
U
W
2
is the wont react from the cache memory and Uw, w=0, . . . ,
W
2
are the operands input to the modular multipliers bank and Rw, w=0, . . . , W−1 are the W output results from these multipliers.

### Claim 7 (depends on 6)

The circuit generating twiddle factors according to claim 6, wherein the size of the cache memory is
(
N
W
-
1
)
⁢
W
2
,
the central controller initialising the content of the cache memory with ψ2, ψ3, . . ,
ψ
W
2
.

### Claim 8 (depends on 7)

The circuit generating twiddle factors according to claim 7, wherein, after a word is read in the cache memory to prepare a calculation cycle, the content of this memory is offset by
W
2
and, at the end of the calculation cycle, the word composed of the output results from the modular multipliers bank is stored after the content thus offset.

### Claim 9 (depends on 1)

The circuit generating twiddle factors according to claim 1, wherein said generating circuit will generate a plurality L of sequences of N twiddle factors {ψ10, ψ11, ψ12, . . . , ψ1N} wherein the elements ψ1, I=0, . . . , L−1 are the Nth roots of unity in a plurality L of finite fields (ZP1, I=0, . . . , L−1), said generating circuit comprising:
a plurality L of cache management modules each cache management module 810 comprising a cache memory and a local controller controlling write and read in the corresponding cache memory;
a modular multipliers bank shared between the different cache management modules;
a central controller initialising in turn the L cache memories with the G first twiddle factors of the sequence {ψ10, ψ12, ψ12, . . . , ψ1N}, and controlling each cache manager so as, for each calculation cycle of a plurality T=N/W of calculation cycles, to supply a word read from the cache memory to the modular multipliers bank, to write a word into the cache memory associated with this cache manager at the end of each calculation cycle except for the last of said plurality, comprising the W results output from the modular multipliers bank, and to provide these W results at the end of each calculation cycle at the output from the generator, as a set of W consecutive twiddle factors of said sequence, the sets of W twiddle factors for the L sequences being supplied interlaced.

### Claim 10 (depends on 7)

The circuit generating twiddle factors according to claim 7, wherein each cache management module is provided at the input to a multiplexer controlled by the central controller, so as to transmit either an initialisation word of the G first twiddle factors of the corresponding sequence, or W results from the modular multipliers bank, to the cache memory associated with the cache management module.
