Parallel polynomial modular multiplication using ntt and inverse ntt

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.

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.