Patent ID: 11206136

Abstract:
A method is provided for multiplying two polynomials. In the method, first and second polynomials are evaluated at 2t inputs, where t is greater than or equal to one, and where each input is a fixed power of two 2l/(2t) multiplied with a different power of a primitive root of unity, thereby creating 2 times 2t integers, where l is an integer such that 2l is at least as large as the largest coefficient of the resulting product multiplying the first and second polynomials. The 2 times 2t integers are then multiplied pairwise, and a modular reduction is performed to get 2t integers. A linear combination of the 2t integers multiplied with primitive roots of unity is computed to get 2t integers whose limbs in the base 2l-bit representation correspond to coefficients of the product of the first and second polynomials. The method can be implemented on a processor designed for performing RSA and/or ECC type cryptographic operations.