数学研发论坛

 找回密码
 欢迎注册
查看: 226|回复: 10

[讨论] 如何笔算将某些数分拆为两个平方数之和

[复制链接]
发表于 2019-3-7 20:07:56 | 显示全部楼层 |阅读模式

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

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

x
如何笔算求解二次不定方程\(\,2333=x^2+y^2\,\)的自然数解\(\left(x, y\right)\)
  1. Solve[233 == x^2 + y^2 && 0 < x && 0 < y, {x, y}, Integers]
  2. Solve[2333 == x^2 + y^2 && 0 < x && 0 < y, {x, y}, Integers]
  3. Solve[23333 == x^2 + y^2 && 0 < x && 0 < y, {x, y}, Integers]
  4. Solve[233333 == x^2 + y^2 && 0 < x && 0 < y, {x, y}, Integers]
复制代码

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-8 17:35:51 | 显示全部楼层
想太多
这样的算法未必有解,哪怕有解,难度也跟分解因式难度一样
然而RSA到现在还是难题

有定理但我忘了具体证明了,我用定理给你构造个算法好了:
定理:对任意非4k+3型素数p存在唯一a<=b使得p=a^2+b^2
对4k+1型质数p,注意到a跟-a同时是/不是p的二次剩余
于是我们可以找到同为p的二次剩余的两个数a以及-a,求出b,c使得b,c小于p/2且b^2=a,c^2=-a(mod p),不妨设b,c互素
记b^2+c^2=np,这里n<p/2,而n的每一个素因子必然可以表示成两个自然数的平方和(否则这个素因子整除b^2+c^2,对4k+3型素数,这是不可能的。)
用b+ci除以每一个n与b+ci的最大公约数,得到的数字的模长平方即为p
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-8 20:25:54 来自手机 | 显示全部楼层
楼上的分析很好,余下就是两个高斯整数的最大公约数问题了。需要注意交换高斯整数实部和虚部或改变任何部分符号不改变最大公约数的运算,所以总可以假设两者的实部虚部都是正数。如果其中一个实部虚部都是奇数,可以乘以(i+1)/2得到一个更小的。如果两者都是有奇偶,把偶数都调到实部再相减除以2

点评

“每一个n与b+ci的最大公约数”这个说法其实可以取巧的,如果n是素数,n=(a+bi)(a-bi),然后可以直接拿这两个因子试除——如果n不是素数,把n分解成素数然后挨个试除就好,这里的n比p/2小,所以算法可以很快停止  发表于 2019-3-9 23:40
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-9 23:14:08 | 显示全部楼层
本帖最后由 葡萄糖 于 2019-3-10 10:51 编辑

例4.  试解同余方程
\[x^2\equiv-1\pmod{2333}\]
解:此方程为模素数\(\,p=2333\,\)余\(\,\left(-1\right)\,\)的二次同余方程\(\,x^2\equiv a\pmod{p}\,\)
      因为\(\,2333\,\)是一个\(\,4n+1\,\)型的素数,我们有
\begin{align*}
&&\left(\frac{a}{p}\right)_{\rm L}
=\left(\frac{-1}{4n+1}\right)_{\rm L}&=\left(-1\right)^{\frac{p-1}{2}}=\left(-1\right)^{\frac{4n+1-1}{2}}=1\\
\end{align*}
      故原同余方程一定有解;
      因为\(p=\,2333=4\cdot2^\lambda\cdot\!s+1=4\cdot2^0\cdot11\cdot53+1=4\cdot583+1\,\),
      所以\(\,n=583\,\),\(\,\lambda=0\,\),\(\,s=583\,\),\(\,\dfrac{s+1}{2}=292\,\),\(a^s=a^{583}=\left(-1\right)^{583}=-1\),
      又因为\(\,2333=2^2\cdot11\cdot53+1\),则
\begin{align*}
\left(\frac{b}{p}\right)_{\rm L}=\left(\frac{2}{2333}\right)_{\rm L}
&=\left(-1\right)^{\frac{\left(2-1\right)\left(2333-1\right)}{4}}\left(\frac{2333}{2}\right)_{\rm L}=-\left(\frac{1}{2}\right)_{\rm L}=-1\\
&=\left(-1\right)^{\frac{2333^2-1}{8}}=-1
\end{align*}
      故\(\,b=2\,\)是\(\,257\,\)的平方非剩余;
      那么\(\,x^2\equiv -1\pmod{2333}\,\)的解为
\begin{align*}
x
&\equiv\pm a^{\frac{s+1}{2}}b^n&\pmod{2333}\\
&\equiv\pm \left(-1\right)^{292}2^{583}&\pmod{2333}\\
&\equiv\pm2^{583}&\pmod{2333}\\
&\equiv\quad{\color{\orange}{\cdots}}&\pmod{2333}\\
&\equiv\quad{\color{\orange}{\cdots}}&\pmod{2333}\\
&\equiv\quad{\color{\orange}{\cdots}}&\pmod{2333}\\
&\equiv\pm108&\pmod{2333}
\end{align*}
\[ \color{\orange}{2^{583}\equiv{\color{blue}{-108}}\pmod{2333}} \]
于是得到\(\,\color{purple}{108^2+1^2=5\cdot2333}\,\)
\begin{align*}
108^2+1^2&=5\cdot2333\\
&\Downarrow\\
21^2+65^2&=2\cdot2333\\
&\Downarrow\\
22^2+43^2&=1\cdot2333\\
\end{align*}

