jacobiSymbol
説明
例
ヤコビ記号の周期性
および に対するヤコビ記号を求めます。
a = 1:9; n = 3; J = jacobiSymbol(a,n)
J = 1×9
1 -1 0 1 -1 0 1 -1 0
という条件の下で が成り立つ場合、ヤコビ記号は最初の引数に対して周期的です。
ヤコビ記号の完全乗法的性質
および に対するヤコビ記号を求めます。
J = jacobiSymbol(28,9)
J = 1
ヤコビ記号が に対して の関係を満たす場合、ヤコビ記号は完全乗法的関数です。ヤコビ記号が に対するこの関係に従うことを示します。
Ja = jacobiSymbol(2,9)*jacobiSymbol(2,9)*jacobiSymbol(7,9)
Ja = 1
このヤコビ記号は に対する の関係も満たします。ヤコビ記号が に対するこの関係に従うことを示します。
Jb = jacobiSymbol(28,3)*jacobiSymbol(28,3)
Jb = 1
ヤコビ記号を使用した素数判定
ヤコビ記号 を使用してソロベイ・シュトラッセン素数判定ができます。奇数の整数 が素数の場合、次の合同
は、すべての整数 を保持しなければなりません。整数 が、この合同関係を満たさない 内にある場合、 は素数ではありません。
が素数であるかどうかをチェックします。 を選択し、素数判定を行います。2 つの値を合同関係において比較します。
最初に、ヤコビ記号を使用して合同関係の左辺を計算します。
n = 561; a = 14; J = jacobiSymbol(a,n)
J = 1
合同関係の右辺を計算します。
m = powermod(a,(n-1)/2,n)
m = 67
整数 は について合同関係を満たさないため、素数ではありません。
checkPrime = mod(J,n) == m
checkPrime = logical
0
次に、 が素数であるかどうかをチェックします。 を選択し、素数判定を行います。
n = 557; a = 19; J = jacobiSymbol(a,n); m = powermod(a,(n-1)/2,n);
整数 は について合同関係を満たすため、おそらく素数です。
checkPrime = mod(J,n) == m
checkPrime = logical
1
内のすべての について素数判定を行い、整数 が真に素数であることを確認します。
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
詳細
ヤコビ記号
ヤコビ記号 は次のようにルジャンドル記号の積として定義されます。
ここで、a は整数、n は次の素因数分解による正の奇数の整数です。
整数 a および奇素数 p に対するルジャンドル記号 は次のように定義されます。
n が奇素数の場合、ヤコビ記号はルジャンドル記号と等しくなります。
参照
[1] Dietzfelbinger, M. Primality Testing in Polynomial Time: From Randomized Algorithms to "PRIMES Is in P". Springer, 2004.
バージョン履歴
R2020a で導入
MATLAB コマンド
次の MATLAB コマンドに対応するリンクがクリックされました。
コマンドを MATLAB コマンド ウィンドウに入力して実行してください。Web ブラウザーは MATLAB コマンドをサポートしていません。
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)