时间戳

首页 > 解决方案 > El Gamal 指数查找算法

c - El Gamal 指数查找算法

问题描述

我试图找到一个数字 Z 的指数，其模 X 将给出 Y。这是我的代码：

int main()
{

    int a = 607;

    int gen = 28;
    long long b = 28;

    int c = 597;
    int i = 1;
    while (i < 10000000000)
    {
        b = b * gen;
        if ((b % a) == c)
        {
            printf("%ld\n", b);
            return i;
        }
        i++;
    }

    return 0;
}

此代码实现了计算指数的 El Gamal 算法。该程序应该返回 153，但相反，它会继续并迭代直到结束。任何人都可以为我解释一下吗？

标签： ccryptography

解决方案

不幸的是，您的描述和您的代码没有共同的变量名称。你犯了一个小错误和一个大错误：你没有采取中间结果模型 a。这是我的代码，做了一些修改：

int main(int argc, char** argv) {
    int a = 607;

    int gen = 28;
    int b = 1;

    int c = 597;
    int i = 1;
    while (i < a)
    {
        b = (b * gen) % a;
        // invariant: b == (gen**i) % a
        if (b == c)
        {
            printf("%d\n", i);
            return i;
        }
        i++;
    }
}

做算术时需要更加小心；对于新程序员来说，它非常脆弱。溢出潜伏在每个角落，对于浮动类型，underflow 也是捕食者。永远不要相信 a+b、ab、a/b 或 a*b 总能产生数学认为它应该产生的结果。

推荐阅读