Dasgupta 的算法（教科书）。概率。 1.36 平方根
Algorithms (textbook) by Dasgupta. Prob. 1.36 Square Roots
首先我想说这不是作业问题。我知道 Whosebug 谴责那些要求家庭作业解决方案的人。我只是出于兴趣做这个问题。
这是我正在研究的问题：
Need help with part (b), not (a)
我相信我明白了（一）；我有自己的答案，但我设法将我的解决方案与 Chegg 预览解决方案进行了比较（它没有显示部分 (b)）。到目前为止，我对 (b) 部分的理解如下：
当他们说
x is a square root of a modulo p if a = x^2(mod p)
他们的意思是：
x = sqrt(a mod p) IF a = x^2(mod p).
现在，它说的是，
如果a有平方根模p，那么a^((p+1)/4)就是这样的平方根
让我很困惑。我不太确定这行是什么意思！
if a has a square root modulo p, then a^((p+1)/4) is such a square root
=
如果存在 K 使得 K^2 mod p = a,
然后
a^((p+1)/4) mod p = K
首先我想说这不是作业问题。我知道 Whosebug 谴责那些要求家庭作业解决方案的人。我只是出于兴趣做这个问题。
这是我正在研究的问题：
Need help with part (b), not (a)
我相信我明白了（一）；我有自己的答案，但我设法将我的解决方案与 Chegg 预览解决方案进行了比较（它没有显示部分 (b)）。到目前为止，我对 (b) 部分的理解如下：
当他们说
x is a square root of a modulo p if a = x^2(mod p)
他们的意思是：
x = sqrt(a mod p) IF a = x^2(mod p).
现在，它说的是，
如果a有平方根模p，那么a^((p+1)/4)就是这样的平方根
让我很困惑。我不太确定这行是什么意思！
if a has a square root modulo p, then a^((p+1)/4) is such a square root
=
如果存在 K 使得 K^2 mod p = a,
然后
a^((p+1)/4) mod p = K