DocumentCode
1571583
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
fYear
2003
Firstpage
28
Lastpage
35
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Arithmetic, 2003. Proceedings. 16th IEEE Symposium on
ISSN
1063-6889
Print_ISBN
0-7695-1894-X
Type
conf
DOI
10.1109/ARITH.2003.1207657
Filename
1207657
Link To Document