理解/使用改进的CRT功能时遇到的问题
我正在开发一个加密项目。我们需要使用NTL的大数字库,特别是使用库的CRT函数来生成公钥。该库的CRT函数不使用标准的中国剩余定理算法;它是一个修改版本,我无法准确理解它是如何工作的。理解/使用改进的CRT功能时遇到的问题
CRT(A,B,C,d)
从我可以告诉CRT如果A%B == C%d返回1,但它并非总是如此,如下面的结果,我集合b = 5,d = 6且a = c是1-6之间的随机整数:
A%b:3 C%d:3 CRT:1
A%b:0 C%d :5 CRT:1
A%b:2 C%d:2 CRT:0
A%b:1个C%d:1 CR T:0
A%B:4 C%d:4 CRT:1
A%B:1个C%d:0 CRT:1
下面是从CRT函数的代码图书馆。 ZZ是用于表示大量数据的库特定类型。
long CRT(ZZ& gg, ZZ& a, const ZZ& G, const ZZ& p){
long modified = 0;
ZZ g;
if (!CRTInRange(gg, a)) {
modified = 1;
ZZ a1;
rem(g, gg, a); // g = gg%a
RightShift(a1, a, 1); // a1 = (a >> 1)
if (g > a1) sub(g, g, a);
}
else
g = gg;
ZZ p1;
RightShift(p1, p, 1);
ZZ a_inv;
rem(a_inv, a, p);
InvMod(a_inv, a_inv, p); // a_inv = a_inv^{-1} mod p, 0 <= a_inv < p
ZZ h;
rem(h, g, p);
SubMod(h, G, h, p); // return h = (G-h)%p
MulMod(h, h, a_inv, p); // return h = (h*a_inv)%p
if (h > p1)
sub(h, h, p);
if (h != 0) {
modified = 1;
ZZ ah;
mul(ah, a, h);
if (!IsOdd(p) && g > 0 && (h == p1))
sub(g, g, ah);
else
add(g, g, ah);
}
mul(a, a, p);
gg = g;
return modified;
}
以下是图书馆提供的唯一信息。离散数学我不擅长。任何人都可以用通俗的话来解释这个函数的功能吗?
中国残留。
该版本新增至v3.7,并且明显比以前的版本更简单,更快速地使用 。
该函数作为输入G,A,G,P, 使得> 0,0 < = G < p和GCD(A,P)= 1 它计算一个” = A * P和g',使得 * g'= g(mod a); * g'= G(mod p); * -a'/ 2 < g'< = a'/ 2。 然后设置g:= g'和a:= a',并且如果g已经改变则返回1。
在正常使用情况下,输入值g满足-a/2 < g < = a/2; 然而,这在早期版本中没有记录或执行,因此为了保持向后兼容性,在g上没有限制 。这个例程运行得更快,但是,如果-a/2 < = a/2, 并且例程所做的第一件事是使条件 成立。
此外,在正常使用情况下,a和p都是奇数;然而,例程 仍然会工作,即使情况并非如此。
该例程基于以下简单事实。设置-a/2 < g < = a/2,并且让h满足 * g + a h = G(mod p); * -p/2 < h < = p/2。此外,如果p = 2 * h并且g> 0,则设置 g':= g-a h;否则,设 g':= g + a h。 然后g'如此定义满足上述要求。 看到g满足同余条件是微不足道的。 唯一要检查的是“平衡”条件 -a'/ 2 < g'< = a'/ 2也成立。
NTL :: CRT实现所谓的“Incremental Chinese Remainsdering” 这是迭代求解同时同余系统的数值方法。 所以增量式中文有同一个目标(与结果)作为中国剩余定理但前者在一次迭代中解决了两个同时同余的系统。在第二次迭代中,它解决了第一次迭代和第三次同余的输出系统等问题。用同样的方法找到三个数字的GCD = GCD(GCD(n1,n2),n3)。 让我们证明NTL :: CRT和经典中国剩余定理的计算给出与以下示例(同余系统)相同的结果。我们应该找到'a'= b1 mod m1,a'= b2 mod m2和a'= b3 mod m3。
一个” == 93
现在,让我们解决NTL库相同的系统。有两个CRT电话。
#include <cassert>
#include "NTL/ZZ.h"
int main()
{
using std::cout;
using std::endl;
using namespace NTL;
ZZ b1, b2, b3;
ZZ m1, m2, m3;
b1 = 1;
b2 = 3;
b3 = 2;
m1 = 4;
m2 = 5;
m3 = 7;
ZZ a, p, A, P; // named as in CRT implementation
// first iteration
a = b1; p = m1;
A = b2; P = m2;
assert(CRT(a, p, A, P)); // CRT returns 1 if a's value changed
cout << "1st iteration a: " << a << "\tp: " << p << endl;
// next iteration
// a and p == m1 * m2 contain result from first iteration
A = b3; P = m3;
assert(CRT(a, p, A, P));
cout << "2nd iteration a: " << a << "\tp: " << p << endl;
return 0;
}
输出:
第一迭代中:-7号码:20
第二迭代中:-47号码:140
所以结果是” == (-47 + 140 == 93)。与经典中文余数算法相同。
我真的很讨厌缩写:阴极射线管(终端)(CRT),C运行时间库。 – 2014-10-31 19:51:04
我把它写在第一段:中国剩余定理 – nhoughto 2014-10-31 20:35:17