大数分解

Question

在课堂上，我们遇到了这个编程问题，目前还不知道如何解决。

给定一个正整数n。已知n = p * q，其中p和q是质数，p<=q并且对于某个给定的正整数k，|q-k*p|<10^5。你需要找到p和q。

输入：

35 1
121 1
1000730021 9

输出：

5 * 7
11 * 11
10007 * 100003

这不是作业，我们只是想解决一些有趣的问题。如果你有一些想法，请在此处发布，以便我们尝试一些东西，谢谢。

- dada

---

http://en.wikipedia.org/wiki/Integer_factorization - Matt Ball

嗯……也许这件事可以移到www.solvemyproblemoverflow.com。 - vfilby

提示：q≈kp，因此n=pq≈kp²。换句话说，p≈√(n/k)。将“≈”转换为精确的界限，这就是您的算法。 将提示中的“≈”改为精确的界限即可得到算法。具体而言，p的范围为[p_min, p_max]，其中p_min=ceil(sqrt(n/k))，p_max=floor(n/k)，ceil(x)表示不小于x的最小整数，floor(x)表示不大于x的最大整数。然后计算q=n/p，如果q和p均为素数，则输出p和q，否则更新p的值并重复执行上述步骤，直到找到一对素数为止。 - ShreevatsaR

输入格式是什么：n k？ - Kaleb Pederson

这听起来非常像是projecteuler.net的一个问题。 - nurdyguy

Answer 1

我用ECM 方法分解大整数。这是已知的最有效的算法之一。如果您想了解该算法的工作原理，那么您需要阅读很多资料，但如果您想利用它进行研究，有些人已经实现了它。例如，您可以获取这些开源软件包： GMP-ECM 适用于C / C++ 或 Pyecm 适用于Python。

$ python
>>> import math
>>> import pyecm
>>> n = 1000730021
>>> list(pyecm.factors(n, False, False, 2 * math.log(math.log(n)), 1.0))
[10007, 100003]

- grokus

Answer 2

对于你所说的这些规模的数字，最快的因数分解方法（可能）是使用埃拉托斯特尼筛法生成素数，直到大约达到该数字的平方根，然后通过试除法找出哪些是约数。

已经发明了许多用于更大数字的因数分解方法。您可能想要搜索“费马因数分解法”，“波拉德-罗（Pollard Rho）算法”，“布伦特（Brent）方法”，“Lenstra椭圆曲线”，“多项式二次筛法”和“通用数域筛法”。我按（大致）复杂性和能力因素的升序列出了这些内容，以便更好地分解更大的数字。不过，是否应该提到通用数域筛法还有待商榷 - 尽管它是目前已知的分解极大数最有效的方法，但只适用于真正大的机器 - 在约110位数字以下，MPQS更快，但要分解GNFS更快的大数字，您需要比典型桌面或服务器支持的内存更多（将1TB RAM作为起点，但可能需要更多）。

- Jerry Coffin

Answer 3

n = p * q 
|q-k*p|<10^5

给定输入的n和k。因此

q-k*p=a 

与

-10^5<=a<=10^5

将 q-k*p=a 乘以 q 并用 p*q=n 替换，得到

q^2-a*q-k*n=0

对于每个 a，解决这个二次方程：

-10^5<=a<=10^5` 

检查 q 是否被 n 整除。

解决二次方程可以在多项式时间内完成，这对于求解 2*10^5+1 方程是正确的。当然，对于小值的n和k以及大值的n和k，还有更好的算法。

正如 ypercube 所提到的，我们只需要检查方程式即可。

a^2+4*k*n

是一个正方形。

- miracle173

---

+1 很好！因此，检查 Δ = a^2+4*k*n 是否为完全平方数将使其更快。 - ypercubeᵀᴹ

Answer 4

给定输入的n和k，其中n = p * q且|q-k*p|<10^5。因此，q-k*p=a，其中-10^5<=a<=10^5。将q-k*p=a乘以q并用p*q替换得到n，则有q^2-a*q-k*n=0。对于每个-10^5<=a<=10^5，解决这个二次方程并检查q是否能够整除n。解决二次方程可以在多项式时间内完成，对于解决2*10^5+1个方程也是如此。对于小的n和k值，有更好的算法。

p在区间内

[(sqrt(k*n+2500000000)-50000)/k,(sqrt(k*n+2500000000)+50000)/k]

因此，您只需检查p的10^5/k个值。q在区间内。

[sqrt(k*n+2500000000)-50000,sqrt(k*n+2500000000)+50000]

其中始终包含约10^5个整数

- miracle173

Answer 5

以下的C程序可以在输入N时给出P和Q: https://github.com/michel-leonard/C-Quadratic-Sieve。速度大约为每秒170位RSA，输出以字符串形式提供，因为数字可能大于64位。

- Michel

Answer 6

您可以使用基于GUI的YAFU版本从http://qurancode.com尝试更大的示例。 YAFU的主要优点是其自适应性，它在分解时会自动切换算法。对于Windows 7/8/10来说，使用GUI版本真的是最好和最容易的选择。

只需点击被红心包围的黄色 PI 符号即可 :)

- Ali Adams