ヤコビ記号

Generalization of the Legendre symbol in number theory

このシンボルを導入したカール・グスタフ・ヤコブ・ヤコビ。

け n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	1
3	0	1	−1
5	0	1	−1	−1	1
7	0	1	1	−1	1	−1	−1
9	0	1	1	0	1	1	0	1	1
11	0	1	−1	1	1	1	−1	−1	−1	1	−1
13	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1
15	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1
17	− 0	− 1	1	−1	− 1	−1	−1	−1	1	− 1	−1	−1	−1	1	−1	1	1

ヤコビ記号( ⁠け/n⁠ ) を、様々なk (上) とn (左)に対して示します。以下の規則 (2) により、他のk はnを法として約分できるため、 0 ≤ k < nのみが表示されています。平方剰余は黄色で強調表示されています。ヤコビ記号が −1 であるエントリは平方剰余ではないことに注意してください。また、k が互いに素なnを法とする平方剰余である場合、( ⁠け/n⁠ ) = 1ですが、ヤコビ記号が1であるすべての要素（ n = 9行とn = 15行を参照）が平方剰余となるわけではありません。また、 nまたはkのいずれかが平方数の場合、すべての値は非負であることにも注意してください

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

意味

任意の整数aと任意の正の奇数nに対して、ヤコビ記号( ⁠1つの/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の素因数分解です。

ルジャンドル記号（⁠1つの/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.}$

空積の通常の慣例に従うと、（⁠1つの/1⁠ ) = 1 です。

下側の引数が奇数の素数の場合、ヤコビ記号はルジャンドル記号と等しくなります。

値の表

以下はヤコビ記号の値の表である（⁠1つの/n⁠ ）で、n  ≤ 59、a  ≤ 30、n は奇数です。

1つの n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
1	− 1	1	1	− 1	1	1	1	1	− 1	1	1	1	1	1	1	− 1	1	1	1	1	1	1	1	1	− 1	1	1	1	1	1
3	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
5	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0
7	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1
9	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0
11	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1
13	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1
15	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0
17	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	1	0	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1
19	1	−1	−1	1	1	1	1	−1	1	−1	1	−1	−1	−1	−1	1	1	−1	0	1	−1	−1	1	1	1	1	−1	1	−1	1
21	1	−1	0	1	1	0	0	−1	0	−1	−1	0	−1	0	0	1	1	0	−1	1	0	1	−1	0	1	1	0	0	−1	0
23	1	1	1	1	−1	1	−1	1	1	−1	−1	1	1	−1	−1	1	−1	1	−1	−1	−1	−1	0	1	1	1	1	−1	1	−1
25	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0
27	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
29	1	−1	−1	1	1	1	1	−1	1	−1	−1	−1	1	−1	−1	1	−1	−1	−1	1	−1	1	1	1	1	−1	−1	1	0	1
31	1	1	−1	1	1	−1	1	1	1	1	−1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	1	−1	−1	1	−1	−1
33	1	1	0	1	−1	0	−1	1	0	−1	0	0	−1	−1	0	1	1	0	−1	−1	0	0	−1	0	1	−1	0	−1	1	0
35	1	−1	1	1	0	−1	0	−1	1	0	1	1	1	0	0	1	1	−1	−1	0	0	−1	−1	−1	0	−1	1	0	1	0
37	1	−1	1	1	−1	−1	1	−1	1	1	1	1	−1	−1	−1	1	−1	−1	−1	−1	1	−1	−1	−1	1	1	1	1	−1	1
39	1	1	0	1	1	0	−1	1	0	1	1	0	0	−1	0	1	−1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0
41	1	1	−1	1	1	−1	−1	1	1	1	−1	−1	−1	−1	−1	1	−1	1	−1	1	1	−1	1	−1	1	−1	−1	−1	−1	−1
43	1	−1	−1	1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	1	−1	−1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1
45	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0
47	1	1	1	1	−1	1	1	1	1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	1	−1	−1	1	1	−1	1	1	−1	−1
49	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1
51	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	1	0	1	0	0	1	1	0	−1	1	0	1	−1	0	−1	1	0
53	1	−1	−1	1	−1	1	1	−1	1	1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1	−1	1	1	−1	−1	1	1	−1
55	1	1	−1	1	0	−1	1	1	1	0	0	−1	1	1	0	1	1	1	−1	0	−1	0	−1	−1	0	1	−1	1	−1	0
57	1	1	0	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	−1	0	0	−1	0	−1	−1	0	1	−1	0	1	1	0
59	1	−1	1	1	1	−1	1	−1	1	−1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	−1	−1	1	1	1	1	1	−1

プロパティ

以下の事実、さらには相互法則は、ヤコビ記号の定義とルジャンドル記号の対応する性質から直接導き出されるものである。^[2]

ヤコビ記号は、上の引数 (「分子」) が整数で、下の引数 (「分母」) が正の奇数の場合にのみ定義されます。

1. nが（奇数の）素数である場合、ヤコビ記号（⁠1つの/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}}}$

そして ${\displaystyle \left({\frac {1}{n}}\right)=\left({\frac {n}{1}}\right)=1}$

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}}}$

ルジャンドル記号のように:

• もし（⁠1つの/n⁠ )  = −1 の場合、a はnを法とした二次非剰余です。

• a がn を法とする平方剰余でgcd ( a , n ) = 1ならば、 ( ⁠1つの/n⁠ )  = 1 です。

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

