Subnostr

とんでもないです、説明の匙加減が詳し過ぎず省き過ぎずで読みやすくわかりやすかったです。素晴らしい記事をありがとうございました。

> これを、最終的に r_n=1 となるまで繰り返せばよい。

はたぶん =0 のことかなというのと、「平方剰余の計算」の2つ目の式で or p-x が導かれる過程だけちょっとわかんなかったです。

Please Login to reply.

これ送った直後に -x と p-x が mod p の下で同一だからだと理解しました…

前者の方もこの通り解決をみました。壁打ちのように使ってしまい恐縮です… nostr:note1lys85h9ux6tnjprz3237v7gg8x5t9mrju066xtukztyv20yg5xlq9f6jhe

あれ…なんでこんな書き方したかな…。見直します。見ていただいてありがとうございます。

拡張ユークリッド互除法：

確かにそうですね、剰余なので r=0 まで続けるが正しいですね。ご指摘ありがとうございます。商と混同してたみたいです。エラッタ作らずにウェブページ作ってたのでなにかしようかな…。

平方剰余の計算：

px (mod p) は xの値によらず、和の単位元（ゼロ）なため、前述の等式はpの整数倍でも成立します。なので px=0 としても良かったのですが、平方剰余の負の数には触れていませんでした。

また、 px-x = -x (mod p)とするよりも、px-x = p-x (mod p) としたほうが、署名計算で使うというコンテキストでは、便利だろうと思いそうしました。

pを素数に選んだ場合、xが奇数ならp-xは偶数で、xが偶数ならp-xは必ず偶数です。平方剰余で出てくる2数は、実数の平方根で言うところの正負の関係のように振る舞うんですよね。楕円曲線を扱うところではそこを意識する箇所があります。なので、あの表記にしたはず…です。

参考

平方剰余のお話、参考記事読ませていただいて腑に落ちました。ありがとうございます (ついでに「なんでシュノア署名か？」も垣間見えて興味深かったです)。これ賢い工夫ですね…すごい

「xが偶数ならp-xは必ず偶数」→「xが偶数ならp-xは必ず奇数」のタイポでした。