RSA爆破——大数因数分解库
下面为博客摘要，详细内容请看http://keke046.github.io/2021/12/01/rsa-crack/
inria。net/projects/yafu/)：Quadratic Sieve，直接下载解压就可以用了。```bashyay -S cado-nfs-git```# 理论性能单核的机器（理论上）：| rsa-bit | ecm | qs | gnfs || ------: | :------------------------------- | :------------------------------- | :----------------------------- || 128 | 0s | 0s | 0s || 256 | 0s | 3s | 6s || 512 | 9月 3天 8h 16m 42s | 19年 2月 25天 4h 30m 39s | 2月 26天 12h 37m 49s || 768 | $10^{6}$年 0月 16天 18h 30m 16s | $10^{7}$年 1月 13天 19h 44m 31s | $10^{3}$年 8月 24天 23h 55m 7s || 1024 | $10^{11}$年 3月 22天 21h 48m 56s | $10^{13}$年 11月 10天 0h 24m 24s | $10^{7}$年 6月 7天 5h 22m 50s || 2048 | $10^{28}$年 8月 0天 8h 52m 12s | $10^{31}$年 8月 0天 8h 4m 52s | $10^{17}$年 4月 8天 0h 20m 56s |16核机器（理论上）：| rsa-bit | ecm | qs | gnfs || ------: | :------------------------------ | :------------------------------ | :------------------------------ || 128 | 0s | 0s | 0s || 256 | 0s | 0s | 0s || 512 | 17天 2h 1m 2s | 1年 2月 12天 19h 46m 54s | 5天 9h 47m 21s || 768 | $10^{4}$年 6月 1天 1h 9m 23s | $10^{6}$年 3月 2天 17h 44m 1s | $10^{2}$年 9月 16天 13h 29m 41s || 1024 | $10^{10}$年 1月 22天 1h 18m 56s | $10^{12}$年 11月 6天 6h 24m 24s | $10^{6}$年 4月 4天 4h 50m 10s || 2048 | $10^{27}$年 8月 0天 8h 52m 12s | $10^{29}$年 8月 0天 8h 4m 52s | $10^{16}$年 4月 8天 0h 20m 56s |用神威太湖之光来算（10649600个核心）| rsa-bit | ecm | qs | gnfs ||----------:|:--------------------------------|:-------------------------------|:---------------------------------|| 128 | 0s | 0s | 0s || 256 | 0s | 0s | 0s || 512 | 2s | 56s | 0s || 768 | 1月 12天 11h 9m 9s | 5年 5月 3天 17h 59m 40s | 4h 45m 40s || 1024 | $10^{4}$年 9月 17天 11h 19m 57s | $10^{6}$年 8月 18天 21h 9m 59s | 2年 0月 22天 2h 13m 47s || 2048 | $10^{21}$年 0月 8天 0h 28m 44s | $10^{23}$年 4月 20天 0h 40m 0s | $10^{10}$年 10月 22天 4h 56m 24s |。[CADO-NFS](https://cado-nfs。gitlabpages。fr/)：GNFS，yay 直接装就可以了。!-- indicate-the-source --# 工作量单位* FLOPS：每秒浮点运算量（FLoating point Operations Per Second）* G-Hour：指1GFLOPS的机器工作1小时的计算量。* CPU-Hour, Core-Year: CPU单线程工作1小时的计算量，CPU泛指有1GFLOPS的参考CPU* CPU-Year, Core-Year：CPU单线程工作1年的计算量，CPU泛指有1GFLOPS的参考CPU!-- more --# 因数分解算法对于大数$n$，最小素因子是 $p$ 的情况下（$p\le\sqrt n$）找最某一个素因子：* 暴力分解：$O(p)$* Pollard Rho：$O(\sqrt p)$* ECM (Elliptic Curve Method)：$O\left(\exp (\sqrt{2\log p \log\log p})\right)$找全部素因子：* SQUFOF (SQUare FOrms Factorization)：$O\left(\exp(\frac{1}{3}\log n)\right)$* CFRAC (Continued FRACtions)：$O\left(\exp(\sqrt{2 \log n \log \log n})\right)$* QS (Quadratic Sieve), MPQS (Multiple Polynomial QS)：$O(\exp(\sqrt{\log n \log \log n}))$* SNFS (Special Number Field Sieve) 对特殊的数：$O\left(\exp(\sqrt[3]{\frac{32}{9}\log n (\log \log n)^2})\right)$* GNFS (General Number Field Sieve)：$O\left(\exp(\sqrt[3]{\frac{64}{9}\log n (\log \log n)^2})\right)$# 开源库[YAFU](https://sourceforge
工作量单位
- FLOPS：每秒浮点运算量（FLoating point Operations Per Second）
- G-Hour：指1GFLOPS的机器工作1小时的计算量。
- CPU-Hour, Core-Year: CPU单线程工作1小时的计算量，CPU泛指有1GFLOPS的参考CPU
- CPU-Year, Core-Year：CPU单线程工作1年的计算量，CPU泛指有1GFLOPS的参考CPU
inria。net/projects/yafu/)：Quadratic Sieve，直接下载解压就可以用了。```bashyay -S cado-nfs-git```# 理论性能单核的机器（理论上）：| rsa-bit | ecm | qs | gnfs || ------: | :------------------------------- | :------------------------------- | :----------------------------- || 128 | 0s | 0s | 0s || 256 | 0s | 3s | 6s || 512 | 9月 3天 8h 16m 42s | 19年 2月 25天 4h 30m 39s | 2月 26天 12h 37m 49s || 768 | $10^{6}$年 0月 16天 18h 30m 16s | $10^{7}$年 1月 13天 19h 44m 31s | $10^{3}$年 8月 24天 23h 55m 7s || 1024 | $10^{11}$年 3月 22天 21h 48m 56s | $10^{13}$年 11月 10天 0h 24m 24s | $10^{7}$年 6月 7天 5h 22m 50s || 2048 | $10^{28}$年 8月 0天 8h 52m 12s | $10^{31}$年 8月 0天 8h 4m 52s | $10^{17}$年 4月 8天 0h 20m 56s |16核机器（理论上）：| rsa-bit | ecm | qs | gnfs || ------: | :------------------------------ | :------------------------------ | :------------------------------ || 128 | 0s | 0s | 0s || 256 | 0s | 0s | 0s || 512 | 17天 2h 1m 2s | 1年 2月 12天 19h 46m 54s | 5天 9h 47m 21s || 768 | $10^{4}$年 6月 1天 1h 9m 23s | $10^{6}$年 3月 2天 17h 44m 1s | $10^{2}$年 9月 16天 13h 29m 41s || 1024 | $10^{10}$年 1月 22天 1h 18m 56s | $10^{12}$年 11月 6天 6h 24m 24s | $10^{6}$年 4月 4天 4h 50m 10s || 2048 | $10^{27}$年 8月 0天 8h 52m 12s | $10^{29}$年 8月 0天 8h 4m 52s | $10^{16}$年 4月 8天 0h 20m 56s |用神威太湖之光来算（10649600个核心）| rsa-bit | ecm | qs | gnfs ||----------:|:--------------------------------|:-------------------------------|:---------------------------------|| 128 | 0s | 0s | 0s || 256 | 0s | 0s | 0s || 512 | 2s | 56s | 0s || 768 | 1月 12天 11h 9m 9s | 5年 5月 3天 17h 59m 40s | 4h 45m 40s || 1024 | $10^{4}$年 9月 17天 11h 19m 57s | $10^{6}$年 8月 18天 21h 9m 59s | 2年 0月 22天 2h 13m 47s || 2048 | $10^{21}$年 0月 8天 0h 28m 44s | $10^{23}$年 4月 20天 0h 40m 0s | $10^{10}$年 10月 22天 4h 56m 24s |。[CADO-NFS](https://cado-nfs。gitlabpages。fr/)：GNFS，yay 直接装就可以了。!-- indicate-the-source --# 工作量单位* FLOPS：每秒浮点运算量（FLoating point Operations Per Second）* G-Hour：指1GFLOPS的机器工作1小时的计算量。* CPU-Hour, Core-Year: CPU单线程工作1小时的计算量，CPU泛指有1GFLOPS的参考CPU* CPU-Year, Core-Year：CPU单线程工作1年的计算量，CPU泛指有1GFLOPS的参考CPU!-- more --# 因数分解算法对于大数$n$，最小素因子是 $p$ 的情况下（$p\le\sqrt n$）找最某一个素因子：* 暴力分解：$O(p)$* Pollard Rho：$O(\sqrt p)$* ECM (Elliptic Curve Method)：$O\left(\exp (\sqrt{2\log p \log\log p})\right)$找全部素因子：* SQUFOF (SQUare FOrms Factorization)：$O\left(\exp(\frac{1}{3}\log n)\right)$* CFRAC (Continued FRACtions)：$O\left(\exp(\sqrt{2 \log n \log \log n})\right)$* QS (Quadratic Sieve), MPQS (Multiple Polynomial QS)：$O(\exp(\sqrt{\log n \log \log n}))$* SNFS (Special Number Field Sieve) 对特殊的数：$O\left(\exp(\sqrt[3]{\frac{32}{9}\log n (\log \log n)^2})\right)$* GNFS (General Number Field Sieve)：$O\left(\exp(\sqrt[3]{\frac{64}{9}\log n (\log \log n)^2})\right)$# 开源库[YAFU](https://sourceforge