ヤコビ記号

ヤコビ記号は、ルジャンドル記号の一般化である。ヤコビにより1837年に導入された^[1]。合同算術や数論の他の分野で理論的に興味深いものであるが、主な用途は計算数論、特に素数判定及び素因数分解である。これらは暗号理論においても重要である。

定義

任意の整数 a と任意の正の奇整数 n に対して、ヤコビ記号 (a/n) は n の素因数に対応するルジャンドル記号の積として定義される。

${\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{\alpha _{1}}\left({\frac {a}{p_{2}}}\right)^{\alpha _{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{\alpha _{k}},}$

ここで

${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}$

はnの素因数分解である。

ルジャンドル記号 (a/p) は全ての整数 a と全ての奇素数 p に対して次のように定義される。

${\displaystyle \left({\frac {a}{p}}\right)=\left\{{\begin{array}{rl}0&{\text{if }}a\equiv 0{\pmod {p}},\\1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x\colon \;a\equiv x^{2}{\pmod {p}},\\-1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and there is no such }}x.\end{array}}\right.}$

空積での通常の慣例に従い、(a/1) = 1とする。

下の引数が奇素数である場合、ヤコビ記号はルジャンドル記号と同じである。

表

n ≤ 59, k ≤ 30で n が奇数のときのヤコビ記号 (k/n) の値の表

性質

以下の事実は、ヤコビ記号の定義とルジャンドル記号の対応する性質からの直接的推論である^[2]。

ヤコビ記号は上の引数（「分子」）が整数で下の引数（「分母」）が正の奇整数である場合にのみ定義される。

1. n が（奇数の）素数の場合、ヤコビ記号 (a/n) は対応するルジャンドル記号と等しい（そして同じように書かれる）。

2. a ≡ b  (mod n)のとき、${\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)=\left({\frac {a\pm m\cdot n}{n}}\right)}$

3. ${\displaystyle \left({\frac {a}{n}}\right)={\begin{cases}0&{\text{if }}\gcd(a,n)\neq 1,\\\pm 1&{\text{if }}\gcd(a,n)=1.\end{cases}}}$

上または下の引数のいずれかが固定の場合、ヤコビ記号はもう一方の引数において完全乗法的関数になる。

