powermod

べき剰余

構文

c = powermod(a,b,m)

説明

c = powermod(a,b,m) はべき剰余 a^b mod m を返します。入力 a,b は整数でなければならず、m は非負の整数でなければなりません。詳細については、べき剰余を参照してください。

例

べき剰余の計算

powermod を使用して、べき剰余 a^b mod m を計算します。関数 powermod は、指数 a^b を計算しないので効率的です。

c = powermod(3,5,7)

c =
     5

フェルマーの小定理の証明

フェルマーの小定理は、p が素数で a が p によって割り切れない場合、a^(p–1) mod p は 1 であるというものです。

p = 5、a = 3 の場合にフェルマーの小定理をテストします。予想どおり、powermod は 1 を返します。

p = 5;
a = 3;
c = powermod(a,p-1,p)

c =
1

p より小さい a のすべての値に対して同じケースをテストします。関数 powermod は要素ごとに 1 のベクトルを返すように働きます。

p = 5;
a = 1:p-1;
c = powermod(a,p-1,p)

c =
     1     1     1     1

フェルマー テストを使用したフェルマー素数の計算

フェルマーの小定理は、p が素数で a が p によって割り切れない場合、a^(p–1) mod p は 1 であるというものです。逆に、a^(p–1) mod p が 1 で a が p で割り切れない場合、p は必ずしも素数であるとは限りません (p は疑素数である可能性があります)。

2 を底とするフェルマーの小定理を使用して、300 から 400 までの数の素数性をテストします。

p = 300:400;
remainder = powermod(2,p-1,p);
primesFermat = p(remainder == 1)

primesFermat =
   307   311   313   317   331   337   341   347   349   353...
   359   367   373   379   383   389   397

結果を isprime と比較してフェルマーの擬素数を求めます。341 はフェルマーの擬素数です。

primeNumbers = p(isprime(p));
setdiff(primesFermat,primeNumbers)

ans =
   341

入力引数

a — 基数

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

基数。数値、ベクトル、行列、配列、あるいはシンボリック数または配列で指定されます。a は整数でなければなりません。

b — 指数またはべき乗

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

指数またはべき乗。数値、ベクトル、行列、配列、あるいはシンボリック数または配列で指定されます。b は整数でなければなりません。

m — 除数

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

除数。数値、ベクトル、行列、配列、あるいはシンボリック数または配列として指定します。m は非負の整数でなければなりません。

詳細

べき剰余

正の指数 b について、べき剰余 c は次のように定義されます。

c = a^b mod m.

負の指数 b については、定義は m を法とする乗法に関する a の逆元 d を求めることによって拡張できます。つまり、次のようになります。

c = d ^‒b mod m.

ここで、d は次の関係を満たします。

ad mod m = 1.

バージョン履歴

R2018a で導入

参考

mod | nextprime | nthprime | prevprime