bignum - 如何找到非常大的因数

Question

我需要找到非常大的因子说 (10^1000) 。即如果输入是100，那么输出应该是10 10，因为（10 * 10 = 100）。如果N < =（长）的大小，这很简单，但我想知道如何找到非常大的因素说（10 ^ 1000）。我也不能使用 Big Integer 。.

Answer 1

1）正如已经指出的那样，分解大数是很困难的。事实上，它是 RSA 公钥密码学的基础已经足够难了，或者换句话说，每次你在网上买东西时，你都在指望这样一个事实，即很难分解 2^2048 的数字（给定 2^10 = 1024 大约是 10^3，2^2048 大约是 10^600)。虽然 RSA 专门使用两个大素数，而您的随机 N 可能有很多小数，这会有所帮助，但我不会指望能够很快分解 10^1000 +/- 一些随机值。

2) 你绝对可以使用字符串重新实现大数库 [来源：我有一个同学在我们学会如何做大数数学之前就这样做了] 但它会非常缓慢，而且你基本上必须将你的字符串转换回每次整数；如果你想重新实现大数字，一个稍微不那么痛苦的方法是整数数组。你仍然需要做一些额外的步骤，但至少要进行基本的数学运算，这并不是特别困难。（但它仍然不会像专门的大数库那样高效，它可以做聪明的算法。例如，将两个大数相乘，直接的方法是让 A = P * 2^32 + Q （即 A 是64 位数字表示为 2 个 32 位数字的数组）和 B = R * 2^32 + S... 直接的方法需要 4 次乘法加上一些加法加上一些处理进位）。随着大数字的大小增加，有一些方法（参见例如http://en.wikipedia.org/wiki/Karatsuba_algorithm）以减少所需的乘法次数）

3）（与试验分解相比，有一些算法可以更有效地分解数字，但目前的算法仍然无法帮助计算你在宇宙热寂之前询问的数字）

Answer 2

10^1000 正好有 1,002,001 个整数除数，稍加思考应该很容易找到它们。质因数分解是

2 * 2 * 2 * ... * 5 * 5 * 5

正好有 1,000 个二和正好 1,000 个五。