integer - 如何测试非常大的整数是否具有仅为 2、3 和 7 的质因数？

Question

我正在处理非常大的整数，大约以 10 为基数的 30000 位数字。大多数数字都是 1，但少数(少于 20 位数字)不是 1。

我只关心这些数字的质因数分解仅由 2、3 和 7 组成。我确信该数字不能被 5 整除，因为它不能以 0 或 5 结尾，所以我不需要检查它。

我希望能够取这个非常大的整数，如果它能被2整除，我将它反复除以2，直到结果不再能被2整除。然后，如果结果能被3整除，我将它除重复除以 3，直到结果不再能被 3 整除。最后，如果结果能被 7 整除，我会重复除以 7，直到结果不再能被 7 整除。如果最终结果是 1，那么我知道原数的质因数只有2、3、7，这就是我要找的属性。

---

我的问题:

1. Is this a good way to test whether a large number has prime factors that are only 2s, 3s, and 7s? If not, is there a more efficient way to test this?
2. What is the least costly way to store these VERY large (~30000 digits) integers? I only care about testing whether these large integers have prime factors other than 2, 3, 7. I'm open to using Java, Python, C++, C, whichever of these common languages will give me the most efficient possible search.

---

我通过搜索发现的东西:

• 许多语言都有“BigInteger”类型，该类型可能仅受可用内存的限制。这听起来不错，但我认为以 10 为基数的约 30000 个数字对应于该整数的大量内存。我不确定是否有更聪明的方法来处理这个问题。

• 数学家将我正在测试的属性称为“7-smoothness ”。如果一个正整数没有大于 7 的质因数，则它是 7 平滑的。我已经知道我要测试的数字不能被 5 整除，所以我实际上只寻找 2、3 和 7。

---

我更像是一名数学家，而不是计算机科学家，所以我对这种计算优化很陌生。

感谢任何帮助:)

Answer 1

有趣的问题。让我们调用问题 X 的号码。

Is this a good way to test whether a large number has prime factors that are only 2s, 3s, and 7s?

您概述的方法似乎是最好的，既非常快速又易于理解。另一种方法是计算 X 和 2*3*7 的最小公倍数。如果结果是 X，则 X 完全由 2、3、7 的幂组成。但是，我相信 LCM 方法的计算复杂度不如您的方法。

What is the least costly way to store these VERY large (~30000 digits) integers.

30000 位数字比密码学中通常使用的数字更大，但在我所知道的任何系统上都不算异常(exception)。它只需要大约 13k 字节的 2 进制存储空间，几乎不值得考虑。

不幸的是，存储整数的“最佳”方法有点复杂，因为它取决于数据的来源和去向。大整数通常以二进制格式存储，并且还取决于您如何定义成本。这种格式可以称为基数 2，但更准确地说，它通常存储为基数 2^w“单词”或“肢体”的序列，其中 w 是进行基本算术运算的方便大小。例如，w 通常为 32 或 64。有时它比 32 或 64 少几个位，因此 w 乘以 w 加上大量进位可以适合 64 或 128 位类型的一个字。

这种以 2 为基数的表示形式是我见过的唯一一种在一般大整数包中使用的表示形式^*。它使得计算除 X 的 2 的最大幂特别高效。如果您编写自己的代码，则可以选择其他基数进行存储，例如，在您的情况下，您可以选择基数 5 或基数 7 或基数 2*3*7=42。

基数的选择还应该考虑数据的输入方式，因为如果输入不是在底层包的基数中提供的，那么将数据从输入源转换为大整数源的成本可能会很高。

^* 还有一些大十进制包可以以 10 为基数而不是 2 为基数存储数据，这样可以方便地确定 X 中 5 或 10 的幂。您必须检查大十进制实现的详细信息，以确定它是否实际上更快，而且您对 5 或 10 的幂不感兴趣。