Online

Elia, Marcus

Mathematics and Statistics

2021

Ph. D.

Historically, polynomial multiplication has required a quadratic number of operations. Several algorithms in the past century have improved upon this. In this work, we focus on the Toom-Cook algorithm. Devised by Toom in 1963, it is a family of algorithms parameterized by an integer, n. The algorithm multiplies two polynomials by recursively dividing them into smaller polynomials, multiplying many small polynomials, and interpolating to obtain the product. While it is no longer the asymptotically fastest method of multiplying, there is a range of intermediate degrees (typically less than 1000) where it performs the best. Some applications, like quantum-resistant cryptosystems, require the use of polynomials whose coefficients belong to the ring of integers modulo a power of 2. A problem arises with using the Toom-Cook algorithm to multiply these polynomials because the interpolation step of the algorithm requires division by even numbers. This results in a loss of 2-adic precision. If too many bits of precision are lost, the product will be incorrect. Interpolating a polynomial from some of its values is generally easy, and different works have solved the interpolation step of the Toom-Cook algorithm with different equations. In order to track the loss of precision, it is necessary to establish and prove the general form of the solution to the system of equations. We present three sets of interpolation formulas: the matrix, natural, and efficient formulas. For any integer n > 2, we seek to find a general expression for each of the three sets of formulas, and to prove the respective loss of precision. First, for the efficient interpolation, we prove the general set of formulas. Then, for the natural interpolation, we conjecture a general set of formulas that depends on two combinatorial identities. We prove the first identity and some cases of the second identity. Finally, we prove the loss of precision of the matrix interpolation formulas.