jacobiSymbol

ヤコビ記号

構文

J = jacobiSymbol(a,n)

説明

J = jacobiSymbol(a,n) は整数 a および正の奇数の整数 n についてヤコビ記号の値を返します。

例

ヤコビ記号の周期性

$$a=1,2,\dots ,9$$ および $$n=3$$ に対するヤコビ記号を求めます。

a = 1:9;
n = 3;
J = jacobiSymbol(a,n)

J = 1×9

     1    -1     0     1    -1     0     1    -1     0

$$a\equiv b(modn)$$ という条件の下で $$\left(\frac{a}{n}\right)=\left(\frac{b}{n}\right)$$ が成り立つ場合、ヤコビ記号は最初の引数に対して周期的です。

ヤコビ記号の完全乗法的性質

$$a=28$$ および $$n=9$$ に対するヤコビ記号を求めます。

J = jacobiSymbol(28,9)

J = 
1

ヤコビ記号が $$a=a_1\times a_2\times \dots a_r$$ に対して $$\left(\frac{a}{n}\right)=\left(\frac{a_1}{n}\right)\times \left(\frac{a_2}{n}\right)\times \dots \left(\frac{a_r}{n}\right)$$ の関係を満たす場合、ヤコビ記号は完全乗法的関数です。ヤコビ記号が $$a=28=2\times 2\times 7$$ に対するこの関係に従うことを示します。

Ja = jacobiSymbol(2,9)*jacobiSymbol(2,9)*jacobiSymbol(7,9)

Ja = 
1

このヤコビ記号は $$n=n_1\times n_2\times \dots n_r$$ に対する $$\left(\frac{a}{n}\right)=\left(\frac{a}{n_1}\right)\times \left(\frac{a}{n_2}\right)\times \dots \left(\frac{a}{n_r}\right)$$ の関係も満たします。ヤコビ記号が $$n=9=3\times 3$$ に対するこの関係に従うことを示します。

Jb = jacobiSymbol(28,3)*jacobiSymbol(28,3)

Jb = 
1

ヤコビ記号を使用した素数判定

ヤコビ記号 $$\left(\frac{a}{n}\right)$$ を使用してソロベイ・シュトラッセン素数判定ができます。奇数の整数 $$n>1$$ が素数の場合、次の合同

$$\left(\frac{a}{n}\right)\equiv a^{(n-1)/2}(modn)$$

は、すべての整数 $$a$$ を保持しなければなりません。整数 $$a$$ が、この合同関係を満たさない $$\{1,2,\dots ,n-1\}$$ 内にある場合、$$n$$ は素数ではありません。

$$n=561$$ が素数であるかどうかをチェックします。$$a=19$$ を選択し、素数判定を行います。2 つの値を合同関係において比較します。

最初に、ヤコビ記号を使用して合同関係の左辺を計算します。

n = 561;
a = 14;
J = jacobiSymbol(a,n)

J = 
1

合同関係の右辺を計算します。

m = powermod(a,(n-1)/2,n)

m = 
67

整数 $$n=561$$ は $$a=19$$ について合同関係を満たさないため、素数ではありません。

checkPrime = mod(J,n) == m

checkPrime = logical
   0

次に、$$n=557$$ が素数であるかどうかをチェックします。$$a=19$$ を選択し、素数判定を行います。

n = 557;
a = 19;
J = jacobiSymbol(a,n);
m = powermod(a,(n-1)/2,n);

整数 $$n=557$$ は $$a=19$$ について合同関係を満たすため、おそらく素数です。

checkPrime = mod(J,n) == m

checkPrime = logical
   1

$$\{1,2,\dots ,556\}$$ 内のすべての $$a$$ について素数判定を行い、整数 $$n=557$$ が真に素数であることを確認します。

a = 1:n-1;
J = jacobiSymbol(a,n);
m = powermod(a,(n-1)/2,n);
checkPrime = all(mod(J,n) == m)

checkPrime = logical
   1

isprime を使用して結果を比較します。

isprime(n)

ans = logical
   1

入力引数

a — 入力

数値 | ベクトル | 行列 | 配列 | シンボリック数 | シンボリック配列

入力。数値、ベクトル、行列、配列、シンボリック数またはシンボリック配列として指定します。a の要素は整数でなければなりません。a と n は同じサイズであるか、一方がスカラーでなければなりません。

データ型: single | double | sym

n — 入力

数値 | ベクトル | 行列 | 配列 | シンボリック数 | シンボリック配列

入力。数値、ベクトル、行列、配列、シンボリック数またはシンボリック配列として指定します。n の要素は正の奇数の整数でなければなりません。a と n は同じサイズであるか、一方がスカラーでなければなりません。

データ型: single | double | sym

出力引数

J — 出力値

–1 | 0 | 1

出力値。–1、0、または 1 として返されます。

データ型: single | double | sym

詳細

ヤコビ記号

ヤコビ記号 $$\left(\frac{a}{n}\right)$$ は次のようにルジャンドル記号の積として定義されます。

$$\left(\frac{a}{n}\right)={\left(\frac{a}{p_1}\right)}^{k_1}{\left(\frac{a}{p_2}\right)}^{k_2}\dots {\left(\frac{a}{p_r}\right)}^{k_r}$$

ここで、a は整数、n は次の素因数分解による正の奇数の整数です。

$$n=p_1^{k_1}{p}_2^{k_2}\dots p_r^{k_r}.$$

整数 a および奇素数 p に対するルジャンドル記号 $$\left(\frac{a}{p}\right)$$ は次のように定義されます。

$$\left(\frac{a}{p}\right)=\{\begin{array}{ll}0\hfill & \text{if }a\equiv \text{0 (mod }p)\hfill \\ 1\hfill & \text{if }a\text{ is a quadratic residue modulo }p\text{ or }{x}^2\equiv a\text{ (mod }p)\text{ has a nonzero solution for }x\hfill \\ -1\hfill & \text{if }a\text{ is a quadratic nonresidue modulo }p\text{ or }{x}^2\equiv a\text{ (mod }p)\text{ has no solutions for }x\text{.}\hfill \end{array}$$

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

参照

[1] Dietzfelbinger, M. Primality Testing in Polynomial Time: From Randomized Algorithms to "PRIMES Is in P". Springer, 2004.

バージョン履歴

R2020a で導入

参考

mod | powermod | isprime