C中真正大数的因式分解

Question

我正在写一篇关于质数对当今密码学的重要性的文章。我想开发一个小型应用程序，显示用 C（低级语言，至少对我而言）编写的程序需要多长时间才能将复合数分解为质因数。我想出了一个简单的算法来做到这一点，但我运行遇到了一个问题：

我希望用户能够输入巨大的数字，例如：7777777777777777777777777772

所以计算机需要几个小时来处理它，显示我们基于素数的密码学有多好。

但在 C 中，我能找到的最大数据类型是 LONG，最大为 2147483646。

你们知道我如何在 C 中输入和处理大数字吗？

提前致谢

Answer 1

和你在纸上做的一样。您将数字分成几部分并使用长除法、长加法和长乘法。

也许最简单的方法是将数字存储为以 10 为基数的字符串，然后编写代码对这些字符串执行您需要的所有操作。你会像在纸上一样用进位做加法。乘法将通过个位数乘法结合加法（您已经做过）来完成。等等。

有很多库可以为您执行此操作，例如 libgmp 的 MPZ 库和 OpenSSL 的 BN 库。

Answer 2

Factorization of really big numbers
I would like the user to be able to type gigantic numbers, for example: 7777777777777777777777777772

这是一个 93 位的数字，不是那么大，所以可以简单地暴力破解它。

如果您有权访问 unsigned __int128，则类似于下面的内容。 C 确实指定了 64 位类型，但除此之外，您只能靠自己了。

我估计这个适度的因式分解可能需要几分钟时间。

https://www.dcode.fr/prime-factors-decomposition 以秒为单位报告答案。

当然很多可以改进。

unsigned __int128 factor(unsigned __int128 x) {
  if (x <= 3) {
    return x;
  }
  if (x %2 == 0) return 2;
  for (unsigned __int128 i = 3; i <= x/i; i += 2) {
    static unsigned long n = 0;
    if (++n >= 100000000) {
      n = 0;
      printf(" %llu approx %.0f\n", (unsigned long long) i, (double)(x/i));
      fflush(stdout);
    }
    if (x%i == 0) {
      return i;
    }
  }
  return x;
}

void factors(unsigned __int128 x) {
  do {
    unsigned __int128 f = factor(x);
    printf("%llu approx %.0f\n", (unsigned long long) f, (double)x);
    fflush(stdout);
    x /= f;
  } while (x > 1);
}

void factors(unsigned __int128 x) {
  do {
    unsigned __int128 f = factor(x);
    printf("approx %0.f approx %.0f\n", (double) f, (double)x);
    fflush(stdout);
    x /= f;
  } while (x > 1);
}

输出

approx 2 approx 7777777777777778308713283584
approx 2 approx 3888888888888889154356641792
approx 487 approx 1944444444444444577178320896
approx 2687 approx 3992699064567647864619008
 99996829 approx 14859790387308
 199996829 approx 7429777390798
 299996829 approx 4953158749339
 399996829 approx 3714859245385
 499996829 approx 2971882684351
 ...
 38399996829 approx 38696146902
 38499996829 approx 38595637421
approx 1485931918335559335936 approx 1485931918335559335936

正确的答案是使用更高效的算法，然后然后考虑所需的类型。

Answer 3

您可以使用一个结构，只需设置您想要的数字，下面的代码未经测试，但应该会给您一些指导。

我相信这应该能让你得到 4294967295 (max_int) 的某处，x 的幂是你在结构

中定义的位置

typedef struct big_number{
    int thousands;
    int millions;
    int billions;
}

//Then do some math
big_number add(big_number n1, big_number n2){
    int thousands = n1.thousands + n2.thousands; 
    int millions = n1.millions + n2.millions;
    //etc... (note each part of your struct will have a maximum value of 999
    if(thousands > 999){
         int r = thousands - 999;
         millions += r; //move the remainder up
    }
}

C中真正大数的因式分解

Factorization of really big numbers in C

c

math

primes

integer

numbers