平方剰余 http://nakano.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2011/11.pdf
について簡単に説明しておきます。
整数aと整数pを与えた時に
の式を満たす解xは存在する場合と、存在しない場合があります。
解が存在する時、a は p を法として平方剰余であるといいます。
解が存在しない時、a は p を法として平方非剰余であるといいます。
例えば、p=5の場合を考えると、
x=1のとき、
x=2のとき、
x=3のとき、
x=4のとき、
となるので、
a=1,4の時は解が存在し、a=2,3の時は解が存在しません。
楕円曲線暗号において、平方剰余計算が出てくるのはなぜでしょうか?
法素数 q における楕円曲線 の乗法群で、楕円曲線上の点{x, y}が決まっているとします。
ここでx,yは整数です。
点の2倍算で先にxの値を計算し、楕円曲線の右辺を計算すれば、あとは、
を満たすyを求めればいいということになります。
2倍算なので、このような解yが存在することは分かっています。
これはまさに平方剰余の解計算です。
はじめての数論 原著第3版 発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで
- 作者:Joseph H. Silverman
- 出版社/メーカー: 丸善出版
- 発売日: 2014/05/13
- メディア: 単行本(ソフトカバー)