Main Content

jacobiSymbol

ヤコビ記号

R2020a 以降

説明

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

すべて折りたたむ

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

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

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

ab(modn) という条件の下で (an)=(bn) が成り立つ場合、ヤコビ記号は最初の引数に対して周期的です。

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

J = jacobiSymbol(28,9)
J = 1

ヤコビ記号が a=a1×a2×ar に対して (an)=(a1n)×(a2n)×(arn) の関係を満たす場合、ヤコビ記号は完全乗法的関数です。ヤコビ記号が a=28=2×2×7 に対するこの関係に従うことを示します。

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

このヤコビ記号は n=n1×n2×nr に対する (an)=(an1)×(an2)×(anr) の関係も満たします。ヤコビ記号が n=9=3×3 に対するこの関係に従うことを示します。

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

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

(an)a(n-1)/2(modn)

は、すべての整数 a を保持しなければなりません。整数 a が、この合同関係を満たさない {1,2,,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=561a=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=557a=19 について合同関係を満たすため、おそらく素数です。

checkPrime = mod(J,n) == m
checkPrime = logical
   1

{1,2,,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 の要素は整数でなければなりません。an は同じサイズであるか、一方がスカラーでなければなりません。

データ型: single | double | sym

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

データ型: single | double | sym

出力引数

すべて折りたたむ

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

データ型: single | double | sym

詳細

すべて折りたたむ

ヤコビ記号

ヤコビ記号 (an) は次のようにルジャンドル記号の積として定義されます。

(an)=(ap1)k1(ap2)k2(apr)kr

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

n=p1k1p2k2prkr.

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

(ap)={0if a0 (mod p)1if a is a quadratic residue modulo p or x2a (mod p) has a nonzero solution for x1if a is a quadratic nonresidue modulo p or x2a (mod p) has no solutions for x.

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

参照

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

バージョン履歴

R2020a で導入

参考

| |