A method includes receiving a first polynomial and a second polynomial, both of order n−1 and forming d polynomial segments from both the first polynomial and the second polynomial such that each polynomial segment is of order (n/d)−1. The polynomial segments of the first polynomial and the d polynomial segments of the second polynomial are used to form segment products. Each segment product is divided into a first polynomial substructure of order n/d and a second polynomial substructure of order (n/d)−1. A first polynomial substructure containing the first n/d coefficients of a product of the first polynomial and the second polynomial is summed with a second polynomial substructure to form a sum substructure. The sum substructure is used multiple times to determine coefficients of a polynomial representing the modulo xn+1 of the product of the first polynomial and the second polynomial.