算法 – 大数的分解

发布时间：2020-12-14 04:46:21 所属栏目：大数据来源：网络整理

导读：在课堂上我们发现了这个编程问题,目前我们还不知道如何解决它. 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 112

在课堂上我们发现了这个编程问题,目前我们还不知道如何解决它.

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

这不是家庭作业,我们只是想解决一些有趣的问题.如果您有一些想法,请在这里发布,以便我们可以尝试一下,谢谢.

解决方法

对于你在这里谈论的数字,最快的保理方法是(可能)使用Eratosthenes的Sieve来生成大约数字的平方根的素数,然后使用试验除法来找到哪一个(s) )是除数.

已经为更大数量发明了许多因子分解方法.您可能希望Google使用“Fermat的保理方法”,“Pollard Rho”,“Brent方法”,“Lenstra椭圆曲线”,“多重多项式二次筛”和“通用数字筛”.我已经列出了(粗略地)复杂性的升序和能够考虑更大数字的能力.我们是否应该提及通用数字现场筛网是值得怀疑的 – 虽然它是目前已知的最有效的方法,因为它非常大,但它只适用于大型机器 – 大约110位左右,MPQS更快,但要考虑GNFS更快的大数字,你需要比典型的桌面或服务器可以支持更多的内存(想想一个TB的RAM作为最低起点,但可能更多).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!