[原创]对大合数分解的一种新的思考

wsc8100

[watermark]设待要分解的大合数为D,我们知道利用sqrt(D)的连分式展开式最终可得到如下同余式，p_n^2=(-1)^n*Q_(n+1)(mod D),如果我们再能得到一个关于Q的平方同余式，则同余式两边同时达到平方，若不是非平凡解，则可分解D,下面我们可以构造一个较为特殊的Pell方程，x^2-Q*y^2=D,然后求解此不定方程，得到x,y的解。于是有x^2=Q*y^2(mod D),最后将p代入，便可两边同时得到平方。现在问题的焦点是求解D大于Q的Pell方程方便吗，都用什么算法。希望知道的朋友讲解讲解，多谢了。[/watermark]

bardo

Pell方程对大合数分解而言,目前几乎是一个死胡同!
记得我国数学家柯召是这方面的专家,如果这好办,他早就解决了

moranhuishou

对于大合数的分解，我有一个思路：
设大合数为x,求出
2^?=1 (mod x)
（2亦为大于1的任意自然数）。
据“？”，即可分解x。
问题是找出求“？”的快速简便方法。

bardo

下面引用由moranhuishou在 2009/10/07 09:59am 发表的内容： 对于大合数的分解，我有一个思路：
设大合数为x,求出
2^?=1 (mod x)
（2亦为大于1的任意自然数）。
据“？”，即可分解x。
问题是找出求“？”的快速简便方法。

你这不是比佩尔方程更难吗? 根据我估计, RSA总部可能已经得出了分解的方法, 但是, 不便于公布. 所以, RSA挑战现在就关了.

wanwna

下面引用由Bardo在 2009/10/09 08:42pm 发表的内容：
你这不是比佩尔方程更难吗?
根据我估计, RSA总部可能已经得出了分解的方法, 但是, 不便于公布.
所以, RSA挑战现在就关了.

三个字：不可能

bardo

怎么不可能, 肯定存在一种算法. 只不过人们没有发现它.
因为, 人们至今未能证明, 分解只能用试除的办法, 其它, 做不到.

wanwna

至少现在没有找到。
另外，这种时间代价比较低的算法不是"肯定"存在,而是可能存在.

bardo

有很多方面表明, 这种算法可能存在.
比如: 奇合数可以表示为各种形式的数列. 最简单的当然是公差为2的奇数数合. 比如, 3,5,7 其和就是15. 那就是说, 存在一种整数的多项式约束. 但我们没有找到它.
实际上, 我们可以把可数表示为很多种数列, 结果, 都能使这个数列的和成为两个多项式的乘积.
最后, 奇合数分解, 实际是二元二次不定方程整数解的问题.

wanwna

下面引用由Bardo在 2009/10/10 08:45pm 发表的内容：
有很多方面表明, 这种算法可能存在.
比如: 奇合数可以表示为各种形式的数列. 最简单的当然是公差为2的奇数数合. 比如, 3,5,7 其和就是15. 那就是说, 存在一种整数的多项式约束. 但我们没有找到它.
实际上, 我们　...

有很多方面表明这种算法可能存在?请给出论文凭据.
尽管目前没有找到也没有证明其没有,但大多数人还是怀疑没有,我也怀疑没有.不过即便要研究大合数有没有相对快速的算法,看似是有很多可以下手的地方,可是一直没有任何真正的进展.
然而就如同P?=NP,大部分的人都相信P!=NP,除了少数几个极品.

wanwna

另外，不是说相对快的分解算法没有被找到，而是现在找到的即使再快的分解算法,都无法满足我们的要求.
另外,我再献上一些关于大数分解方面的介绍.