Circuits and methods for computing an order N polynomial include V decimation stages, each stage including respective multiply-and-accumulate circuitry. The multiply-and-accumulate circuitry in each stage k, in response to an input r-term and a plurality of input z-terms 0 through (Nk−1), generates output z-terms 0 through (Nk/2−1) and an output r-term as a square of the input r-term. Each output z-term i 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. The multiply-and-accumulate circuitry in decimation stages k for k≤(V−1) provides 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. A recursive stage inputs from decimation stage V, the output r-term as a recursive r-term and the output z-terms as a-terms, and generates a polynomial output value z by a recursive evaluation of the recursive r-term, the a-terms, and a modulus, p.