Pebble Coding

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

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

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

プライバシーポリシー

お問い合わせ

スポンサーリンク