Improving the Karatsuba-Ofman multiplication algorithm for special applications Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/3197xq60h

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • In this thesis, we study the Karatsuba-Ofman Algorithm (KOA), which is a recursive multi-precision multiplication method, and improve it for certain special applications. This thesis is in two parts. In the first part, we derive an efficient algorithm from the KOA to multiply the operands having a precision of 2[superscript m] computer words for some integer m. This new algorithm is less complex and three times less recursive than the KOA. However, the order of the complexity is the same as the KOA. In the second part of the thesis, we introduce a novel method to perform fast multiplication in GF(2[superscript m]), using the KOA. This method is intended for software implementations and has two phases. In the first phase, we treat the field elements in GF(2[superscript m]) as polynomials over GF(2) and multiply them by a technique based on the KOA, which we call the LKOA (lean KOA). In the second phase, we reduce the product with an irreducible trinomial or pentanomial. The LKOA is similar to the KOA. However, it stops the recursions early and switches to some nonrecursive algorithms which can efficiently multiply small polynomials over GF(2). We derive these nonrecursive algorithms from the KOA, by removing its recursions. Additionally, we optimize them, exploiting the arithmetic of the polynomials over GF(2). As a result, we obtain a decrease in complexity, as well as a reduction in the recursion overhead.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0 on a Canon DR-9050C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-08-21T17:40:04Z (GMT) No. of bitstreams: 1 ErdemSerdarS2002.pdf: 535003 bytes, checksum: fa96733e787e594a5b4cea04a288123a (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-08-21T17:42:21Z (GMT) No. of bitstreams: 1 ErdemSerdarS2002.pdf: 535003 bytes, checksum: fa96733e787e594a5b4cea04a288123a (MD5)
  • description.provenance : Submitted by Kirsten Clark (kcscannerosu@gmail.com) on 2012-08-21T17:29:57Z No. of bitstreams: 1 ErdemSerdarS2002.pdf: 535003 bytes, checksum: fa96733e787e594a5b4cea04a288123a (MD5)
  • description.provenance : Made available in DSpace on 2012-08-21T17:42:21Z (GMT). No. of bitstreams: 1 ErdemSerdarS2002.pdf: 535003 bytes, checksum: fa96733e787e594a5b4cea04a288123a (MD5) Previous issue date: 2001-11-08

Relationships

In Administrative Set:
Last modified: 08/20/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items