一个564位大整数分解

mathematica

.·.·. 发表于 2020-10-29 16:01
可以固定基的大小
用更大的计算量代替更大的基

2224442340713
这个数，你用2 3 5 7为基分解给我看一下呗

mathematica

.·.·. 发表于 2020-10-29 16:01
可以固定基的大小
用更大的计算量代替更大的基

52万列的大矩阵，这还是129位的合数

资料来源
二次筛法的英文维基百科
https://en.wikipedia.org/wiki/Quadratic_sieve

mathematica

.·.·. 发表于 2020-10-29 13:25
NFS的第一步是找到一系列的r，使得每个r都可以拆成这些基的乘积
r1^2=p2p3p5p7...p999983
r2^2=p1p3p5. ...

个人认为，当n越大的时候，需要的小素数的个数越多，
因此我觉得目前来说，有效的素数分解算法，应该都是依赖于小素数。
包括属于筛法，二次筛法，椭圆曲线算法

mathematica

当然了，那个量子计算机的算法，可能不依赖小素数，但是到目前为止都还没实现，
数域筛法目前我还没看懂，但是我感觉是二次筛法的改进，思想应该差不多

.·.·.

mathematica 发表于 2020-10-30 08:35
2224442340713
这个数，你用2 3 5 7为基分解给我看一下呗

去掉2,3,5,7用ECM呢？
“基”之所以是“基”，意思很简单，它们是可替代的。
ECM算一个数，如果假设这个数的order不被2,3,5,7整除，会死得很惨。

如果真的2,3,5,7分解2224442340713，NFS会非常慢，这里可以直接用QFS
（虽然QFS也快不到哪里去）

my(c=(2*3*5*7)^500);parfor(i=1,10000000,my(x=(sqrtint(2224442340713*i)+1)^2%2224442340713);if(gcd(x,c)==x,print(i)))
（懒得写检测一个数字是2,3,5,7的乘积的算法了，直接gcd搞定）
得到
174953
699812
1574577
2164253
2331353
2455773
2799248
4373825
6298308
7529723
7864001
8572697
8657012
9325412
9823092
time = 29,776 ms.

把这些输出统一处理一下
z=[174953,699812,1574577,2164253,2331353,2455773,2799248,4373825,6298308,7529723,7864001,8572697,8657012,9325412,9823092]
apply(x->print(x),apply(x->factor((sqrtint(2224442340713*x)+1)^2%2224442340713),z))
输出
[2, 8; 3, 7; 5, 1]
[2, 10; 3, 7; 5, 1]
[2, 8; 3, 9; 5, 1]
...
比较走运的，x[10]直接符合题意(x[10]^2和x[10]^2%2224442340713都是完全平方数且后者恰好是2,3,5,7为基筛出来的东西)
gcd(x[10]+3*5^5*7,2224442340713)
可以直接得到答案

现在该你了
随便选ECM，一切初始值随意，分解2224442340713，要求是分解时候使用的order不是2,3,5,7的倍数

mathematica

.·.·. 发表于 2020-10-30 10:55
去掉2,3,5,7用ECM呢？
“基”之所以是“基”，意思很简单，它们是可替代的。
ECM算一个数，如果假设这 ...

你这个是二次筛法吧，还是？
不过你写的我没看懂

mathematica

.·.·. 发表于 2020-10-30 10:55
去掉2,3,5,7用ECM呢？
“基”之所以是“基”，意思很简单，它们是可替代的。
ECM算一个数，如果假设这 ...

估计太小的合数分解起来没意义，
你试试这个整数
9846451186268106372347126340355779799009

.·.·.

mathematica 发表于 2020-10-30 12:55
估计太小的合数分解起来没意义，
你试试这个整数
9846451186268106372347126340355779799009

可能会很慢
但是
你也可以试试，ecm下找一个sigma和一个order不能被2,3,5,7整除的数字

NFS算法对一切基一视同仁（顶多会有效率上的问题）
ecm的话
大概会很惨。

另外我用QFS的原因是我不会NFS
……毕竟我是个学统计的

mathematica

.·.·. 发表于 2020-10-31 13:00
可能会很慢
但是
你也可以试试，ecm下找一个sigma和一个order不能被2,3,5,7整除的数字

我也想知道nfs具体如何操作的

mathematica

.·.·. 发表于 2020-10-31 13:00
可能会很慢
但是
你也可以试试，ecm下找一个sigma和一个order不能被2,3,5,7整除的数字

我想知道数域筛法是怎么回事，似乎是代数数域，整系数多项式的根