為什麼要計算u∗在3∗(u∗在7)(p-5)/8在∗在3∗(在∗在7)(p−5)/8uv^3(u*v^7)^{(p-5)/8}建議代替(u/v)(p+3)/8(在/在)(p+3)/8(u/v)^{(p+3)/8}

使用 Curve25519 我遇到了建議的計算平方根候選形式： $ uv^3(uv^7)^{\frac{p-5}{8}} $ 代替 $ \left(\frac{u}{v}\right)^{\frac{p+3}{8}} $ . 為什麼會這樣？或者為什麼它更便宜？

• 愛德華茲曲線數字簽名算法 (EdDSA) https://www.rfc-editor.org/rfc/rfc8032#section-5.1.3
• 高速高安全簽名https://eprint.iacr.org/2011/368.pdf

注意 $$ \frac{7(p-5)}8+3=\frac{7p-11}8\equiv \frac{7p-11}8-p-1\equiv -\frac{(p+3)}8\pmod{p-1}. $$

相似地 $$ \frac{p-5}8+1=\frac{p+3}8 $$

所以 $ v^3(v^7)^{\frac{p-5}8}\equiv v^{-\frac{(p+3)}8}\pmod p $ .

同樣地 $ u(u)^{\frac{p-5}8}\equiv u^{\frac{p+3}8} $ 按要求。

原因是為了節省一個模組化的部門，這是一個相當昂貴的操作。

引用自：https://crypto.stackexchange.com/questions/88868