将单质数表为两数平方和的最快速算法
最近论坛讨论的问题有点少，那我就出个问题吧，设p是质数，当p较大时，求p=x^2+y^2的最快速算法，已知有sqrt(p)的连分式的PQa算法可以给出一个确定性的算法.不知还是否还有其它较好的算法。 p=4n+1形式时才有解吧 https://bbs.emath.ac.cn/forum.php?mod=redirect&goto=findpost&ptid=15803&pid=78125&fromuid=865
程序的代码我已经替你写好了 本帖最后由 uk702 于 2021-2-25 15:46 编辑
个人觉得这是个好方法，https://www.ams.org/journals/mcom/1972-26-120/S0025-5718-1972-0314745-6/S0025-5718-1972-0314745-6.pdf。 以 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.php?mod=viewthread&tid=15803&page=1#pid78125 第 7 楼的结果一致。 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如何求解吗？ 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#
页:
[1]