参考:
1.《数论经典著作系列:初等数论(3)》陈景润
2.《数论概论(原书第3版)》(美)西尔弗曼(Silverman,J.H.)
下面两张图片均来自《数论概论(原书第3版)》
逐次平方法.png 降阶程序.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-11 11:19:42 | 显示全部楼层
葡萄糖 发表于 2019-3-9 23:14
例4.  试解同余方程
\[x^2\equiv-1\pmod{2333}\]
解:此方程为模素数\(\,p=2333\,\)余\(\,\left(-1\right ...

  1. Clear["Global`*"];
  2. (*子函数,由上一轮的a b p迭代到下一轮的a b,并且作为返回结果*)
  3. fun[inp_,p_]:=Module[{a,b,m,x,y,ax,by,out},
  4.     a=inp[[1]];
  5.     b=inp[[2]];
  6.     m=(a^2+b^2)/p;
  7.     x=Mod[a,m];If[x>m/2,x=x-m];
  8.     y=Mod[b,m];If[y>m/2,y=y-m];
  9.     (*此处ax=a*x+b*y,而按照复数乘法是a*x-b*y,但是按照复数行不通*)
  10.     ax=Abs[(a*x+b*y)]/m;
  11.     by=Abs[(b*x-a*y)]/m;
  12.     out={ax,by};
  13.     Print[{ax,by,(ax^2+by^2)/p}];
  14.     Return[out]
  15. ]

  16. p=10^20+129;(*4k+1素数*)
  17. (*找到x^2=-1(mod p),随机选择一个a,使得a是非剩余,然后计算得到b*)
  18. Do[If[JacobiSymbol[k,p]==-1,a=k;Break[]],{k,2,10^10}];
  19. Print[a];
  20. b=PowerMod[a,(p-1)/4,p];
  21. If[b>p/2,b=p-b];
  22. (1^2+b^2)/p
  23. inp={1,b}
  24. Print["迭代开始"];
  25. While[inp!={0,0},inp=fun[inp,p]]
复制代码


我这写了一个程序,如何把一个4k+1的素数表达成两个整数的平方和,你可以拿去自己改写改写,
程序运行是如何把10^20+129表达成两个整数的平方!
\[10^{20}+129=4418521500^2+8970878873^2\]

迭代开始

{11524180067925436155,2,1328067262379699101}

{3717620611328925266,18,138207030097776520}

{375756505880982053,486,1411929517118845}

{48769435658774031,129276,23784578544753}

{22656899513236579,265015800,5133350955529}

{7554451426259577,1169779741200,570697377201}

{1724131042496980,375471581745246,31136067604}

{155848506308095,67126090170184,287946689}

{35543172939846,11620742548056,13983588}

{5846179219571,11373631281726,1635373}

{1027110339168,3986419991819,169465}

{1069002905108,2265487318188,62752}

{349328932555,82881221516,1289}

{129876989849,30528142881,178}

{40569708738,53423765619,45}

{22226443373,22494115119,10}

{4418521500,8970878873,1}

{0,0,0}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-11 11:25:20 | 显示全部楼层
\[10^{200}+357=4869498124813486982231377956355473573990401367667605534476012902371537410710789858816644285044662191^2+8734299514697096415092324422262172643487651173596610058044551075223059534652741558693062858574717874^2\]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-11 13:49:46 | 显示全部楼层
本帖最后由 葡萄糖 于 2019-3-11 16:11 编辑
mathematica 发表于 2019-3-11 11:19
我这写了一个程序,如何把一个4k+1的素数表达成两个整数的平方和,你可以拿去自己改写改写,
程序运 ...


多谢!
虽然我知道Wolfram Mathematica有PowersRepresentations(幂表示)这个函数,但是我依旧想自己用MMa写一个关于将某些数分拆为两个平方数之和的小程序。(以后有空试一试)
  1. Select[Table[10^100 + i, {i, 1000}], PrimeQ]
  2. Select[Select[Table[10^100 + i, {i, 1000}], PrimeQ], Mod[#, 4] == 1 &]
复制代码

大于\(\,10^{100}\,\)的最小素数为\(\,10^{100}+267\,\);
大于\(\,10^{100}\,\)的最小(4n+1)型素数为\(\,10^{100}+949\,\);
  1. PowersRepresentations[10^100 + 949, 2, 2]
复制代码

利用MMa自带的PowersRepresentations函数将\(\,10^{100}+949\,\)分拆为两个平方数,可以立刻得到解
7766881905507050845172598218029833369440123277895
99697921470138519447541656418848509184628524016382

点评

程序我已经写出来了,你可以自己稍微改写改写就可以了  发表于 2019-3-11 14:02
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-11 13:53:20 | 显示全部楼层
葡萄糖 发表于 2019-3-11 13:49
多谢!
虽然我知道Wolfram Mathematica有PowersRepresentations(幂表示)这个函数,但是我依旧想自己用 ...

你好聪明,我都没想到这个函数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 3 天前 | 显示全部楼层
葡萄糖 发表于 2019-3-11 13:49
多谢!
虽然我知道Wolfram Mathematica有PowersRepresentations(幂表示)这个函数,但是我依旧想自己 ...
  1. FactorInteger[10^200 + 357, GaussianIntegers -> True]
复制代码

利用这个函数,分解质因数,分解成高斯整数,也能表达成两个整数的平方和
{{-I, 1}, \
{486949812481348698223137795635547357399040136766760553447601290237153\
7410710789858816644285044662191 +
   8734299514697096415092324422262172643487651173596610058044551075223\
059534652741558693062858574717874 I,
  1}, {873429951469709641509232442226217264348765117359661005804455107\
5223059534652741558693062858574717874 +
   4869498124813486982231377956355473573990401367667605534476012902371\
537410710789858816644285044662191 I, 1}}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-3-25 20:13 , Processed in 0.068278 second(s), 24 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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