Fast number-theoretic transform ntt acceleration chip

A fast number-theoretic transform NTT acceleration chip, the acceleration chip comprising:

• a twiddle factor computing module, comprising a plurality of pre-computing units and a plurality of real-time computing units, wherein the plurality of pre-computing units is configured to compute several initial lines of twiddle factors and an inter-line step factor in parallel by using a primitive root of unity;
• and the plurality of real-time computing units is configured to repeatedly and iteratively compute, for one line of twiddle factors of the several initial lines of twiddle factors obtained by the plurality of pre-computing units, other lines of twiddle factors different from the several initial lines of twiddle factors in parallel according to the inter-line step factor;
• a transposition module, comprising a plurality of transposition units, configured to perform transposition processing on an input sequence in parallel, to obtain a transposed sequence;
• and
• an NTT computing module, comprising a plurality of butterfly computing units, configured to perform a butterfly operation of orders and a point quantity in parallel according to the twiddle factors obtained by the twiddle factor computing module and the transposed sequence obtained by the transposition module, to obtain an output sequence, wherein the twiddle factor computing module, the transposition module, and the NTT computing module respectively correspond to different stages of a first pipeline processing task.