algorithm - 大数分解

Question

我们在类里面发现了这个编程问题，目前，我们不知道如何解决它。

The positive integer n is given. It is known that n = p * q, where p and q are primes, p<=q and |q-k*p|<10^5 for some given positive integer k. You must find p and q.

输入:

35 1
121 1
1000730021 9

输出:

5 * 7
11 * 11
10007 * 100003

这不是作业，我们只是想解决一些有趣的问题。如果您有任何想法，请将它们张贴在这里，以便我们尝试一些事情，谢谢。

Answer 1

对于您在这里谈论的大小的数字，最快的因式分解方法(可能)是使用埃拉托色尼筛法生成素数，直到大约为数字的平方根，然后使用这些素数进行试验除法以找出哪个素数一个或多个是除数。

已经为更大的数字发明了相当多的因式分解方法。您可能想在 Google 上搜索“费马因式分解法”、“Pollard Rho”、“布伦特法”、“Lenstra 椭圆曲线”、“多重多项式二次筛法”和“一般数域筛法”。我已经(大致)按照复杂性和分解更大数字的能力的升序列出了这些。不过，我是否应该提及通用数域筛选法尚待商榷——虽然它是目前已知的分解极大数的最有效方法，但它只在真正的大机器上有用——低于大约 110 位数字，MPQS速度更快，但考虑到 GNFS 速度更快的大量数据，您需要比典型台式机或服务器所能支持的内存更多的内存(将 1 TB 的 RAM 视为最低起点，但可能不止于此)。