もし（⁠1つの/n⁠ )  = 1 の場合、a はnを法とした平方剰余である場合もそうでない場合もあります。

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

ヤコビ記号は、正方形と非正方形の観点からは一様に解釈できませんが、ゾロタレフの補題によって順列の記号として一様に解釈できます。

ヤコビ記号（⁠1つの/n⁠ )は、 nを法とするディリクレ指標です。

ヤコビ記号の計算

上記の式は、ヤコビ記号を計算するための効率的なO (log a log b ) ^[3] アルゴリズムにつながります。これは、2つの数値の最大公約数を求めるユークリッドの互除法に似ています。(これは規則2に照らして驚くべきことではありません。)

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

下記のコードに加えて、Riesel ^[4]はPascalでもこれを提供しています。

実装ルア

関数jacobi ( n , k ) assert ( k > 0かつ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かつk % 4 == 3 then t = - t end n = n % k end if k == 1 then return t else return 0 end end                                                                                              

実装C++

// a/n は (a,n) と表現されますint jacobi ( int a , int n ) { assert ( n > 0 && n % 2 == 1 ); // ステップ 1 if (( a %= n ) < 0 ) a += n ; // 処理 (a < 0) // ステップ 3 int t = 0 ; // ビット 1 と 2 の XOR により、戻り値の符号が決まりますwhile ( a ) { // ステップ 2 while ( a % 4 == 0 ) a /= 4 ; if ( a % 2 == 0 ) { t ^= n ; // "^= n & 6" の可能性もあります。ビット 1 と 2 のみを扱いますa /= 2 ; } // ステップ 4 t ^= a & n & 2 ; // 符号を反転 if a % 4 == n % 4 == 3 int r = n % a ; n = a ; a = r ; } if ( n != 1 ) 0を返す; else if (( t ^ ( t >> 1 )) & 2 ) -1を返す; else return 1 ; }                                                                                                   

素数判定

ヤコビ記号とルジャンドル記号には、もう一つ異なる点があります。オイラーの判定基準公式を合成数を法として用いた場合、結果はヤコビ記号の値と一致する場合もあれば、一致しない場合もあります。実際、-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を選び、ヤコビ記号( ⁠1つの/n⁠ ）をオイラーの公式と比較します。これらがn を法として異なる場合、nは合成数です。aのさまざまな値に対してn を法として同じ剰余を持つ場合、nは「おそらく素数」です。

これは、確率的Solovay–Strassen 素数性テストと、 Baillie–PSW 素数性テストやMiller–Rabin 素数性テストなどの改良の基礎となります。

間接的な用途としては、ルーカス・レーマー素数判定の実行中にエラー検出ルーチンとして用いることが可能です。この判定は、現代のコンピュータハードウェアでさえ、（2024年10月時点で知られている最大のメルセンヌ素数）を超えるメルセンヌ数を処理する場合、完了までに数週間かかることがあります。名目上のケースでは、ヤコビ記号は次のようになります。 ${\displaystyle {\begin{aligned}2^{136,279,841}-1\end{aligned}}}$

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

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

参照

• クロネッカー記号、ヤコビ記号をすべての整数に一般化したもの。
• べき乗剰余記号、ヤコビ記号を高次のべき乗剰余に一般化したもの。

注記

1. ジャコビ、CGJ (1837)。 「Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie」。ベリヒト・アクウィス。ベルリン: 127–136。
2. アイルランド＆ローゼン pp. 56–57 または レマーマイヤー p. 10
3. コーエン、29～31ページ
4. 285ページ

参考文献

• コーエン、アンリ（1993年）『計算代数的数論講座』ベルリン：シュプリンガー、ISBN 3-540-55640-0。
• アイルランド、ケネス、ローゼン、マイケル (1990). 『現代数論への古典的入門』（第2版）. ニューヨーク:シュプリンガー. ISBN 0-387-97329-X。
• レンマーマイヤー、フランツ (2000)。返報性の法則: オイラーからエイゼンシュタインまで。ベルリン：シュプリンガー。ISBN 3-540-66957-4。
• リーゼル、ハンス（1994）、素数と因数分解のためのコンピュータ手法（第2版）、ボストン：ビルクハウザー、ISBN 0-8176-3743-5
• ジェフリー・シャリット（1990年12月）. 「ヤコビ記号を計算する3つのアルゴリズムの最悪ケースについて」 .シンボリック計算ジャーナル. 10 (6): 593–61 . doi : 10.1016/S0747-7171(08)80160-5 . コンピュータサイエンス技術報告書 PCS-TR89-140.
• ヴァレー, ブリジット; ルメ, シャルリー (1998年10月). ヤコビ記号を計算する3つのアルゴリズムの平均ケース解析 (技術レポート). CiteSeerX  10.1.1.32.3425 .
• Eikenberry, Shawna Meyer; Sorenson, Jonathan P. (1998年10月). 「ヤコビ記号を計算するための効率的なアルゴリズム」(PDF) . Journal of Symbolic Computation . 26 (4): 509– 523. CiteSeerX  10.1.1.44.2423 . doi :10.1006/jsco.1998.0226.

外部リンク

• Jacobi 記号を計算する(Wayback Machineの 2016-10-05 アーカイブ) には、計算の手順が表示されます。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Jacobi_symbol&oldid=1321383277"