论坛 › 趣题妙解 › 如何笔算将某些数分拆为两个平方数之和

葡萄糖 发表于 2019-3-7 20:07:56

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

如何笔算求解二次不定方程\(\,2333=x^2+y^2\,\)的自然数解\(\left(x, y\right)\)
Solve
Solve
Solve
Solve

.·.·. 发表于 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

mathe 发表于 2019-3-8 20:25:54

楼上的分析很好，余下就是两个高斯整数的最大公约数问题了。需要注意交换高斯整数实部和虚部或改变任何部分符号不改变最大公约数的运算，所以总可以假设两者的实部虚部都是正数。如果其中一个实部虚部都是奇数，可以乘以(i+1)/2得到一个更小的。如果两者都是有奇偶，把偶数都调到实部再相减除以2

葡萄糖 发表于 2019-3-9 23:14:08

本帖最后由 葡萄糖 于 2019-3-10 10:51 编辑

例4.试解同余方程
\
解：此方程为模素数\(\,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版)》

mathematica 发表于 2019-3-11 11:19:42

葡萄糖 发表于 2019-3-9 23:14
例4.试解同余方程
\
解：此方程为模素数\(\,p=2333\,\)余\(\,\left(-1\right ...

Clear["Global`*"];
(*子函数,由上一轮的a b p迭代到下一轮的a b,并且作为返回结果*)
fun:=Module[{a,b,m,x,y,ax,by,out},
    a=inp[];
    b=inp[];
    m=(a^2+b^2)/p;
    x=Mod;If;
    y=Mod;If;
    (*此处ax=a*x+b*y,而按照复数乘法是a*x-b*y,但是按照复数行不通*)
    ax=Abs[(a*x+b*y)]/m;
    by=Abs[(b*x-a*y)]/m;
    out={ax,by};
    Print[{ax,by,(ax^2+by^2)/p}];
    Return
]

p=10^20+129;(*4k+1素数*)
(*找到x^2=-1(mod p),随机选择一个a,使得a是非剩余,然后计算得到b*)
Do==-1,a=k;Break[]],{k,2,10^10}];
Print;
b=PowerMod;
If;
(1^2+b^2)/p
inp={1,b}
Print["迭代开始"];
While]


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

迭代开始

{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}

mathematica 发表于 2019-3-11 11:25:20

\

葡萄糖 发表于 2019-3-11 13:49:46

本帖最后由 葡萄糖 于 2019-3-11 16:11 编辑

mathematica 发表于 2019-3-11 11:19
我这写了一个程序,如何把一个4k+1的素数表达成两个整数的平方和,你可以拿去自己改写改写,
程序运 ...

多谢！
虽然我知道Wolfram Mathematica有PowersRepresentations（幂表示）这个函数，但是我依旧想自己用MMa写一个关于将某些数分拆为两个平方数之和的小程序。（以后有空试一试）
Select, PrimeQ]
Select, PrimeQ], Mod[#, 4] == 1 &]
大于\(\,10^{100}\,\)的最小素数为\(\,10^{100}+267\,\)；
大于\(\,10^{100}\,\)的最小(4n+1)型素数为\(\,10^{100}+949\,\)；
PowersRepresentations
利用MMa自带的PowersRepresentations函数将\(\,10^{100}+949\,\)分拆为两个平方数，可以立刻得到解
7766881905507050845172598218029833369440123277895
99697921470138519447541656418848509184628524016382

mathematica 发表于 2019-3-11 13:53:20

葡萄糖 发表于 2019-3-11 13:49
多谢！
虽然我知道Wolfram Mathematica有PowersRepresentations（幂表示）这个函数，但是我依旧想自己用 ...

你好聪明,我都没想到这个函数

mathematica 发表于 2019-3-22 14:10:48

葡萄糖 发表于 2019-3-11 13:49
多谢！
虽然我知道Wolfram Mathematica有PowersRepresentations（幂表示）这个函数，但是我依旧想自己 ...

FactorInteger
利用这个函数,分解质因数,分解成高斯整数,也能表达成两个整数的平方和
{{-I, 1}, \
{486949812481348698223137795635547357399040136766760553447601290237153\
7410710789858816644285044662191 +
   8734299514697096415092324422262172643487651173596610058044551075223\
059534652741558693062858574717874 I,
1}, {873429951469709641509232442226217264348765117359661005804455107\
5223059534652741558693062858574717874 +
   4869498124813486982231377956355473573990401367667605534476012902371\
537410710789858816644285044662191 I, 1}}

kte 发表于 2019-4-14 21:17:05

本帖最后由 kte 于 2019-4-14 21:24 编辑

$x^2=-1(mod p) $ , $GCD$可以给出$p$的一个分解


$GCD=43 + 22 I$

另外计算$x^2=-1(mod p) $ 有特殊算法，选取$ a$ 是 $p$ 的二次非剩余，$p=4k+1$,计算 $ x=a^k (mod p) $,这里 p 模 8 余5，可以选 a=2

查看完整版本: 如何笔算将某些数分拆为两个平方数之和