loading...
Asymmetric Squaring Formulae
Montpellier, France June 25-June 27
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ARITH.2007.1118th IEEE Symposium on Computer Arith ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Jaewook Chung, University of Waterloo, Ontario, Canada
M. Anwar Hasan, University of Waterloo, Ontario, Canada
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.