4. ${\displaystyle \left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right),\quad {\text{so }}\left({\frac {a^{2}}{n}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.}$

5. ${\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right),\quad {\text{so }}\left({\frac {a}{n^{2}}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.}$

平方剰余の法則: m と n が奇数で互いに素な正整数である場合、

6. ${\displaystyle \left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{{\tfrac {m-1}{2}}\cdot {\tfrac {n-1}{2}}}={\begin{cases}1&{\text{if }}n\equiv 1{\pmod {4}}{\text{ or }}m\equiv 1{\pmod {4}},\\-1&{\text{if }}n\equiv m\equiv 3{\pmod {4}}\end{cases}}}$

であり、補足として

7. ${\displaystyle \left({\frac {-1}{n}}\right)=(-1)^{\tfrac {n-1}{2}}={\begin{cases}1&{\text{if }}n\equiv 1{\pmod {4}},\\-1&{\text{if }}n\equiv 3{\pmod {4}},\end{cases}}}$

8. ${\displaystyle \left({\frac {2}{n}}\right)=(-1)^{\tfrac {n^{2}-1}{8}}={\begin{cases}1&{\text{if }}n\equiv 1,7{\pmod {8}},\\-1&{\text{if }}n\equiv 3,5{\pmod {8}}.\end{cases}}}$

性質4と8を組み合わせると

9. ${\displaystyle \left({\frac {2a}{n}}\right)=\left({\frac {2}{n}}\right)\left({\frac {a}{n}}\right)={\begin{cases}\left({\frac {a}{n}}\right)&{\text{if }}n\equiv 1,7{\pmod {8}},\\-\left({\frac {a}{n}}\right)&{\text{if }}n\equiv 3,5{\pmod {8}}.\end{cases}}}$

となる。ルジャンドル記号と同様に、

• (a/n) = −1 の場合、a はnを法として平方非剰余である。

• a がnを法として平方剰余であり、gcd(a,n) = 1 の場合、(a/n) = 1である。

但し、ルジャンドル記号と異なり、

(a/n) = 1 である場合、a は n を法として平方剰余であるかもしれないし、ないかもしれない。

これは、a が n を法とする平方剰余であるためには、n の全ての素因数を法とする平方剰余でなければならないためである。ただし、例えば a が n の素因数のちょうど2つを法とする非剰余である場合、ヤコビ記号は1に等しくなる。

ヤコビ記号は、平方と非平方の観点から一律に解釈することはできないが、ゾロタレフの補題(en:Zolotarev's lemma)による順列の符号として一律に解釈することはできる。

ヤコビ記号(a/n)は、法nに対するディリクレ指標である。

ヤコビ記号の計算

上記の式は、2つの数のgcdを見つけるためにユークリッドの互除法に似た、ヤコビ記号を計算するための効率的なO(log a log b)^[3] につながる（これは規則2に照らすと驚くべきことはない）。

1. 規則2を使用して「分母」を法として「分子」を減らす。
2. 規則9を使用して、偶数の「分子」を抽出する。
3. 「分子」が1の場合、規則3と4の結果は1になる。「分子」と「分母」が互いに素でない場合、規則3の結果は0になる。
4. それ以外の場合、「分子」と「分母」は互いに素な奇数の正整数であるため、規則6を使用して記号を反転し、手順1に戻ることができる。

Luaでの実装

function jacobi(n, k)
  assert(k > 0 and k % 2 == 1)
  n = n % k
  t = 1
  while n ~= 0 do
    while n % 2 == 0 do
      n = n / 2
      r = k % 8
      if r == 3 or r == 5 then
        t = -t
      end
    end
    n, k = k, n
    if n % 4 == 3 and k % 4 == 3 then
      t = -t
    end
    n = n % k
  end
  if k == 1 then
    return t
  else
    return 0
  end
end

計算例

ルジャンドル記号(a/p)は奇素数 p に対してのみ定義され、ヤコビ記号と同じ規則に従う（つまり、(−1/p) と (2/p) の相互作用と補足式、および「分子」の乗法性）

問題: 素数9907が与えられたとする。(1001/9907)を計算せよ。

ルジャンドル記号を使用する

${\displaystyle {\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {7}{9907}}\right)\left({\frac {11}{9907}}\right)\left({\frac {13}{9907}}\right).\\\left({\frac {7}{9907}}\right)&=-\left({\frac {9907}{7}}\right)=-\left({\frac {2}{7}}\right)=-1.\\\left({\frac {11}{9907}}\right)&=-\left({\frac {9907}{11}}\right)=-\left({\frac {7}{11}}\right)=\left({\frac {11}{7}}\right)=\left({\frac {4}{7}}\right)=1.\\\left({\frac {13}{9907}}\right)&=\left({\frac {9907}{13}}\right)=\left({\frac {1}{13}}\right)=1.\\\left({\frac {1001}{9907}}\right)&=-1.\end{aligned}}}$

ヤコビ記号を使用する

${\displaystyle {\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {9907}{1001}}\right)=\left({\frac {898}{1001}}\right)=\left({\frac {2}{1001}}\right)\left({\frac {449}{1001}}\right)=\left({\frac {449}{1001}}\right)\\&=\left({\frac {1001}{449}}\right)=\left({\frac {103}{449}}\right)=\left({\frac {449}{103}}\right)=\left({\frac {37}{103}}\right)=\left({\frac {103}{37}}\right)\\&=\left({\frac {29}{37}}\right)=\left({\frac {37}{29}}\right)=\left({\frac {8}{29}}\right)=\left({\frac {2}{29}}\right)^{3}=-1.\end{aligned}}}$

