FermatとPrime
mod23
素数が法のpowermod
１．底が既知数
このワークシートはMath by Codeの一部です。
フェルマーの小定理から、
底が既知のときは、法が素数ｐなら、p-1乗が１と合同であることが使えるね。
＜大きい指数の剰余を求める＞
（例）指数が大きめ
「 のｘ」は？
９は73の倍数ではないから、フェルマーの小定理が使えるね。
73-1=72で、 。左辺と同じ表現を作り、１に置き換えることで指数を激減できる。
7777=72･108+1だから、
だから、x=9。
＜指数も底も大きいときの剰余＞
（例）底が合成数
「のｘ」は？
底が合成数なので分解しよう。
2002=22･91 だから、
x=1。
（例）底が素数
「 のｘ」は？
90=22･4+2、37=23+14。
これから、
x=12。
（一般論を考えよう）
底が合成数でもなく底のサイズも指数も大きいときは、どうするか
ab(mod23)を求めたいとき、底も指数も剰余を求めよう。
b=22c+d
a=23e+f
ab(mod23)≡ad(mod23)≡(23e+f)d(mod23)
≡fd(mod23)
二項定理から、fd以外すべて23の倍数の項だから０。
dは22未満なので、dは５桁以下の２進数になるね。d=hijkl(2)
lが１ならf1(mod23)≡8をたてる。
kが１ならf2(mod23)≡82≡18をたてる。
jが１ならf4(mod23)≡182≡2をたてる。
iが１ならf8(mod23)≡22≡4をたてる。
hが１ならf16(mod23)≡42≡13をたてる。
だから、fd(mod23)≡13h・４i・２j・18k・８l(mod 23)
hijklのうち0があれば0乗は１だ。だから、最悪でも(13・4・２・18・8 )÷23の計算をするだけ。
これで、桁爆発がおきにくくなるでしょう。
＜大きい法の剰余＞
（例）法の素数が大きめ
「 のｘ」は？
2003は素数だから、フェルマーの小定理から
2002-2000=2だから、xに２を２乗したもの、４をかけると1と剰余は1と合同になる。
4x≡1（2003)を解く。
1≡1+2003=2004と４の倍数にすれば４割れるね。
x≡2004÷4=501(mod2003)
。
２．fermatとprime判定
フェルマーの小定理を論理式でかこう。
F：整数pとpの倍数でない整数aに対して、「ｐが素数」ならば「ap-1≡1(mod p)」
ベン図でかくと、「素数pの集合P」を「ap-1≡1(mod p)となる数ｐの集合F」が包んでいる図になる。
FはPより、ゆるい、広いというイメージで関係をつかもう。
逆F：整数pとpの倍数でない整数aに対して、「ap-1≡1(mod p)」ならば「ｐが素数」
対偶F:整数pとpの倍数でない整数aに対して、「ap-1≡1(mod p)でない」ならば「ｐが素数でない」
Fが真であることと、対偶Fが真であることは同値だね。
だから、フェルマーの小定理は対偶の形式でも使える。Fに入らない数は当然Pに入らない。
しかし、逆は成り立つとは限らない。Fに入る数でも、Pでない数がありうる。
だから、フェルマーの小定理は「素数でない判定」には使えるけれど、「素数の判定」には使えない。
＜素数でない判定には使える＞
判定するまでもなく、「aがpの倍数」だと、フェルマーの定理はなりたたない。
たとえば、p=3で、a=15としよう。152=225≡0(mod3）となり、３で割った剰余は１にならない。
これは、素数かどうかの判定というよりも、前提条件を満たしていないというだけのこと。
言い換えると、「pが素数ではない判定」をしたいならば「aはｐの倍数でないなら何でもよい。」
ということだ。a=2のようにべき乗を計算しやすいものがおすすめ。
（例）「213が素数でない判定」は？
2212のmod213による剰余が１でないことだ。
2は何乗しても法の213の倍数にならない。
212を割れないときは１引き、２のべきで割る。
212を２のべき乗の和に分解して、2進数の発想で計算してもよいが、
2進数にしたときの桁数が多いため、前段階の計算がわりと必要になる。
212=53･4。53-1=13･4, 13-1=3･4。
だから、4乗か2倍の計算でそのつど、剰余にして桁減らしを繰り返すことにしてみる。
212=(23)4=(64)2≡49(mod213)
252=(213)4＝(212･２)4≡(49・2)4≡96042≡192≡361≡148≡-65(mod213)
2212=(253)4=(252・2)4≡(-65・2)4≡(-130)4≡(832)2≡(6889)2≡(73)2≡5329≡4(mod213)
2212≡４(mod213）だから、剰余が１でない。
だから、「213は素数でない判定」は成り立つ。
実際213=3×71。
（例）「223が素数でない判定」は？
2222がmod223の剰余が１でないことを求めよう。
2は何乗しても法の223の倍数にならない。
222を割れないときは１引き、２のべきで割る。
222=111･2。111-1=55･2, 55-1=27･2。27-1=13・2, 13-1=3･4。
だから、2乗か2倍の計算でそのつど、剰余にして桁減らしを繰り返すことにしてみる。
212=(23)4=(64)2≡82(mod223)
254=((213)2･２)2＝((82･２)2･２)2≡(1642・2)2≡((-59)2･2)2≡69622≡492≡2401≡171(mod223)
2222=((254・2)2・2)2=((171・2)2・2)2≡(1192・2)2≡(112・2)2≡2242≡1(mod223)
2222≡1(mod223）だから、剰余が１。
だから、「223は素数でない判定」は成立しない。
しかし、素数でない判定が成立しないからといって、素数だとも言い切れない。
たまたま、223は素数だけれど、上記の計算結果がそれを正当化しているわけではない。
サルは人間に似ているけど、人間でない動物だ。
素数の可能性の条件にはあうのに、素数でない数というものがある。
それを次にみていこう。
３．やっかいなおサルさん？
人間のようで、人間でない動物がいるように、
素数の可能性の条件に合格しても、素数でない数がある。
フェルマーの小定理の後件にあうのに、前件にあわない数だ。
pの倍数でないaに対して「ap-1≡1(mod p)」なのに「素数でない」数ｐもある。
＜擬素数＞
擬素数[pseudo prime, almost prime]
aの選び方によってはp-1乗の剰余が１になったり１でなかったりする数もある。
たとえば、341は31･11だから、合成数だ。
でも、2340≡1(mod 341)
しかし、3340≡56(mod341)
（計算は省略した。指数を2進化して、そのつど法で割った剰余にし、最後に掛け算して、
剰余をもとめればよいね。）
底の選び方によって変わってくる。
341は擬素数と呼ばれる。
#[IN]julia
#=========================================
#341=33*11
#でも、2^340≡1(mod 341)
#しかし、3^340≡56(mod341)
println("2^340 mod 341 =", powermod(2,340,341))
println("3^340 mod 341 =", powermod(3,340,341))
#=========================================
[OUT]
2^340 mod 341 =1
3^340 mod 341 =56
＜カーマイケル数＞
しかし、aの選び方を変えてもｐの倍数以外なら、いつでも１になるという、
超まぎらわしい数もある。つまり、オイラーの小定理の対偶によって、素数の可能性がないという判定ができないのに、素数ではない数だ。
それが、カーマイケル数。
たとえば、561=3･11･17だ。
３，１１，１７は素数だから、フェルマーの小定理から
aが3,11,17の倍数でないなら、
a2≡1(mod3), a10≡1(mod11), a16≡1(mod17)
a560≡(a2)280≡1(mod3), a560≡(a10)56≡1(mod11), a560≡(a16)35≡1(mod17)
だから、a560≡1(mod561)となる。
a561≡a(mod561)の形にすれば、aはすべての数で成り立つことになるね。
561=3･11･17に対して、2,10,16が560の約数になっていたから、カーマイケル数になった。
だから、C=p･q･rに対して、p-1,q-1,r-1がC-1の約数になっていればカーマイケル数になれるね。
10000以下では
561=3･11･17で2,10,16が560の約数。
1105=5･13･17で4,12,16が1104の約数。
1729=7･13･19で6,12,18が1728の約数。
2465=5･17･29で4,16,28が2464の約数。
2821=7･13･31で6,12,30が2820の約数。
6601=7･23･41で6,22,40が6600の約数。
8911=7･19･67で6,18,66が8910の約数。
の7個ある。
・カーマイケル数は奇数だ。
カーマイケル数なら、an≡a(mod n)。a=-1のとき、(-1)n≡-1(mod n)
これから、nは奇数。
質問：1000以下の素数を使ったカーマイケル数を作り、小さい順にならべるにはどうしたらよいでしょうか。
素数リストから小さい順に３数a,b,cを取り出しその積mickel=a・b・cを
a-1,b-1,c-1で割った剰余の和が0ならば、カーマイケル数のリストmickelsにmickelを追加しましょう。
#[IN]Python
#=============================================================
from itertools import combinations
lim=1000
divCount=lambda n:len(list(filter(lambda m:n % m==0, list(range(1,n+1)))))
M=list(range(1,lim))
P=[x for x in M if divCount(x)==2]
mickels=[]
for a,b,c in combinations(P, 3):
mickel = a*b*c
if (mickel-1) % (a-1) + (mickel-1) % (b-1) + (mickel-1) % (c-1) ==0 :
mickels.append(mickel)
mickels.sort()
print(mickels)
#=============================================================
#[OUT]
[561, 1105, 1729, 2465, 2821, 6601, 8911,
10585, 15841, 29341, 46657, 52633, 115921,
162401, 252601, 294409, 314821, 334153, 399001, 410041, 488881, 512461, 530881,
1024651, 1152271, 1193221, 1461241, 1615681, 1857241, 1909001, 2508013, 3057601, 3828001, 4335241, 5049001, 5148001, 5444489, 6189121, 6733693, 6868261, 7519441, 9439201,
10024561, 10267951, 11972017, 14469841, 14676481, 15829633, 17098369, 17236801, 19384289, 29111881, 31405501, 34657141, 37964809, 50201089, 56052361, 64377991, 68154001, 79624621, 82929001, 92625121,
116682721, 118901521, 172947529, 216821881]