Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

mod pでの平方剰余を計算する(p mod 8 = 5) その2

ed25519 整数論

www.pebblewind.com

こちらの記事で、平方剰余を計算しましたが、ed25519 においては、aは u/v という形になっています。
u,vの計算量は少ないので、計算効率をあげるため、u,vを用いた掛け算になるように変形します。

(\frac {u} {v})^{\frac {p+3} {8} }
= (\frac {u} {v})^{\frac {p+3} {8} } {v}^{p-1} (フェルマーの小定理)
= {u}^{ \frac {p+3} {8}} {v}^{p-1 - \frac {p+3} {8}}
= {u}^{\frac {p+3} {8} } {v} ^ { \frac {7p - 11} {8}}
= {u}^{\frac {p+3} {8} } {v}^{\frac {7(p-5) + 24} {8}} (余分な項が8の倍数になるようにする)
= {u}^{\frac {p+3} {8}} {v}^{\frac {7(p-5)} {8}} {v}^{3}
= {u}^{\frac {p -5 + 8} {8}} {v}^{\frac {7(p-5)} {8}} {v}^{3} (余分な項が8の倍数になるようにする)
= u {v}^{3} {u}^{\frac {p-5} {8}} {v}^{\frac {7(p-5)} {8}}
= u {v}^{3} (u v^{7})^{\frac {p-5} {8}}

参考:
https://ed25519.cr.yp.to/ed25519-20110926.pdf