c - C 中大数的因式分解

Question

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

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

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

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

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

提前致谢

Answer 1

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

<小时/>

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