GENERALIZATIONS OF n-TERM KARATSUBA LIKE FORMULAE IN GF(2n) WITH NAYK ALGORITHM

• Main Author: NURSALMAN (NIM: 33212001), MUHAMAD
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/23173
• Institution: Institut Teknologi Bandung

There have been many researches that were developed to reduce multiplication operations in polynomial multiplier in GF(2n). This is important because of its connection with the efficient implementation in restricted devices, such as in elliptic curve cryptography. Two of them are the researches conducted by Paar for n=4 and Montgomery for n=5,6,7. Their researches are better than previous researches, but they do not explain their methods, how they can find the multipliers. This is the knowledge gap and in this research sought to find a method is better than what they have done in finding the multipliers. The first step is to develop a formula that is better than Generalizations of The Karatsuba Algorithm, after then develop an exhaustive search algorithm for all possible existing products. Then, combine both of these formulas and algorithm, which we refer to as the NAYK algorithm. This algorithm can explain how to reduce the multiplications significantly, that is by identifying some multiplications or products included in the solution and some products which is not included in the solution. So the rest of products is reduced significantly. Then we use the products have been identified are included in the solution, and with reference to the upper bound of the function of O(n), then the lack of products is added from a combination of existing residual products. The search space becomes much smaller significantly than the Montgomery algorithm. Further, the NAYK algorithm allows to search multiplier for n>7. NAYK algorithm is suitable for use in composite field because it can improve efficiency significantly.