C编程使用模幂计算

Question

我只是有一个简短的问题来验证我的编程和数学是否正确。如果这与主题无关，请提前抱歉，我没有其他地方可以要求获得高质量的答案；)我如何仔细检查答案是否正确？谢谢

这是我的问题:

如果一个密码系统有 2^48 个可能的 key ，并且您有 1000 台计算机，每台计算机每秒可以测试 500,000 个加密 key ，那么在最坏的情况下，您需要多少天才能恢复正确的 key ，假设蛮力搜索，当你尝试用它解密时，你能立即识别出正确的 key 吗？ (回想一下，一天有 86,400 秒。)

这是我解决问题的程序输出:

Number of keys: 2^48
Number of computers: 1000
Number of keys/persecond: 500000
Number of days: 647168000

我的代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int max_power(int base,int exp,int mod);
int main(void)
{
    int num_computers=1000;
    int keys_per_second= 500000;
    int seconds_in_day=86400;
    printf("Number of keys: 2^48\n");
    printf("Number of computers: %d\n",num_computers);
    printf("Number of keys/persecond: %d\n",keys_per_second);
    printf("Number of days: %d\n",max_power(2,48,seconds_in_day)*num_computers*keys_per_second);

    return 0;
}

int max_power(int base,int exp,int mod)
{
    if (exp == 0)
        return 1;
else if (exp%2 == 0) {
        int mysqrt = max_power(base, exp/2, mod);
        return (mysqrt*mysqrt)%mod;
    }
    else
        return (base*max_power(base, exp-1, mod))%mod;
}

最终代码(仍然不完全满意，但我会问我的教授这在测试中是否可以接受):

int main(void)
{
    double num_computers=1000;
    double keys_per_second= 500000;
    double seconds_in_day=86400;
    long double keys=pow(2.0,48);
    printf("Number of keys: %.0lf\n",keys);
    printf("Number of computers: %.0f\n",num_computers);
    printf("Number of keys/persecond: %.0f\n",keys_per_second);
    printf("============================================\n");
    printf("Time to decrypt all keys: %.2f days\n",keys/(num_computers*keys_per_second*seconds_in_day));

    return 0;
}

Answer 1

评论中指出了正确的计算。但是，您仍然不确定自己哪里出错了。

您申请 modular exponentiation这里不太正确。模幂运算只给出 x 到 y 对 z 的余数，您还需要商。