loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
18th IEEE Symposium on Computer Arithmetic (ARITH '07)
Asymmetric Squaring Formulae
Montpellier, France
June 25-June 27
ISBN: 0-7695-2854-6
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.