ヤコビ記号

ヤコビ記号の概要

ヤコビ記号は、1837年に数学者ヤコビによって導入された、整数と奇素数に関連した数学的な記号です。この記号は、数論や合同算術といった分野において、特に素数の判定や素因数分解という重要な計算に利用されます。具体的には、任意の整数 `a` と正の奇整数 `n` に対して、ヤコビ記号は以下のように定義されます。

$$
\left(\frac{a}{n}\right) = \prod_{i=1}^{k} \left(\frac{a}{p_i}\right)^{\alpha_i}
$$

ここでは、`n` の素因数分解を `n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}` と表しています。\

ヤコビ記号の性質

ヤコビ記号の性質は、ルジャンドル記号に酷似しており、次のような特性を持ちます。まず、`n` が奇数の素数であれば、ヤコビ記号はルジャンドル記号と等しくなります。また、もし `a` が `n` と合同であるならば、次の関係が成り立ちます。

$$
\left(\frac{a}{n}\right) = \left(\frac{b}{n}\right) = \left(\frac{a \pm m \cdot n}{n}\right)
$$

これにより、ヤコビ記号は「分子」の `a` に関して完全な乗法的関数として機能します。\

ヤコビ記号の計算方法

ヤコビ記号を計算する際には、いくつかの規則が利用できます。例えば、`gcd(a, n)` が1であれば、ヤコビ記号は±1のいずれかになります。また、もし分子が1になった場合、結果は1となります。これらの計算を効率的に行うために、ユークリッドの互除法に似た手法が用いられ、計算量は O(log a log b) となります。\

素数性判定への応用

ヤコビ記号は、素数の判定にも利用されています。例えば、ある数 `n` が素数か合成数か不明な場合、乱数`a`を選択し、ヤコビ記号を計算することで、結果を比較する手法が使われます。この方法により、`n` が合成数であれば必ず異なる結果が得られ、逆に多くの異なる`a`に対して同じ剰余が得られる場合、`n` は「おそらく素数」であるとされます。

計算例

ヤコビ記号の計算例として、素数9907に対する (1001/9907) の値を求めることを考えます。この場合、ルジャンドル記号や他の定義を使用して計算を進めます。この際、

• - `1001` は `7`, `11`, `13` に因数分解され、それぞれのヤコビ記号を計算することで、最終的に `-1` という結果が得られます。
• - 一方、ヤコビ記号の定義をそのまま利用する場合、効率的な計算が可能となり、より迅速に結論に達することができます。

ヤコビ記号は、計算や数論において非常に役立つ道具であり、特に現代の暗号理論においてその重要性は高まっています。これにより、数を扱う方法や新たなアルゴリズムの開発が進んでいます。

もう一度検索