将单质数表为两数平方和的最快速算法

wsc810

最近论坛讨论的问题有点少，那我就出个问题吧，设p是质数，当p较大时，求 p=x^2+y^2的最快速算法，已知有sqrt(p)的连分式的PQa算法可以给出一个确定性的算法.不知还是否还有其它较好的算法。

northwolves

p=4n+1形式时才有解吧

mathematica

https://bbs.emath.ac.cn/forum.ph ... 125&fromuid=865
程序的代码我已经替你写好了

uk702

个人觉得这是个好方法，https://www.ams.org/journals/mco ... -1972-0314745-6.pdf。

uk702

以 p = 10^100 + 949 为例，使用 julia 验证上述结果(由于 10^100+949 是 8k+5 型素数，故选 c = 2)
a = big(10)^100 + 949; b = (a-1) >> 2; x0 = powermod(2, b, a); d = isqrt(a);
x1 = a % x0;
while x1 > d
  x2 = x0 % x1;
  x0, x1 = x1, x2
end
println((x1, x0 % x1))

得：(99697921470138519447541656418848509184628524016382, 7766881905507050845172598218029833369440123277895)
和 https://bbs.emath.ac.cn/forum.ph ... amp;page=1#pid78125 第 7 楼的结果一致。

mathematica

uk702 发表于 2021-2-25 20:38
以 p = 10^100 + 949 为例，使用 julia 验证上述结果(由于 10^100+949 是 8k+5 型素数，故选 c = 2)
a = b ...

那你知道pell方程x^2-A*y^2=B如何求解吗？

uk702

mathematica 发表于 2021-2-26 09:24
那你知道pell方程x^2-A*y^2=B如何求解吗？

又找到了一个很牛叉的数论软件（还带代码），可以解你的问题  \(x^2 - dy^2\) = n，见 frattini(d,n)。
但它有说了The algorithm works only for small d and n，由此看来，你的问题除了试算外，有没有通用算法可能还要打个问号。

请见：http://www.numbertheory.org/calc/krm_calc.html#[56]