数学研发论坛

 找回密码
 欢迎注册
12
返回列表 发新帖
楼主: wsc810

[求助] 用欧几里得算法实现因子分解,这个算法怎么理解

[复制链接]
发表于 2019-11-7 11:47:21 | 显示全部楼层
wsc810 发表于 2019-11-6 22:16
这点不理解,二次筛右边凑的时候,左边完全分解的数,在右边是怎么从0,1矩阵中找到符合条件的n行,使得 ...


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

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

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-11-7 19:17:25 | 显示全部楼层
本帖最后由 wsc810 于 2019-11-7 19:43 编辑
无心人 发表于 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

这个矩阵怎么计算

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-8 09:10:00 | 显示全部楼层

我还没看过对应的算法,只知道超过B基长度矩阵必然线性相关,怎么算我不太清楚,有个优化算法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-8 09:10:39 | 显示全部楼层
.·.·. 发表于 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


点评

主要是费马数是特殊形式的数字,可以不需要完全展开到内存就能试除,所以不需要惊讶那么大的数字怎么会得到因子  发表于 2019-11-8 22:34
受教!  发表于 2019-11-8 17:46
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-8 22:20:28 | 显示全部楼层
mathematica 发表于 2019-11-8 09:10
pollard p-1算法借助的是p-1的因子分解,如果p-1的分解质因数后有较大的质因子,那么这个办法就失效了。
...


这些都是试除算出来的,有不少项目做这些工作的,集合世界上很多志愿者的电脑分布式计算,所以你以一台电脑的算力看这些结果是不可能得到的,但是上万电脑看,这些就是刷时间的问题
比如前一段我的电脑就做了一段时间的Prime95计算,其中做了好几个麦森数(2的1.9亿次方左右的)的分解的因子试除,暴力算2^70附近的因子,虽然是特殊形式的数字,但是也是很大的计算了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-11 08:40:47 | 显示全部楼层
无心人 发表于 2019-11-8 22:20
这些都是试除算出来的,有不少项目做这些工作的,集合世界上很多志愿者的电脑分布式计算,所以你以一台 ...

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

点评

不,其实试除难度也很大,你可以看得到至少一个因子的费马数与全部费马数的比例,是不是很低  发表于 2019-11-11 15:20
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-12-8 15:22 , Processed in 0.192265 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表