找回密码
 欢迎注册
查看: 8911|回复: 1

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

[复制链接]
发表于 2021-5-22 13:41:34 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
本帖最后由 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  (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}$使得二次函数的值为平方数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-5-22 14:43:53 | 显示全部楼层
本帖最后由 wsc810 于 2021-5-22 14:46 编辑

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

  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}]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-28 17:16 , Processed in 0.049783 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表