改进的二进制左移模逆算法

摘要

一种改进的二进制左移模逆算法，对于给定的模数p，p的位数在计算模逆过程中，跳出循环的条件为c_u=n-1或c_v=n-1，即c_u、c_v与常数n-1的比较，其中，u、v是用来存储需要左移数据的n位中间变量，分别初始化为p、a，r是用来通过左移得到模逆的中间变量，初始化为0，当算法结束后，r中的值就是所求的模逆结果，c_u表示u左移的次数，c_v表示v左移的次数，本发明还提供了实现该算法的电路结构，本发明的算法具有更精简的操作步骤，占用更少的存储单元，从而减少了电路面积以及降低了电路功耗，更好地满足了低端密码系统的低功耗要求。

主权项

1.一种改进的二进制左移模逆算法，素数域GF(p)上整数a的模逆定义为：对于素数p和整数a∈[1,p-1]，存在唯一的整数i∈[1,p-1]，使得i·a≡1(mod p)，则整数i为a的逆元，记作：i≡a^-1(mod p)，其特征在于，对于给定的模数p，p的位数在计算模逆过程中，跳出循环的条件为c_u=n-1或c_v=n-1，即c_u、c_v与常数n-1的比较，其中，u、v是用来存储需要左移数据的n位中间变量，分别初始化为p、a，r是用来通过左移得到模逆的中间变量，初始化为0，当算法结束后，r中的值就是所求的模逆结果，c_u表示u左移的次数，c_v表示v左移的次数。