18th IEEE Symposium on Computer Arithmetic (ARITH '07) Asymmetric Squaring Formulae Montpellier, France June 25-June 27 ISBN: 0-7695-2854-6
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ARITH.2007.11
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.2GHz. 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.
Index Terms:
Squaring, Karatsuba algorithm, Toom- Cook multiplication algorithm, Montgomery?s Karatsuba-like formulae, multiple-precision arithmetic
Citation:
Jaewook Chung, M. Anwar Hasan, "Asymmetric Squaring Formulae," arith, pp.113-122, 18th IEEE Symposium on Computer Arithmetic (ARITH '07), 2007 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||