用欧几里得算法实现因子分解，这个算法怎么理解

无心人

wsc810 发表于 2019-11-6 22:16
这点不理解，二次筛右边凑的时候，左边完全分解的数，在右边是怎么从0,1矩阵中找到符合条件的n行，使得 ...

线性代数算法啊
所有找到的数都分解成B基的素数的幂乘积
然后组成个矩阵

B基是基于待分解n计算出来的的一个上界的所有素数的集合
所有算法的目的就是找mod n能完全分解成B基的素数的整数
有的算法允许有1个素因子可以不是B基的素数
数域筛的B基是基于某个代数数域构造的

wsc810

无心人 发表于 2019-11-7 11:47
线性代数算法啊
所有找到的数都分解成B基的素数的幂乘积
然后组成个矩阵

N=4033


        2   3   7   13  17  19
64    0   0   1   0    0    0
65    0   1   0   0    0    0
66    0   0   0   0    1    1
67    1   1   0   0    0    1
69    1   0   1   1    0    0
70    0   1   0   0    0    0
71    0   0   1   0    0    0

这个矩阵怎么计算

无心人

wsc810 发表于 2019-11-7 19:17
N=4033

我还没看过对应的算法，只知道超过B基长度矩阵必然线性相关，怎么算我不太清楚，有个优化算法

mathematica

.·.·. 发表于 2019-11-6 09:54
话说椭圆曲线难道不是pollard p-1算法变的吗？
不同的只是pollard p-1算法借助的是p-1的因子分解（或者 ...

pollard p-1算法借助的是p-1的因子分解,如果p-1的分解质因数后有较大的质因子，那么这个办法就失效了。
但是用椭圆曲线，由于模p的时候，群的阶在p+1-p^0.5与p+1+p^0.5之间变化（Hasse定理），
而不一定是p-1，所以当p-1分解质因数可能有较大的质因子，但是p-3分解质因数可能质因子都比较小，
所以一条椭圆曲线不行，就再换一条椭圆曲线，模p的阶在不断地变，所以就很可能成功，
但是p-1的办法没办法变，所以一旦行不通就失败了！
椭圆曲线用来获得较大的素因子，还是比较有效的，

人类是怎么知道费马数F118的因子的?
https://bbs.emath.ac.cn/forum.ph ... 111&fromuid=865
第14个费马数的因子是怎么来的？
https://bbs.emath.ac.cn/forum.ph ... 703&fromuid=865

无心人

mathematica 发表于 2019-11-8 09:10
pollard p-1算法借助的是p-1的因子分解,如果p-1的分解质因数后有较大的质因子，那么这个办法就失效了。
...

这些都是试除算出来的，有不少项目做这些工作的，集合世界上很多志愿者的电脑分布式计算，所以你以一台电脑的算力看这些结果是不可能得到的，但是上万电脑看，这些就是刷时间的问题
比如前一段我的电脑就做了一段时间的Prime95计算，其中做了好几个麦森数（2的1.9亿次方左右的）的分解的因子试除，暴力算2^70附近的因子，虽然是特殊形式的数字，但是也是很大的计算了

mathematica

无心人 发表于 2019-11-8 22:20
这些都是试除算出来的，有不少项目做这些工作的，集合世界上很多志愿者的电脑分布式计算，所以你以一台 ...

素数判定有很多办法，包括费马数的试除法，而且通常还只有试除法才能解决费马数的素性判定问题！