素性检测与整数分解

福娃PNP

个人发现求解不定方程 $x^2-by=1$ 既可以判断一个整数是不是素数，也可以找出这个数(如果为合数)的因子。 详细的过程可到http://hi.baidu.com/%CB%EF%CD%F2 ... 85b5c77d1e712f.html查看！ 个人认为只要能找到求解不定方程的高效办法，将会对素数的问题有很大的帮助！ 对应用不定方程做素性检测和整数分解做个简单的介绍， 求解不定方程如果有解$x_1$(指非显然解)，则下一步计算$(x_1-1)//2$和b的公约数可以得到b的一个因子； 如果无解，判断此数是不是一个素数的某次方，如果是，此数为合数，不是，为素数！ 请您讨论能不能找到解不定方程 $x^2-by=1$ 的高效办法！

无心人

如果这个问题等价于整数分解 则就没有高效方法吧 ======================= 另外目前并没有对100位十进制整数比较快速的整数分解算法 往往要计算很长时间来分解一个所有因子在$10^50$附近的整数 而更大的数字，比如200位，目前的方法是无效的，必须借助很多计算机并行工作

shshsh_0510

这个不太清楚，不过感觉没啥“高效”的方法吧。根据如下：柯召写的数论述中介绍的求pell方程的基本解的方法就是将y从1开始带入，然后看是不是平方数。 另外素数检验是著名的非NP问题，所以如果你的算法是确定性的，那么肯定会很复杂；如果很简单，那么基本不对

medie2005

已经有讨论了: http://topic.csdn.net/u/20071128 ... 4-35533d8e630d.html

福娃PNP

刚看过!我觉得大家是在没有了解实际情况的前提下作的答复!并且还是比较想靠a^2=b^2modD做分解的,我想让大家在实际的问题中去考虑和探讨!

无心人

有两种结果 第一种，最后归结到分解b 第二种，比如连分数方式解这个方程，其效果还不如普通的顺序查找因子的时间复杂度呢 当然第二种很可能就是连分数方式分解的变形，据俺知道，目前连分数方式并不是必须的方法 最好的是数域筛，其次是二次筛，这两种用来对最终的大因子进行搜索 第三个是椭圆曲线方法，包括RHO，用来查找小因子，就是大约低于10^30的因子 第四种，是小素因子的试除 当然你也可以寻找第三种方法

medie2005

实际情况是什么？ 实际问题又是什么？

无心人

我想楼主对目前的大整数素性检测和分解的现状并不很了解 这个方向很艰深，甚至涉及到了代数域分园域的知识 如果单论你说的方程 我感觉并不会对这个问题有多大的帮助

福娃PNP

你能告诉我计算一个100位和计算一个1000位整数的连分数的时间吗?(使用普通计算机),怎么计算的?我想通过连分数的变形来解方程,不过感觉希望好象很渺茫,听说在八几年的时候,一个外国数学家已经对连分数的性质研究的很透彻了! 碰碰运气吧! 在你转载的百度阳槐空间里的《素数判定与大数分解问题》（下）看到3.连分数法里有这样一段话“　在连分数算法中，计算量主要是在分解诸(－1)m+1Qm+1上．计算机往往在不太可能在基集上分解的(－1)m+1Qm+1上耗费很多运算．波门伦斯对此问题作了研究后，他找出了一个方法，用此方法可以排除那些不太可能在基集上分解的(－1)m+1Qm+1．他的方法更进一步提高了连分数法的速度．”我个人理解：只是告诉我们“在基集上分解的(－1)m+1Qm+1上耗费很多运算”，应该是说耗费的时间多，没有告诉我们计算连分数需要多少时间。

无心人

1000位？那似乎不可能吧 目前的方法都做不到吧 连分数的时间复杂度我给你看下有介绍么？ 找到了 未经检验的结论 渐进时间复杂度是 $exp{c_1(ln n lnln n)^(1//2)} = n^{C(lnln n // ln n)^(1//2)}$ 对最佳选择的参数来说 $c_1 = 2 + \varepsilon_n, n \rarr \infty, \varepsilon_n \rarr 0$ C.P.Schnorr, Refined analysis and improvements on some factoring algorithms, J.Algorithms, 3(1982), 101-127