Ⅰ 如何进行幂模运算
模幂乘运算采用平方乘算法,将模幂乘运算转化为模乘和模平方运算实现.
平方-乘算法:一般地,求S=ABmodN,其中A<N,B<N;将指数B表示为二进制,即
观察算法,由于指数B化为二进制后的长度不确定,多数情况下高位会存在很多个0.如果完全按照该算法实现,指数B从最高位起开始运算,在第一个1出现以前,虽进行了多次运算,但D的值一直为1;当B出现第一个1后才进入有效的模乘运算.在具体实现时,设计专门的电路从高到低扫描指数B的每一位,当在找到第一个1之前,不做任何运算,找到第一个1时,使D=A,以后根据每次扫描的6[i]值,调用模乘实现运算.
经过对多种公钥加解密算法的分析——如RSA算法,通常公钥的有效位较短,而私钥有效位较长.加密中的模幂乘运算,指数有效位很少,所以上面的改进可大大减少模乘次数,加快加密过程.以目前常用的私钥和模数1 024 bit,公钥128bit情况为例,采用上述改进可减少896次不必要的模乘.解密过程使用中国余数定理(CRT),可有效降低解密指数的长度,整个算法的执行效率得到进一步提高.
2.2 模乘及模加的实现方法
模乘采用改进的Blakley加法型算法,原理与平方-乘算法类似,核心是将模乘转化为模加实现.如通常S=(A×B)modN,A<N,B<N可以按如下方式考虑.
将B表示成二进制:
由上式可知,可以像平方一乘算法一样,将模乘转化为模加实现.
一般模加运算表示为S=(A+B)modN,观察以上模乘及模幂乘算法原理描述,可知在其调用的模加运算中,因为A<N且B<N,则(A+B)<2N,所以,
因此考虑在运算中同时计算(A+B)和(A+B-N)两个结果,运算完成后通过判断加法器与减法器的进位输出(CO)与借位输出(BO).决定哪个为本次模加的正确结果.同上,A,B,N均为l位的二进制数,若CO=1,则说明(A+B)为l+1位二进制数,必大于l位的N;若CO=0,则(A+B)和N同为l位,当BO=1时(A+B)<N,当BO=0时N≤(A+B).
从而可以在一次运算中完成加法和求模过程,使模加的运算速度提高1倍.
Ⅱ 协同优化算法(CO算法)的具体细节是什么
协同优化算法的原理是将一复杂的目标函数分解成简单的子目标函数,然后再将这些子目标函数进行协同优化。具体说来,协同优化是在优化每一子目标函数同时综合考虑其它子目标函数的结果,使子目标函数之间的优化结果能够一致。优化结果一致是指使每一变量的值在每一子目标函数的优化结果中能够一致。一般来说,可以证明,如果变量的值一致则为最优解。协同优化算法没有局部最优问题同时具有非常良好的收敛特性。 它很好地解决了许多实际中非线性优化及组合优化难题。