我在 C 中实现 RSA。我正在使用"unsigned long long int" (Top limit: 18446744073709551615).
当我必须计算4294967296 ^ 2之类的东西时，问题就来了。它应该是18446744073709551616，但我得到0 (overflow)。我的意思是，我需要计算结果超过上限的事情。
我试过使用 float、double、long double，但结果不正确。
例子：
4294967000.0 * 4294967000.0 the result is 18446741874686296064.0
but it should be 18446741531089000000
OpenSSL 示例：
#include <stdio.h>
#include <openssl/bn.h>
/* compile with -lcrypto */
int main ()
{
char p_sa[] = "4294967296";
char p_sb[] = "4294967296";
BN_CTX *c = BN_CTX_new();
BIGNUM *pa = BN_new();
BIGNUM *pb = BN_new();
BN_dec2bn(&pa, p_sa);
BN_dec2bn(&pb, p_sb);
BN_mul (pa,pb, pa,c);
char * number_str = BN_bn2hex(pa);
printf("%s\n", number_str);
OPENSSL_free(number_str);
BN_free(pa);
BN_free(pb);
BN_CTX_free(c);
return 0;
}
4294967296 是这样的：
> 女巫 4294967296 女巫 (c) 1981-2017 Alf Lacis Build: 20200823.144838 参数 ________Hex_______ _______Uns.Dec______ 1 0x0000000100000000 4294967296
如您所见，它已经在使用字节 5 (01) 的底部位。
如果对这个数字求平方，它会尝试设置字节 9 的最低位，但是 64 位无符号整数中只有 8 个字节，所以答案 0 是处理器认为正确的值。这就是为什么 UINT64_MAX (stdint.h) 的值为 1844674407370955161 5而不是 1844674407370955161 6的原因。
18446744073709551615 是十六进制的：
>女巫 18446744073709551615 女巫 (c) 1981-2017 Alf Lacis Build: 20200823.144838 参数 ________Hex_______ _______Uns.Dec______ 1 0xffffffffffffffff 18446744073709551615
“实现 RSA”+“我必须计算 4294967296 ^ 2 之类的东西”是矛盾的。要实现 RSA，不需要该计算。该算法不需要比 64 位更宽的整数。
我试过使用 float、double、long double，但结果不正确。
4294967000.0 * 4294967000.0 the result is 18446741874686296064.0
使用unsigned long long数学。典型double的精度只有 53 位，但这个计算需要 60+ 位才能得到精确的乘积。
int main(void) {
unsigned long x = 4294967000;
printf("%lu * %lu the result is %lu\n", x,x,x*x); // overflow
printf("%lu * %lu the result is %llu\n", x,x,(unsigned long long) (x*x)); // overflow
printf("%lu * %lu the result is %llu\n", x,x,(unsigned long long)x*x);// good 64-bit math
return 0;
}
输出
4294967000 * 4294967000 the result is 87616
4294967000 * 4294967000 the result is 87616
4294967000 * 4294967000 the result is 18446741531089000000