アルゴリズム論特論（塩田）第9回 (3) カーマイケル数
カーマイケル数
フェルマ・テストを不完全たらしめている最大の原因はカーマイケル数の存在です。
Def.11 gcd(b,n)=1 を満たす全ての整数 b に対して
bn−1≡1(modn)
が成り立つ合成数 n をカーマイケル数と呼ぶ。
Ex.12 n=561=3×11×17 はカーマイケル数である。
証明 gcd(b,561)=1 であれば、フェルマの小定理より
b2≡1(mod3),b10≡1(mod11),b16≡1(mod17)
となります。それぞれ、
280 乗、
56 乗、
35 乗すると
b560≡1(mod3),b560≡1(mod11),b560≡1(mod17)
となり、
b560−1 は
3,
11,
17 の公倍数ですから
b560≡1(mod561).
(証明終)
次の定理を使うと大きなカーマイケル数を作ることができます。
Th.13 p=6k+1, q=12k+1, r=18k+1 が全て素数であれば n=pqr はカーマイケル数である。
証明は
Ex.12 と全く同じです。
Ex.14
k = 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271609318291
のとき
p = 6k + 1 = 13438468453066825263344653683410665668729872983407897209399934605782751227080965672285264959629655909747
q = 12k + 1 = 26876936906133650526689307366821331337459745966815794418799869211565502454161931344570529919259311819493
r = 18k + 1 = 40315405359200475790033961050231997006189618950223691628199803817348253681242897016855794878888967729239
は全て素数で
n = pqr = 14561314392384758852607372045391100342305613529432683239147836573776346740245578013749386663115053375527637666588629193151550389687696379599004671655261602333117349735165428436344922950761580622183044886774735262914257003709862150465768021078578761491289686266731268838123191809245649371909369818627048924845769
は 1031 ビットのカーマイケル数。
Rem.15 bn−1%n は
gcd(b,n) の倍数です。
ですから、
n がカーマイケル数のときは、
- gcd(b,n)=1 ⇔ bn−1%n=1
- gcd(b,n)≠1 ⇔ bn−1%n≠1
ということになります。
カーマイケル数
n が小さな素因子を持てば、
底
b をランダムにとる version のフェルマ・テストで
n を合成数だと見破ることができますが、
Ex.14 のように素因子が巨大なカーマイケル数では絶望的です。
Rem.16 厄介者のカーマイケル数は無限個存在することが証明されています。
しかし幸いなことに、そんなにたくさんはありません。
Rem.17 カーマイケル数も合成数だと見破ることのできる確率的素数判定法としては
などがあります。
ミラー・ラビン法は今迄の本講義の知識で理解できますがそこそこ複雑です。
ソロベイ・ストラッセン法を理解するには「平方剰余」の知識が必要となります。
Rem.18 1729 は
タクシー数
として有名な数ですが、実はカーマイケル数でもあります。