利用pell方程的二次曲线进行因子分解

wsc810

在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  (mod  Q_nQ_{n+1})$

                                            $ y=p_nq_{n-1}+p_{n-1}q_n$

计算$GCD[P_{n+1}*2q_nq_{n-1}+(-1)^n+y,n] $  得到  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

这是要测试的代码，该如何优化

1. Clear["Global`*"]; n = 4181; d = n + P^2; P = 66;
   
2. Do[y = d 4 x^2 - P 4 x + 1; If[FractionalPart[Sqrt[y]] == 0, Break[]];
   
3. t = GCD[P 2 x - 1 + Sqrt[y], n],
   
4. {x, 5*10^12, 6*10^12}]
   
5. Print[{t, y}]
   

复制代码