一个564位大整数分解

mathematica

.·.·. 发表于 2020-10-28 12:59
并不是
NFS分解只需要拿小素数做一组基
我简单地用MPQS来解释一下好了（虽然可能不对但原理类似）

晕，我说的这小素数，你这个还不是依赖小素数吗？

.·.·.

mathematica 发表于 2020-10-28 13:38
晕，我说的这小素数，你这个还不是依赖小素数吗？

行吧
从1数到10
有本事别数小素数

离了小素数你连数数都数不全
你还想干什么？
椭圆曲线对小素数的“依赖”和NFS对小素数的“依赖”，完全不是一个概念

mathematica

.·.·. 发表于 2020-10-28 14:48
行吧
从1数到10
有本事别数小素数

NFS难道是上来就分解成几个大素数的乘积？？？

wsc810

mathematica 发表于 2020-10-25 08:17
n=1734624471791475554302589708643097783774218447236640846493470190613635791928791088575910383304 ...

你用的什么软件

mathematica

wsc810 发表于 2020-10-28 20:59
你用的什么软件

有时间去考证书，比如注册会计师等，
不要研究素数判定、整数分解，虽然我觉得这两个问题真的非常有趣！
但是真的是太难太难了！白白浪费你的时间！

mathematica

wsc810 发表于 2020-10-28 20:59
你用的什么软件

根据我在论坛上的观察，你就喜欢搞素数、整数分解，
你放弃吧，好好干活、赚钱、养家、娶老婆、考证书，现实一点

mathematica

.·.·. 发表于 2020-10-28 12:59
并不是
NFS分解只需要拿小素数做一组基
我简单地用MPQS来解释一下好了（虽然可能不对但原理类似）

比如你得到a^2=p1p2,b^2=p2p3,c^2=p1p3，那么(abc)^2=(p1p2p3)^2
你这儿的p1 p2 p3也只可能是小素数呀，你以为你可以恰好找到很大的素数配成完全平方？
那是不可能的！

.·.·.

mathematica 发表于 2020-10-29 08:58
比如你得到a^2=p1p2,b^2=p2p3,c^2=p1p3，那么(abc)^2=(p1p2p3)^2
你这儿的p1 p2 p3也只可能是小素数呀， ...

NFS的第一步是找到一系列的r，使得每个r都可以拆成这些基的乘积
r1^2=p2p3p5p7...p999983
r2^2=p1p3p5...p999999
r3^2=p1p4p9...p998001
r4^2=...
...
然后用简单的线性变换找到一个组合，比如(r1r11r111...)^2可能是某个数字的平方
第一步的确需要用那一组小素数基进行分解
但问题是，得到一组合格数字的概率跟这些小素数，跟我们待分解的数字，都没有太大关系（跟多项式的关系更大）

NFS算法并不需要假设待分解的数字具有任何性质。
（与之对比的，ECM如果在某些sigma下，待分解的某个数字的素因子都不是smooth的，那么ECM永远得不到结果）

mathematica

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

我就问你，如果n越大，通常这些小素数基的上限是不是越大？
如果越大，那么就是有关系的！

.·.·.

mathematica 发表于 2020-10-29 13:34
我就问你，如果n越大，通常这些小素数基的上限是不是越大？
如果越大，那么就是有关系的！

可以固定基的大小
用更大的计算量代替更大的基