这个强大的质因数分解工具是怎么开发出来的？

KeyTo9_Fans

这个质因数分解工具……
https://zh.numberempire.com/numberfactorizer.php

可以在1秒内分解70位以内的任意合数。我想知道这个工具用的是什么算法？

而10^70约等于2^256，这是不是意味着256位的RSA加密系统已经不安全了？

我编程实现过Pollard-Rho算法：
https://zhuanlan.zhihu.com/p/267884783

可惜该算法只能快速分解10^38以内的合数，

如果硬要使用该算法分解70位的合数，

则需要10^(70/4)约等于3*10^17次运算，约等于1年的CPU时间，显然无法做到1秒这么快。

通过查询百度百科，可以找到这样一个词条：

https://baike.baidu.com/item/%E6 ... B%E9%80%89%E6%B3%95

但没有找到该算法对应的程序代码。

我想问一下这个算法的代码是不是非常复杂，以至于无法通过一篇科普文把算法的原理和程序实现步骤说清楚？

mathe

RSA现在512比特一下肯定已经不安全了，一般认为1K比特左右也不太安全了，最好上2K甚至3K以上。

风云剑

之前在github见过一个gnfs的，现在怎么也找不到。不过找到一个类似的，这个包含了多种算法。
https://github.com/bbuhrow/yafu
这些理论很复杂，我看不懂，后来就没继续折腾了。

lihpb00

应该也是递归算法，但算力提高了

nyy

有可能使用的是查询法。试试10^69-1241
你随机生成两个35位的大质数，然后
乘起来，应该做不到一秒钟就分解了。

nyy

论坛密码被浏览器保存了，
然后连续几天不用浏览器访问论坛，
然后是就被退出了。我感觉是这样。
不知道有没有人遇到类似的情况。

nyy

1730094121708583941745321846630716635557190568712076798609128046567341

试试这个整数，是不是一秒钟就能分解完的

nyy

nyy 发表于 2023-11-20 09:19
1730094121708583941745321846630716635557190568712076798609128046567341

试试这个整数，是不是一秒钟就 ...

网站有记忆，试试这个整数
12998212960232852288871595221751349373875268430680730735304014728525703
这个整数我没分解过

nyy

你说的一秒内，肯定不正确，因为我找到10秒这样才能分解的

nyy

Clear["Global`*"];(*清除所有变量*)
m=29
p1=NextPrime@RandomInteger[{10^(m-1),10^m}]
p2=NextPrime@RandomInteger[{10^(70-m-1),10^(70-m)}]
n=p1*p2

给你代码，根据这个代码，你应该能找到大量整数是一秒分解不完的