Pebble Coding

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

平方剰余とは

平方剰余 http://nakano.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2011/11.pdf

について簡単に説明しておきます。

整数aと整数pを与えた時に
 {x}^{2} = a \mod p
の式を満たす解xは存在する場合と、存在しない場合があります。
解が存在する時、a は p を法として平方剰余であるといいます。
解が存在しない時、a は p を法として平方非剰余であるといいます。

例えば、p=5の場合を考えると、
x=1のとき、 {x}^{2} = 1 \mod 5
x=2のとき、 {x}^{2} = 4 \mod 5
x=3のとき、 {x}^{2} = 9 \mod 5 = 4 \mod 5
x=4のとき、 {x}^{2} = 16 \mod 5 = 1 \mod 5
となるので、
a=1,4の時は解が存在し、a=2,3の時は解が存在しません。

楕円曲線暗号において、平方剰余計算が出てくるのはなぜでしょうか?
法素数 q における楕円曲線  {y}^{2} = {x}^{3} + 7 の乗法群で、楕円曲線上の点{x, y}が決まっているとします。
ここでx,yは整数です。
点の2倍算で先にxの値を計算し、楕円曲線の右辺を計算すれば、あとは、
 {y}^{2} = a \mod q を満たすyを求めればいいということになります。
2倍算なので、このような解yが存在することは分かっています。
これはまさに平方剰余の解計算です。

はじめての数論 原著第3版 発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

はじめての数論 原著第3版 発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

  • 作者:Joseph H. Silverman
  • 出版社/メーカー: 丸善出版
  • 発売日: 2014/05/13
  • メディア: 単行本(ソフトカバー)