Subnostr

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

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

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

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

Please Login to reply.

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

確かにそうですね、剰余なので 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は必ず奇数」のタイポでした。