[vc_empty_space][vc_empty_space]
Generalizations of n-Term Karatsuba like Formulae in GF(2n) with NAYK algorithm
Nursalman M.a, Sasongko A.a, Kurniawan Y.a, Kuspriyantoa
a School of Electrical Engineering and Informatics, Institut Teknologi Bandung, Bandung, 40132, Indonesia
[vc_row][vc_column][vc_row_inner][vc_column_inner][vc_separator css=”.vc_custom_1624529070653{padding-top: 30px !important;padding-bottom: 30px !important;}”][/vc_column_inner][/vc_row_inner][vc_row_inner layout=”boxed”][vc_column_inner width=”3/4″ css=”.vc_custom_1624695412187{border-right-width: 1px !important;border-right-color: #dddddd !important;border-right-style: solid !important;border-radius: 1px !important;}”][vc_empty_space][megatron_heading title=”Abstract” size=”size-sm” text_align=”text-left”][vc_column_text]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. This causes the search space becomes much smaller significanly 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.[/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”Author keywords” size=”size-sm” text_align=”text-left”][vc_column_text]Composite fields,Exhaustive search algorithms,Generalizations of n-Term Karatsuba Like Formulae,Improving of Generalizations of The Karatsuba Algoritm,Polynomial multiplication[/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”Indexed keywords” size=”size-sm” text_align=”text-left”][vc_column_text]Composite Field,Exhaustive Search Algorithm,Generalizations of n-Term Karatsuba Like Formulae,Improving of Generalizations of The Karatsuba Algoritm,NAYK Algorithm,Polynomial multiplication in GF(2n)[/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”Funding details” size=”size-sm” text_align=”text-left”][vc_column_text][/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”DOI” size=”size-sm” text_align=”text-left”][vc_column_text][/vc_column_text][/vc_column_inner][vc_column_inner width=”1/4″][vc_column_text]Widget Plumx[/vc_column_text][/vc_column_inner][/vc_row_inner][/vc_column][/vc_row][vc_row][vc_column][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][/vc_column][/vc_row]