数学研发论坛

 找回密码
 欢迎注册
查看: 247|回复: 22

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

[复制链接]
发表于 2019-11-5 07:45:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
$a_2$怎么计算,假设$a_1=2,N=91$,谁能讲解下这个算法


无标题.jpg
360截图16630501277940.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-5 10:06:11 | 显示全部楼层
目前来看这个算法没多大意义

点评

……看出来了……能求出因子当且仅当某个$a_i$是因子,否则算法可以在一次Euclid算法之后求出每一个$a_i$的逆  发表于 2019-11-5 23:30
?为啥我只看见了这个算法有BUG呢?  发表于 2019-11-5 23:27
这是montgomery reduce算法中一种用途,同时求多个数在数域中的逆,其中N是2的幂。他这里割裂出来是看上去毫无意义  发表于 2019-11-5 13:18
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-5 11:27:00 | 显示全部楼层
建议你先搞明白椭圆曲线算法因子分解,然后再搞因子分解,
这玩意真的很难很难很难!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-5 23:44:55 | 显示全部楼层
很久很久以前我试过构造一个用尽可能少的运算构造出尽可能多的零点的多项式函数f(x)借助f(x)进行因式分解
好像成果是加法乘法共计6-7次,即可构造16个零点($f(x-a)=((x^2 - 130)^2 - 10116)^2-33177600$)
如果能用几万次运算构造出有多于2^2048个零点的非零多项式,破解RSA-4096大约是分分钟的事情。
然而问题是,现在只能快速算出2^4个零点,离2^2048遥遥无期

后来……我试图用更神奇的方法构造一组更神奇的解
https://bbs.emath.ac.cn/thread-15416-1-1.html
想法是,通过“压缩”余数的方法,构造出一系列更“小”的数字,为之后的筛法提供便利(如果我们能找到x^2=y^2(mod N)而x不等于正负y(mod N)的时候,有1<gcd(N,x+y)<N,这里,减小余数有助于构造碰撞)
……

……

……

后来我就学乖了
在论坛里老老实实做水题不好吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-6 08:32:26 | 显示全部楼层
.·.·. 发表于 2019-11-5 23:44
很久很久以前我试过构造一个用尽可能少的运算构造出尽可能多的零点的多项式函数f(x)借助f(x)进行因式分解
...

把椭圆曲线算法理解了,都不迟,哪怕只是理解其中的思想,
我当时理解了,这真的是个绝妙的ideal
因子分解算法很难的

点评

椭圆曲线只能得到n的小因子,低于95位的数字,用二次筛,高于95位的用数域筛,几百位的除了特殊形式的,用做梦筛  发表于 2019-11-6 19:43
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-6 09:54:05 | 显示全部楼层
mathematica 发表于 2019-11-6 08:32
把椭圆曲线算法理解了,都不迟,哪怕只是理解其中的思想,
我当时理解了,这真的是个绝妙的ideal
因子 ...

话说椭圆曲线难道不是pollard p-1算法变的吗?
不同的只是pollard p-1算法借助的是p-1的因子分解(或者,fermat小定理)
而椭圆曲线则是借助了另一种素数在椭圆曲线上的阶可能很小

并没感觉出椭圆曲线的奇妙
是我看得太粗略吗?

或者说,我应该专门研究一下椭圆曲线看看这东西有什么很好的性质吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-6 10:42:43 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-6 19:46:24 | 显示全部楼层
其实所有有效的方法都是构造
\( x^2 \equiv y^2 \mod n \)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-11-6 21:40:06 | 显示全部楼层
mathe 发表于 2019-11-6 10:42
https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization

英文维基百科上不了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-11-6 22:16:07 | 显示全部楼层
本帖最后由 wsc810 于 2019-11-6 22:17 编辑
无心人 发表于 2019-11-6 19:46
其实所有有效的方法都是构造
\( x^2 \equiv y^2 \mod n \)


这点不理解,二次筛右边凑的时候,左边完全分解的数,在右边是怎么从0,1矩阵中找到符合条件的n行,使得所有每列的指数e_i的和 mod 2=0
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-11-20 17:58 , Processed in 0.167424 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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