c++ - 离散对数蛮力:有人可以向我解释C++和带有NTL的C++之间的运行时差异吗？

这是一个运行时和/或时间复杂性问题，而不是加密问题，因此请继续阅读：

在大学里，我们必须实现蛮力离散对数算法以在diffie hellman交换中找到秘密，我开始使用C ++和NTL库来实现它，因此我不必担心数据类型和大质数。

下面是带有25位素数的示例数字，我们想找到离散对数：

p = 20084173;  /* the prime */
g = 2;         /* the generator */
a = 7709318;   /* the logarithm of a */
b = 6676335;   /* the logarithm of b */

我使用NTL在C ++中实现了以下内容：

int main() {

    ZZ p, g, a, b;

    // 25 Bit
    p = 20084173;
    g = 2;
    a = 7709318;
    b = 6676335;

    exhaustiveSearch(p, g, a);
    exhaustiveSearch(p, g, b);

    return 0;
}

ZZ exhaustiveSearch(ZZ p, ZZ g, ZZ t) {
    ZZ i, x;
    i = 0;
    x = 1;
    while ((x = (x % p)) != t) {
        i++;
        x = x * g;
    }
    cout << endl << endl << "p = " << p << endl << "g = " << g << endl << "t = " << t << endl << "secret: = " << i << endl;
    return i;
}

输出（7.581s）：

p = 20084173
g = 2
t = 7709318
secret: = 557254

p = 20084173
g = 2
t = 6676335
secret: = 8949383

-> time: 7.581s

好吧，我认为那真的很长，所以我在C ++中没有NTL和正常的long对其进行了测试->想象所有ZZ被long（0.124s）取代：

p = 20084173
g = 2
t = 7709318
Secret: = 557254

p = 20084173
g = 2
t = 6676335
Secret: = 8949383

-> time: 0.124s

有人可以解释一下为什么NTL这么慢吗？请记住，我不是该领域的专家，只是试图弄清楚密码学基础知识以及如何在简单的示例中实现这些基础知识。

谢谢！

最佳答案

一般来说。 NTL是用于长整数和其他与密码有关的算术的功能强大且编写良好的库，但显然，它不能击败内置数字的效率。
请注意，在使用long类型时，所有操作都转换为单个cpu指令。它尽可能快，但仅限于32/64位。

另一方面，ZZ是一个成熟的类，需要管理其内存并能够对任意长度的整数进行操作。这是有代价的。

可能的优化。话虽如此，您可以考虑ZZ是一个类的事实来尝试优化一些事情，因此例如避免创建不必要的临时对象。

例如，考虑

x = x * g;

它在两个对象上调用operator*并将新值再次分配给x。查看它的实现，我们看到：

inline ZZ operator*(const ZZ& a, const ZZ& b)
      { ZZ x; mul(x, a, b); NTL_OPT_RETURN(ZZ, x); }

因此，将创建并返回一个新的临时对象。
我认为打电话会更有效

x *= g

因为operator*=的实现避免了临时创建

inline ZZ& operator*=(ZZ& x, const ZZ& a)
  { mul(x, x, a); return x; }

使用ZZ_p。要考虑的另一件事是，您实际上是在Z_p中进行算术运算（即以Z模p），因此您可能希望使用ZZ_p类，该类在必要时自动执行归约。

将NTL与GMP一起使用如果您关心（长）算术的性能，一个不错的主意是构建NTL，以便它将GMP用于底层的长算术。这在某种程度上比普通的NTL具有更好的性能。

关于c++ - 离散对数蛮力:有人可以向我解释C++和带有NTL的C++之间的运行时差异吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24081939/