Cooley-tukey butterfly-based number theoretic transform (ntt)/inverse ntt without explicit bit reversal

A system comprising:

• a local memory to store instructions and/or data for a program;
• a scratchpad memory, coupled to the local memory, to store instructions and/or data for the program;
• and
• a plurality of execution blocks, coupled to the scratchpad memory, to execute one or more mathematic and/or logical instructions of the program, wherein each execution block is to include a plurality of register files and execution units at least including a number theoretic transform (NTT) circuit, the NTT circuit to use a decimation-in-frequency (DIF) data flow and a plurality of Cooley-Tukey butterfly stages, wherein NTT input data from the scratchpad memory is in a normal order and output data from the NTT circuit is in a bit reversed order.

A method comprising:

• decoding instructions of a plurality of threads of a program, wherein each thread is to be handled by a different set of physical resources;
• placing each decoded instruction into an instruction queue, of a plurality of instruction queues, dedicated to a particular set of the different sets of physical resources;
• streaming instructions from each instruction queue dedicated to a particular set of the different sets of physical resources;
• and
• independently executing the decoded instructions from each thread using its dedicated particular set of physical resources, wherein at least one of the instructions is a number theoretic transform (NTT) instruction to be executed using a number theoretic transform (NTT) circuit, the NTT circuit to use a decimation-in-frequency (DIF) data flow and a plurality of Cooley-Tukey butterfly stages, wherein NTT input data is in a normal order and output data from the NTT circuit is in a bit reversed order.