Pentanômios irredutíveis sobre GF(2M) para redução modular eficiente

Abstract

Este trabalho teve como objetivo propor uma analise de complexidadede pentanômios na aritmética modular polinômial em GF(2m). Para isto, foi realizado um estudo das técnicas existentes e implementado um algoritmo para determinar o numero de operações base em bits. O algoritmo teve uma heurística de algoritmos gulosos para otimizar estas operações. O resultado da computação do algoritmo para determinados pentanômios de grau de interesse foi a constituição de duas novas famílias de pentanômios irredutíveis. Com isso, e apresentada uma nova classe de pentanômio irredutível sobre F2 com o seguinte formato f(x) = x2b+c + xb+c + xb + xc + 1 onde b > c. Seja m = 2b + c eo uso de f para definir a extensão de um corpo finito F2m. E demonstrado que a complexidade da aritmética modular pode ser efetuada em3m-2 = 6b+3c-2 XORs. Entretanto, são apresentados casos particulares para quando b = 2c. Neste caso, o numero de operações cai para 12/5 m - 1. Consequentemente, o numero total de operações XOR para multiplicar F2m utilizando a família proposta e m2 + m - 1; e quando b = 2c o numero total e m2+2/5m. O atraso das portas lógicas e tão bom quanto os pentanômios encontrados na literatura. A família proposta neste trabalho apresenta uma excelente performance na redução modular para alguns graus de m, incluindo os recomendados pelo NIST, isto e, para 163, 283 e 571.<br>

Abstract : This study is aimed at proposing an analysis of pentanomials for modularreduction in GF(2m). To achieve this goal, an evaluation of the techniques for reduction was implemented that is capable to determine the number of ground operations in bits. The algorithm uses a greedy heuristic to optimize these operations. The result of the computation of the algorithm for some polynomials was the basis for the detection of two new families of irreducible pentanomials. We introducea new class of irreducible pentanomials over F2 of the formf(x) = x2b+c +xb+c +xb +xc +1 where b > c. Let m = 2b+c and usef to dene the nite eld extension F2m. We show that the bit complexity of reducing modulo f is, in general, 3m - 2 = 6b+3c - 2 XORs. In the particular case when b = 2c, we further reduce these number of operations to 125 m - 1. Consequently, the total number of XOR operations to multiply in F2m using our pentanomials is m2 + m - 1;when b = 2c this number is m2 + 25m. Our gate delay is as good as the best pentanomials found in the literature. Hence, our new classof pentanomials has excellent performance, and it is the best possible for some degree extensions m including the NIST degrees 163, 283 and 571.