为什么建议计算$u*v^3*(u*v^7)^{(p-5)/8}$而不是$(u/v)^{(p+3)/8}$

Question

在使用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

Answer 1

请注意，

\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}。

原因是为了节省一个模块化的部门，这是一个相当昂贵的操作。