利用sqrt(d)的连分式展开关系式Q_n*Q_{n+1}+P_{n+1}^2可进行因子分解

wsc810

本人发现利用如题所述的方法，令Q_n*Q_{n+1}=m,为要分解的数，P_{n+1}为参数P计算m+P^2,令其为d,然后将sqrt(d)进行连分式展开,得到Q_n和P_{n+1},当P_{n+1}恰好为P的时候，这时，便得到m的一种分解。 利用上述方法，关键是寻求合适的P,使得迭代地过程中能够出现P值。一般情况下，所选的参数P都能够满足要求，究竟何种情况下迭代能够产生满足要求的P值，还没搞清楚。总之，P_{n+1}是一个小于等于Int（sqrt(d)）的数。 下面仅以较小的数247,取P=8,得d=311为例做以该种方法的演示。 311 a0=17 22a_1-17=5 a1=1 13a_2-5=8 a_2=1 19a_3-8=11 a_3=1 至此，已将247完全分解为13*19 。对数4181,不知参数P可选为多少，n（迭代次数）等于多少时可以将其分解，不知此种方法分解的效率如何，问题的关键是求得较小的迭代次数。

282842712474

令$Q_n*Q_{n+1}=m$,为要分解的数，$P_{n+1}$为参数P计算$d=m+P^2$,然后将$\sqrt(d)$进行连分式展开,得到$Q_n$和$P_{n+1}$,当$P_{n+1}$恰好为P的时候，这时，便得到m的一种分解。

无心人

那个连分式的周期是和d的分解相关的，应该是所有素因子周期的lcm吧 你这个思路不合适吧 有二次根式分解方法，而且效率是很高的，不过不是你的思路哦

wsc810

令P_{n+1}=P,Q_{n+1}=Q,Q_n=Q',将(sqrt(d)+P)/Q利用连分式展开，在倍周期中，可以推倒出以下几个公式 p_n=x_n+P*y_n q_{n-1}=x_n-P*y_n p_{n-1}=Q'*y_n q_n=Q*y_n 其中(x_n)^2-d*(y_n)^2=(-1)^n 但是，既就是得到连分式基本公式的四个值，好像也无助于QQ'的分解，因为p_{n-1}和q_n是结合在一块的，不知各位有什么好的办法。

wsc810

无心人，我用的方法不是将sqrt(d)用连分式关系完全展开，得到它的一个周期，而是只要P_{n+1}出现P值，便终止迭代。另外你说的二次根式分解方法是什么，愿闻其详。

mjs1wh

你的参数P是任选的，这肯定无助于解决问题，这跟选一个数做因子，直接用原数来除，看能否除尽不是一样吗

wsc810

该问题有最新进展，能将m分解的可选参数P的范围，(d2-d1)/2d1，上述区间可理解为P大于它的非平凡“根距”，而小于其平凡“根距”。