페어링 암호 연산을 위한 F_(3^m)에서의 효율적인 세제곱근 연산 방법

Abstract

F_(3^m)에서의 Tate 페어링 또는 페어링 알고리즘 계산을 위하여 효율적인 세제곱근 계산은 매우 중요하다. (수식)의 다항식 표현 중 0이 아닌 계수들의 개수를 (수식)의 헤밍웨이트라 할 때, 이 헤밍웨이트가 세제곱근 연산의 효율성을 결정하게 된다. O. Ahmadi 등은 (수식)가 (수식)의 삼항 기약다항식이라 할 때, (수식)을 생성하는 모든 삼항 기약다항식에 대하여 (수식)의 헤밍웨이트를 계산하였다. 본 논문에서는 Shifted Polynomial Basis(SPB)가 기존의 결과보다 의 헤밍웨이트를 낮출 수 있음을 보이며, 모듈로 감산 연산이 필요없는 가장 적합한 SPB를 제공한다.