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

wsc810

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

无心人

目前来看这个算法没多大意义

mathematica

建议你先搞明白椭圆曲线算法因子分解，然后再搞因子分解，
这玩意真的很难很难很难！

.·.·.

很久很久以前我试过构造一个用尽可能少的运算构造出尽可能多的零点的多项式函数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，这里，减小余数有助于构造碰撞）
……

……

……

后来我就学乖了
在论坛里老老实实做水题不好吗？

mathematica

.·.·. 发表于 2019-11-5 23:44
很久很久以前我试过构造一个用尽可能少的运算构造出尽可能多的零点的多项式函数f(x)借助f(x)进行因式分解
...

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

.·.·.

mathematica 发表于 2019-11-6 08:32
把椭圆曲线算法理解了，都不迟，哪怕只是理解其中的思想，
我当时理解了，这真的是个绝妙的ideal
因子 ...

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

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

或者说，我应该专门研究一下椭圆曲线看看这东西有什么很好的性质吗？

mathe

https://en.wikipedia.org/wiki/Le ... curve_factorization

无心人

其实所有有效的方法都是构造
\( x^2 \equiv y^2 \mod n \)

wsc810

mathe 发表于 2019-11-6 10:42
https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization

英文维基百科上不了

wsc810

无心人 发表于 2019-11-6 19:46
其实所有有效的方法都是构造
\( x^2 \equiv y^2 \mod n \)

这点不理解，二次筛右边凑的时候，左边完全分解的数，在右边是怎么从0,1矩阵中找到符合条件的n行，使得所有每列的指数e_i的和 mod 2=0