奇素数 p と p で割れない a に対して、

    x2≡a (mod p)

なる x は存在するときと、存在しないときがある。

たとえば、p = 7 のとき

    12≡1、 22≡4、32≡2、42≡2、 52≡4、62≡1

であるから、a≡1 または 2 または 4 のときのみ解がある。解があるとき、
a を mod p での平方剰余という。a がある数を平方して p で割った余りと
なるからである。解がないときは、平方非剰余という。このとき、

    (a/p)= 1   解があり
    (a/p)=-1   解がなし

と定義される。また、この (a/p) を平方剰余記号という。

<関数名>
  jacobi ---- 平方剰余記号 (a/p) の値を計算する

<形式>
  int jacobi(long a, long p);

<引数>
  a、p それぞれ平方剰余記号の分子、および分母

<関数値>
  平方剰余記号の値 +1 または -1。引数により計算不能の場合は 0。

<注意事項>
  平方剰余記号の分母 p は奇素数でなければならない。また、分子 a は p で割れないものでなければならない。特に奇素数の判定については手間がかかるので、本関数内では奇素数かどうかの判定はしていない。

用例

<関数本体>
  jacobi.c

<説明>
  平方剰余記号の値を計算するのに、以下の性質が利用される。

      (1/p) = 1
      (ab/p) = (a/p)(b/p)

      (2/p) = 1、p≡1 または 7 (mod 8) 時
      (2/p) = -1、p≡3 または 5 (mod 8) 時

      奇数 a と互いに素な p に対して、ガウス定理より
      (a/p) = (p/a)、p≡1 または a≡1 (mod 4) 時
      (a/p) = -(p/a)、p≡3 かつ a≡3 (mod 4) 時

  上の性質から、a の値が奇数か偶数かで異なる処理をする。偶数の場合は、 (2/p)の値をかけておき、a 自身の値を半分にする。奇数の場合は、分母と分子を入れ替え、ユークリッド互除法を適用する。この繰り返しを a が 1 になるまで行う。
  本アルゴリズムでは平方剰余記号の値を log(p) に比例時間で計算される。

Comments are closed.

Post Navigation