1、介绍
考虑到RSA的安全缺陷和Elgamal公钥算法，Smith等研究人员提出了一些基于Lucas的新密码系统序列。虽然这些密码系统可以抵抗一些基于模展开的乘法性质的攻击，其计算效率并不令人满意。在参考文献里面提出了一种计算算法Q＝1的Lucas序列，但其运行时间为还是太长了。另一篇参考文献提出了一种更可行的算法，其运行时间是RSA算法的两倍。Joye随后将该算法推广到计算Lucas序列作为Q取任意值。参考文献[8]中对广义算法进行了进一步优化，通过减少乘法运算的冗余。阿里等曾还提出了另一种基于加法链的算法Lucas序列，但其效率并不比以前的那些更高。
然而，Yen-Laih算法的效率很难改进尽管其程序类似于模块化幂运算，使用的改进方案在后者中不能明确采用在前者中。对于例如m-Ary算法可以显著提高模幂运算的效率，这使得Yen-Laih算法更加缓慢。
本文提出了一种新的算法来改进Lucas序列的计算效率。这个Lucas序列的计算被转换为模
线性多项式的幂运算引入窗口化方法以减少所需的其主要计算过程中的乘法次数。结果表明，新算法的效率更高在某些情况下比Yen-Laih算法更好。
2、基于LUCAS的公钥密码系统序列
设P和Q为正整数，Lucas序列为定义为[3]：
另一种定义形式如下：
很容易证明，对于任意整数k，n
特别地，当Q＝1时，方程变为
还可以证明，对于任意正整数k和N，方程
因此Lucas序列的性质在模N条件下也是适用的。本文的剩余部分讨论了后一种情况下的问题。基于Vn的半群性质，构造了一种公钥加密算法，其主要过程如下：
(1) 密钥对生成
随机选择两个大整数p，q，并计算N=pq。选择整数e∈Zn，满足gcd（e，（q+1）（q−1）（p+1）（p−1））=1。那么（e，N）是公钥，（p，q）是私钥。
(2) 加密
设M为消息，则密码计算如下：
(3)解密第一，计算
S（N）=lcm（p−L（D，p），q−L（D，p））
其中D= C2−1,L（D，p) = D is Legendre symbol,
然后计算d = e−1 (mod S(N ))
通过扩展的欧几里得算法。最后进行以下计算：
M′ = Vd(C, 1)
可以证明M＝M，所以接收机可以得到正确的消息。
当Q=1时，可以使用另一种形式的加密算法，具有更高的安全性和更低的效率。在所有这些算法中，最重要和最昂贵的运算是Lucas序列的计算。因此，如何提高其效率是一个至关重要的问题。
3、新算法
由于改进后的Yen-Laih算法难以进一步改进，我们用另一种方法来解决这些密码系统的效率问题，即改进特征多项式算法。
特征多项式算法是通过线性多项式的模幂运算来计算Lucas序列值的一种方案。假设变量λ表示表达式中的α或β，并且n=t i=0 ai2i，其中ai为0或1，可以应用以下过程来计算λn：
当λ满足特征多项式f（λ）=λ2−Pλ+Q=0，λ2的二阶多项式可以通过关系式λ2=Pλ−Q转换为线性多项式。幂减运算等价于模f（λ）=λ2−Pλ+Q的运算。因此，该算法也可以描述为：
最终结果的形式为s1λ+s0，这意味着αn=s1α+s0，βn=s1β+s0。在表达式（2）中应用这些关系，可以得出
因此，Lucas序列Vn和Un最终被计算出来。特征多项式算法比严莱算法慢，因为需要更多的乘法运算。但是可以通过引入下面描述的窗口化方法来改进它以实现更高的速度。
设n = t i=0 nibi,，其中0≤ni<h，0≤i<t。要计算λn，可以首先计算λi=λbi的一系列值，并通过以下表达式计算λn：
设bi＝bi，则h＝b，表达式（7）转到
因此，根据表达式（7）计算λn的过程如下：
在这种方法中，预先添加了预计算过程，以推导主计算过程中的平均乘法次数。本文剩余部分将对该算法进行更详细的讨论。
4、效率
假设整数n在（1，m−1）之间，计算λn所需的线性多项式乘法次数为
λ的幂总是用线性多项式表示，因此算法的主要运算是线性多项式的乘积
每个线性多项式乘法需要6次整数乘法运算。如前所述，要通过λn计算Un和Vn，需要进行一次额外的乘法运算。因此，该算法的预期乘法次数为
在预计算过程中，应执行tlog2 b−1线性多项式平方，每个多项式平方平均需要3次整数乘法和2次整数平方。通过优化，平方运算只能使用乘法运算的一半时间。因此，预计算过程中预期的乘法次数大约为[8]中提出的Yen-Laih算法将需要4次log2m+2次乘法运算。
假设b=32，n是1024位的整数。在平均情况下，计算Lucas序列的值，Windowing算法在预计算过程中需要4076次乘法，在主过程中需要1367次乘法，而Yen-Laih算法需要4098次乘法，并且
不需要任何预计算。当Lucas序列的值被多次计算时（在这个例子中只有两次），前者可以很容易地利用后者的优势。
5、优化
一旦给定了n的长度，所提出算法的预期运行时间与b相关。如果b太大或太小，则该算法的运行时间将非常长。例如，如果b＝2，则所需乘法的预期次数为3067，远长于b＝32的情况；如果b=m，则数字变为6m−17，这是一个不可行的数字 。因此，为了获得最佳性能，应优化b的值，以使整数乘法运算最少，这反过来意味着计算λn的线性多项式乘法运算最少。
为了便于讨论，假设b=2x，x|l和2l≤n<2l+x，换句话说，窗口大小是x，并且l=x[logb m♩. 根据表达式（9），可以推导出计算λn的线性多项式乘法的预期次数为
f（x）的曲线如图1所示
在区间[1，l]f（x）是连续的，因此在[1，l]上的f（x）的最小值必须在x=1，x=l的点或其极值中。f（x）的导数为
在实践中，l≥512，则很容易找到f'（1+）＜0和f'（l−）＞0，因此f（x）取其极值的最小值。在这样的点方程f（x）＝0成立。
在最佳情况下，这就是窗口大小和指数长度的关系。如图2所示。
6、模拟
为了将新算法与Yen-Laih算法进行比较，设n是1024位的整数，这意味着l＝1024。n的值在区间[2l−1，2l）中，而不是（1，m−1），但表达式（10）也可以用于估计预期 的乘法次数，并确定优化的窗口大小x。从图2可以看出最高效率x应该是5。参数x=5的Windowing算法与Yen-Laih算法的运行时间比较如图3和图4所示，其中YLA和WA分别代表Yen-Lah算法和Windowing算法。
从图3和图4可以看出，当n的权重很小时，加窗算法很少花费时间，因为在主过程中只需要很少的乘法运算。随着n权重的增加，算法的运行时间起初快速增加，但增量率很快就会降低。这些算法的平均运行时间是n的权重是n长度的一半。因此，可以看出，新算法的平均运营时间与其最坏情况下的运营时间之间几乎没有差异。在最坏的情况下，Windowing算法的运行时间仍然小于Yen-Laih算法。当Q=1时，这两种算法之间的差异并没有那么大，但前者仍然比后者更快。因此，Windowing算法的实时效率高于Yen-Laih算法。这些仿真结果没有考虑Windowing算法的预计算成本。但很明显，当Lucas序列被重复计算时，新算法比Yen-Laih算法更有效，甚至其预计算成本也被计算在内。
7、总结
本文提出并分析了一种计算Lucas序列的新算法。与Yen-Laih算法相比，新算法更支持实时应用，并且在多次计算Lucas序列时，其整体效率高于其他算法。新算法的一个缺点是保存预先计算的值需要很大的内存空间。当存储空间不够时，或者Lucas序列只计算一次时，Yen-Laih算法是更好的选择。在其他情况下，应使用“窗口化”算法。
