Pipelined processing of polynomial computation

A circuit arrangement for computing an order N polynomial, comprising:

• a plurality of V decimation stages, each including respective multiply-and-accumulate circuitry, wherein the respective multiply-and-accumulate circuitry in each decimation stage k of the V decimation stages is configured to, in response to an input r-term and a plurality of input z-terms 0 through (Nk−1):
• generate one or more output z-terms 0 through (Nk/2−1), wherein each output z-term i of the one or more output z-terms is a sum of input z-term (2i+1) of the input z-terms and a product of input z-term 2i and the input r-term;
• and
• generate an output r-term as a square of the input r-term;
• wherein the respective multiply-and-accumulate circuitry in each decimation stage k for k≤(V−1) is configured to provide the output r-term and one or more output z-terms from decimation stage k as the input r-term and one or more input z-terms to the respective multiply-and-accumulate circuitry of decimation stage k+1;
• and
• a recursive stage having multiply-and-accumulate circuitry configured to:
• input from the respective multiply-and-accumulate circuitry of decimation stage V, the output r-term as a recursive r-term and the one or more output z-terms as a-terms 0 through (T−1), and
• generate a polynomial output value z by a recursive evaluation of the recursive r-term, the a-terms 0 through (T−1), and a modulus, p.