2つの計算の違いは、ルジャンドル記号を使用する場合、記号を反転する前に「分子」を素数冪に因数分解する必要があることである。これにより、整数を因数分解するための既知の多項式時間アルゴリズムがないため、ルジャンドル記号を使用した計算はヤコビ記号を使用した計算よりも大幅に遅くなる^[4]。実際、これがヤコビがこの記号を導入した理由である。

素数性判定

ヤコビ記号とルジャンドル記号が異なる別の方法がある。オイラーの規準の式が合成数を法として使用される場合、結果はヤコビ記号の値である場合とそうでない場合があり、実際には−1または1でさえないこともある。

${\displaystyle {\begin{aligned}\left({\frac {19}{45}}\right)&=1&&{\text{ and }}&19^{\frac {45-1}{2}}&\equiv 1{\pmod {45}}.\\\left({\frac {8}{21}}\right)&=-1&&{\text{ but }}&8^{\frac {21-1}{2}}&\equiv 1{\pmod {21}}.\\\left({\frac {5}{21}}\right)&=1&&{\text{ but }}&5^{\frac {21-1}{2}}&\equiv 16{\pmod {21}}.\end{aligned}}}$

そのため、数nが素数であるか合成数であるかが不明である場合は、乱数aを選択し、ヤコビ記号(a/n)を計算し、オイラーの式と比較する。それらがnを法として異なる場合、nは合成数である。それらがaの多くの異なる値に対してnを法とする同じ剰余を持つ場合、nは「おそらく素数」（擬素数）である。

これは確率論的なソロベイ–シュトラッセン素数判定法と、Baillie-PSW primality testやミラー–ラビン素数判定法などの改良の基礎である。

間接的な使用として、リュカ–レーマー素数判定の実行中のエラー検出ルーチンとして使用することができる。これは現代のコンピュータハードウェアにおいても${\displaystyle {\begin{aligned}2^{82,589,933}-1\end{aligned}}}$ （既知の最大のメルセンヌ素数）を処理を完了するのに数週間かかる場合がある。In nominal cases, the Jacobi symbol:

${\displaystyle {\begin{aligned}\left({\frac {s_{i}-2}{M_{p}}}\right)&=-1&i\neq 0\end{aligned}}}$

これは最終的な剰余 ${\displaystyle {\begin{aligned}s_{p-2}\end{aligned}}}$ にも当てはまるため、妥当性の検証として使用できる。ただしハードウェアでエラーが生じた場合、結果が0または1になる可能性が50%あり、これは ${\displaystyle {\begin{aligned}s\end{aligned}}}$ の後続の項で変化しない（別のエラーが生じて-1に戻らない限り）。

関連項目

• クロネッカー記号（英語版） 全ての整数に対するヤコビ記号の一般化
• en:Power residue symbol より高次の剰余に対するヤコビ記号の一般化

出典

レファレンス

• Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. ISBN 3-540-55640-0 
• Ireland, Kenneth; Rosen, Michael (1990). A Classical Introduction to Modern Number Theory (Second edition). New York: Springer. ISBN 0-387-97329-X 
• Lemmermeyer, Franz (2000). Reciprocity Laws: from Euler to Eisenstein. Berlin: Springer. ISBN 3-540-66957-4 
• Shallit, Jeffrey (December 1990). “On the Worst Case of Three Algorithms for Computing the Jacobi Symbol”. Journal of Symbolic Computation 10 (6): 593-61. doi:10.1016/S0747-7171(08)80160-5. Computer science technical report PCS-TR89-140. https://digitalcommons.dartmouth.edu/cs_tr/42/. 
• Vallée, Brigitte; Lemée, Charly (October 1998). Average-case analyses of three algorithms for computing the Jacobi symbol (Technical report). CiteSeerX 10.1.1.32.3425。
• Eikenberry, Shawna Meyer; Sorenson, Jonathan P. (October 1998). “Efficient Algorithms for Computing the Jacobi Symbol”. Journal of Symbolic Computation 26 (4): 509-523. doi:10.1006/jsco.1998.0226. https://doi.org/10.1006/jsco.1998.0226. 

外部リンク

• Calculate Jacobi symbol shows the steps of the calculation.