1. A method comprising: computing a product C of a polynomial A having n coefficients and a polynomial B having n coefficients, C having (2n−1) coefficients, where n is prime by: computing products of coefficients of A and coefficients of B for which indices (i, j) are equal; computing products of coefficients of A and B for which indices (i, j) are not equal and the sum of the indices is not equal to n or n−1; using the computed products to compute coefficients of C; and computing the nth and (n−1)th coefficients of C using a result of evaluating C at {1, −1} and the computed coefficients of C.