GF(3ⁿ)椭圆曲线快速算法研究

Research on Fast Algorithms of Elliptic Curve over GF(3ⁿ)

摘要: GF(3ⁿ)作为GF(pⁿ)更加特殊的一种类型，定义于其上的椭圆曲线密码算法有自己的优越性。快速计算椭圆曲线密码标量乘的方法之一是牺牲乘法或平方减少求逆次数，若采用逐次累加的方法计算GF(3ⁿ)上椭圆曲线标量乘3^kp ，需要2k次求逆运算。本文根据递推归纳、转换求逆为乘法的思想，推导了直接计算3^kp 的公式，使求逆运算降至一次。在逆乘率I/M较高时，其效率要优于逐次三倍点算法，并且逆乘率越大，其效率提高的越多。

Abstract: GF(3ⁿ) , as a more special type field of GF(3ⁿ) , the elliptic curve cryptosystem based on which has their own advantages. As we know, reducing the operation of inverse is an important method in elliptic curve cryptography fast calculation. It requires 2k times inversions on elliptic curves over GF(3ⁿ) to compute scalar multiplication 3^kp by individual computation. This paper deduces a formula of calculating 3^kp directly based upon the idea of recursive induction and trading inversions for multiplication, which reduces the inversion to once. The proposed algorithm is prior to multiple tripling point algorithms when the speed ratio of field inversion to field multiplication is high. And the bigger the ratio is, the more the efficiency improves.