pow函数和long int导致问题 [英] pow function and long int causing problems

问题描述

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

加密数据=（（消息）^ e）％n 和解密数据=（（加密数据）^ 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，加密）; 
 
返回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，加密）; 
 
 long long decrypt =（long long）pow（（double）encrypt，7）％33; 
 
 printf（％llu \ n，解密）; 
 
返回0; 
 
} 
  

这是此代码的输出：

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

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

解决方案

你的代码中有一些未签名和签名的数字 - 你应该尽量避免这种情况如果可能。此外，您尝试在签名的长整数上使用％llu - 在这种情况下，您应该使用％lld 。

但这里有一个更微妙的问题。在这一行：

  long long encrypt =（long long）pow（（double）num，3）％33; 
  

pow 返回 double ，这不能保证您正在寻找的所有精度。当你施放 long long 时，你最终会失去几位数。不幸的是，C不能为计算指数提供一个很好的选择，所以你需要自己实现一些东西或使用一个库（其他一些答案已经提出了一些）。

<如果你想自己实现一个，可以在Wikipedia上找到一篇关于通过平方快速求幂的好文章：通过平方排除

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

但最后，一般来说，你的代码将受到 long long 的大小限制，或者你选择的任何类型。最终对于大数字，您应该使用其他库，或找到更好的算法。在这种情况下，您正在计算功率然后采用模数 - 这正是模块化指数算法无需处理这些库即可实现的功能。你可以在这里找到维基百科的文章：模块化指数

I am trying to impliment RSA encryption scheme. It goes something like this:

encrypted data = ((message)^e) % n and decrypted data = ((encrypted data)^d) % n

I tried to implement this in c. Here is the code :

#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;

}

I compiled this using gcc -Werror -g -o encrypt encrypt.c -lm

This is the output I get = -2, which is obviously wrong. When i try this code for smaller numbers, I get the right result. For eg:

when I set num = 2, I get the right result which is 8

I know I am either type casting wrong or I am running out of boundaries somewhere. I do need to use this code to encrypt large numbers like the one in the code above.

Could you please point out where I am going wrong.

Thanks

EDIT:

Ok as per suggestion from @Micael Oliver here is the modified code:

#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;

}

here is the output of this code :

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

which is obviously wrong as the 2nd outpt should have been 3255859

解决方案

You've got a bit of a mix of unsigned and signed numbers in your code - you should try to avoid this when possible. Also you're attempting to use %llu on a signed long long - you should use %lld in this case.

But there is a more subtle problem in play here. In this line:

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

pow returns a double, which won't guarantee all the precision you're looking for. You're going to end up losing a few digits when you cast to long long. Unfortunately C doesn't provide a good alternative for computing exponentials, so you'll need to implement something yourself or use a library (some of the other answers have suggested some).

If you want to implement one yourself, a great article on fast exponentiation by squaring can be found on Wikipedia here: Exponentiation by squaring

They provide some pseudo-code that should be obvious for coding in C.

But lastly, in general your code is going to be limited by the size of long long, or whatever type you choose. Ultimately for large numbers you should use some other library, or find a better algorithm. In this case, you're computing a power and then taking a modulus - which is exactly what Modular Exponentation algorithms can accomplish without having to deal with these libraries. You can find a Wikipedia article here: Modular Exponentiation

这篇关于pow函数和long int导致问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！