Title :
A less recursive variant of Karatsuba-Ofman algorithm for multiplying operands of size a power of two
Author :
Erdem, Serdar S. ; Koç, Çetin K.
Author_Institution :
Elektronik Muhendisligi Bolumu, Gebze Yuksek Teknoloji Enstitusu, Turkey
Abstract :
We propose a new algorithm for fast multiplication of large integers having a precision of 1k computer words, where k is an integer. The algorithm is derived from the Karatsuba-Ofman Algorithm and has the same asymptotic complexity. However, the running time of the new algorithm is slightly better, and it makes one third as many recursive calls.
Keywords :
computational complexity; digital arithmetic; multiplying circuits; KOA complexity; Karatsuba-Ofman algorithm; asymptotic complexity; integer multiplication; multiprecision multiplication method; recursive call; Algorithm design and analysis; Application software; Arithmetic; Digital signatures; Elliptic curve cryptography; Elliptic curves; Power engineering and energy; Power engineering computing; Public key cryptography; Software algorithms;
Conference_Titel :
Computer Arithmetic, 2003. Proceedings. 16th IEEE Symposium on
Print_ISBN :
0-7695-1894-X
DOI :
10.1109/ARITH.2003.1207657
