基于GF(2n)椭圆曲线点积改进算法的PKI数据传输模型研究(2)

    设K为有限域 ，取K上的椭圆曲线为E: ,其中x,y,a,b∈K,b≠0,则E上的加法运算定义如下：

   设P，Q∈E。P，Q≠O(O为无穷远点)， ； ，则P的逆元 ，且 。

   若Q≠ ，Q≠P，则 ，其中

;  ;

  

    若 , P≠q, 则 其中

  ;  ;

  

    特别的，对任意P∈E,P+Q=P,对实数0,0P=O, 则nP=P+P+P…..+P 。

也就是椭圆点P自身加n次。^[4]

    第一种解法：

    参考文献[4]给出了计算 P的最基本算法：“加-减”(addition-subtraction)算法J，它是“加-与-倍加”(add-and-double)算法的改进，无需预处理。在仿射坐标模式下，对给定的整数，设P为椭圆曲线 E上的一个随机点，B(n )为给定的任意大正整数的二进制序列，显然n和B(n )可分别表示成如下形式[5]：

                 (1)

    其中， a_i∈{0,1},i=0,1,…t-1 于是根据点积定义，nP可写成

   (2)

    INPUT:大正整数n和椭圆点P

    OUTPUT:Q=nP

    ①

    ③for i form k-2 downto 0 do

       

      

        Else

       

    ④   

    效率分析：该算法要进行8/31og2n次乘法和4/31og2n次求逆运算，在射影坐标模式下要8/31og2n次乘法。

 

    第二种解法：

    对NAF做了改进[6]，使得B(n)序列中任3个(或以上)的连续元素中至少有一个为0，再通过对 做预计算来提高运算效率。

   

   

    ① (预先做倍点运算)

    ②set Q=0,i=0;

    ③for i from k-1 to 0

    效率分析：该算法至多做2(k-1)/3次点加法运算，而每次点加法运算仅需要域 上元素的3次乘法，9次加法和一次求逆。比之算法一有了较大的提高。

    算法3:

    在算法1和算法2的基础上，通过设置合适的窗口长度来减少点加运算次数。以达到提高运算效率的目的[7]。

    INPUT: 大正整数n的 表示和椭圆点P

    OUTPUT：Q=nP

    ⑴

    ⑵

    ⑶ while i>=3 do

3.4 数据分析 4  总结 参考文献