c - pow 函数和 long int 导致问题

Question

我正在尝试实现 RSA 加密方案。它是这样的:

加密数据 = ((message)^e) % n 和解密数据 = ((encrypted data)^d) % n

我试图在 c 中实现它。这是代码:

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

int main(){

    long int num = 3255859; 
    long int encrypt =(int)pow((double) num,3) % 33;
    printf("%ld\n",encrypt);

    return 0;

}

我使用 gcc -Werror -g -o encrypt encrypt.c -lm 编译了它

这是我得到的输出 = -2，这显然是错误的。当我为较小的数字尝试此代码时，我得到了正确的结果。例如:

当我设置 num = 2 时，我得到了正确的结果，即 8

我知道我要么类型转换错误，要么我在某处超出了界限。我确实需要使用此代码来加密大数字，如上面代码中的数字。

能否请您指出我哪里出错了。

谢谢

编辑:

根据@Micael Oliver 的建议，这里是修改后的代码:

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

int main(){

    unsigned long long  num = 3255859; 

    long long encrypt =(long long)pow((double) num,3) % 33;

    printf("%llu\n",encrypt);

    long long decrypt =(long long)pow((double) encrypt,7) % 33;

    printf("%llu\n",decrypt);

    return 0;

}

这是这段代码的输出:

Notra:Desktop Sukhvir$ gcc -Werror -g -o encrypt encrypt.c -lm
Notra:Desktop Sukhvir$ ./encrypt
18446744073709551608
18446744073709551614

这显然是错误的，因为第二个输出应该是 3255859

Answer 1

您的代码中混合了一些无符号和有符号数字 - 您应该尽可能避免这种情况。此外，您还试图在 signed long long 上使用 %llu - 在这种情况下您应该使用 %lld。

但是这里有一个更微妙的问题。在这一行中:

long long encrypt =(long long)pow((double) num,3) % 33;

pow 返回一个 double，它不能保证您正在寻找的所有精度。当您转换为 long long 时，您最终会丢失几位数字。不幸的是，C 并没有为计算指数提供一个很好的替代方案，因此您需要自己实现一些东西或使用一个库(其他一些答案已经提出了一些建议)。

如果您想自己实现一个，可以在维基百科上找到一篇关于通过平方快速求幂的好文章:Exponentiation by squaring

它们提供了一些伪代码，对于用 C 编写代码来说应该是显而易见的。

但最后，通常您的代码将受到 long long 的大小或您选择的任何类型的限制。最终对于大量你应该使用一些其他的库，或者找到一个更好的算法。在这种情况下，您正在计算一个幂，然后取一个模数——这正是模幂算法可以完成的，而无需处理这些库。您可以在此处找到维基百科文章:Modular Exponentiation