素性检测与整数分解

福娃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