Asymmetric Squaring Formulae
Jaewook Chung, M.A. Hasan · Proceedings/Proceedings - Symposium on Computer Arithmetic · 2007
We present efficient squaring formulae based on the Toom-Cook multiplication algorithm. The latter always requires at least one non-trivial constant division in the interpolation step. We show such non-trivial divisions are not needed in the case two operands are equal for three, four and five-way squarings. Our analysis shows that our 3-way squaring algorithms have much less overhead than the best known 3-way Toom-Cook algorithm. Our experimental results show that one of our new 3-way squaring methods performs faster than mpz_mul ( ) in GNU multiple precision library (GMP) for squaring integers of approximately 2400-6700 bits on Pentium IV Prescott 3.2 GHz. For squaring in Z[x], our 3-way squaring algorithms are much superior to other known squaring algorithms for small input size. In addition, we present 4-way and 5-way squaring formulae which do not require any constant divisions by integers other than a power of 2. Under some reasonable assumptions, our 5-way squaring formula is faster than the recently proposed Montgomery's 5-way Karatsuba-like formulae.