利用pell方程的二次曲线进行因子分解
本帖最后由 wsc810 于 2021-5-22 18:18 编辑在pell方程中我们有如下公式
$(p_nq_{n-1}+p_{n-1}q_n)^2=d*4*(q_nq_{n-1})^2+4*(-1)^nP_{n+1}q_nq_{n-1}+1$
推导过程 $(p_nq_{n-1}+p_{n-1}q_n)^2=(p_nq_{n-1} - p_{n-1}q_n)^2+4p_np_{n-1}q_nq_{n-1}=1+4p_np_{n-1}q_nq_{n-1}$
$ p_np_{n-1}-dq_nq_{n-1}=(-1)^nP_{n+1}$
$1+4(dq_nq_{n-1}+(-1)^nP_{n+1})q_nq_{n-1}=d*4*(q_nq_{n-1})^2+4*(-1)^nP_{n+1}q_nq_{n-1}+1$
我们熟悉的二次方程
$ax^2+2bx+c=y^2$
将这个方程变形
$(ax+b)^2=(b^2-ac)+ay^2$
同样题目中的方程可变形为
$(d2q_nq_{n-1}+(-1)^nP_{n+1})^2-d(p_nq_{n-1}+p_{n-1}q_n)^2=-Q_nQ_{n-1}$
假设我们要分解的数为$n=Q_nQ_{n+1}$,Q_n及Q_{n+1}是 n 的两个未知的因子
将上述方程对n取模 $(P_{n+1}^2*2q_nq_{n-1}+(-1)^nP_{n+1})^2=(P_{n+1})^2(p_nq_{n-1}+p_{n-1}q_n)^2 (mod Q_nQ_{n+1})$
方程两边消去$P_{n+1}$
$(P_{n+1}*2q_nq_{n-1}+(-1)^n)^2=(p_nq_{n-1}+p_{n-1}q_n)^2(modQ_nQ_{n+1})$
$ y=p_nq_{n-1}+p_{n-1}q_n$
计算$GCD $得到n 的一个因子
下面是实例验算$n=4181,P_{n+1}=66$; $ p_n=247789693;q_n=2681826;p_{n-1}=176773752;q_{n-1}=1913221$
GCD[ 66*2*2681826*1913221-1+247789693*1913221+176773752*2681826,4181]=113
现在的问题是如何快速找到$q_nq_{n-1}$使得二次函数的值为平方数 本帖最后由 wsc810 于 2021-5-22 14:46 编辑
这是要测试的代码，该如何优化
Clear["Global`*"]; n = 4181; d = n + P^2; P = 66;
Do] == 0, Break[]];
t = GCD, n],
{x, 5*10^12, 6*10^12}]
Print[{t, y}]
页:
[1]