Five, six, and seven-term Karatsuba-like formulae
Author:
- 31 January 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 54 (3) , 362-369
Abstract
The Karatsuba-Ofman algorithm starts with a way to multiply two 2-term (i.e., linear) polynomials using three scalar multiplications. There is also a way to multiply two 3-term (i.e., quadratic) polynomials using six scalar multiplications. These are used within recursive constructions to multiply two higher-degree polynomials in subquadratic time. We present division-free formulae, which multiply two 5-term polynomials with 13 scalar multiplications, two 6-term polynomials with 17 scalar multiplications, and two 7-term polynomials with 22 scalar multiplications. These formulae may be mixed with the 2-term and 3-term formulae within recursive constructions, leading to improved bounds for many other degrees. Using only the 6-term formula leads to better asymptotic performance than standard Karatsuba. The new formulae work in any characteristic, but simplify in characteristic 2. We describe their application to elliptic curve arithmetic over binary fields. We include some timing data.Keywords
This publication has 3 references indexed in Scilit:
- More on squaring and multiplying large integersIEEE Transactions on Computers, 1994
- On fast multiplication of polynomials over arbitrary algebrasActa Informatica, 1991
- On arithmetical algorithms over finite fieldsJournal of Combinatorial Theory, Series A, 1989