Main Content

powermod

べき剰余

ページ内をすべて折りたたむ

構文

c = powermod(a,b,m)

説明

例

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

例

すべて折りたたむ

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

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 は整数でなければなりません。

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

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

詳細

すべて折りたたむ

べき剰余

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

c = ab mod m.

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

c = d ‒b mod m.

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

ad mod m = 1.

バージョン履歴

R2018a で導入

参考

| | |