ミラーラビン素数判定法の補足

フェルマーの小定理を理解する前に、まずは「体」を学びましょう。

「体とはなんぞや」ということになるのですが身近なところだと「有理数体」とか「実数体」とかがあります。

ひどく大雑把に言えば、「体」とは四則演算が(ゼロ除算を除いて)自由に行える代数系のことです。

例えば整数は加法・減法・乗法に対して閉じています(整数同士の加法・減法・乗法の結果は必ず整数になる)が、除法は整数にならないパターンがあるので、体ではありません。

有理数や実数は四則演算の結果がそれぞれ必ず有理数になりますし、実数になるので体というわけです。

  • 加法に対して
    • マイナス元が存在する
    • 結合法則が成立する
    • 交換法則が成立する
  • 乗法に対して
    • 逆元が存在する
    • 単位元が存在する
    • 結合法則が成立する
  • 分配法則が成立する

これらが成立すれば基本的には「体」だといえます。

本来はもっともっと厳密な定義があるのですが、ここでは省略します(そもそも本人がよくわかっていない)

剰余群

まず、整数の集合(整数環)の整数pに対する剰余群(集合)を考えてみます。これは記号を使って以下のように表せます。

ちなみにZは整数環を表します。

整数のpの剰余なのでこれは0からp-1までの数しかないのはわかると思います。

整数環Zとp=5の剰余群の比較

さて、この剰余群ですがよく見ると加法に閉じていることがわかります。

更に注目すると、

なんと乗法に対しても閉じていたりします。

これはなんだか都合がいい感じですね。

整域

整域というのはこれまた超大雑把にいえば、二つの元(値)の乗算の結果が0になったとき「少なくとも一方は(零元)0であると言えるか?」ということと深いつながりがあります。

実数や複素数の場合にはこれがいえますが、それは実数や複素数が「体」だからです。

さて、先程の剰余群ですがもしもpが素数の場合は「積が0ならばどちらか一方が0だ」ということができます。

まず、ある整数nの剰余が0になるのはその定義から整数kを用いて、

と書かれる場合のみです。

ここでpが仮に素数であれば、素数は1と自分自身しか約数を持たないので、

のように因数分解できません。

よって必ず次のように表すことができます。

このときp mod pが必ず0になるので、少なくとも一方が0だといえます。

p=6の剰余群

pが素数でない場合は、pの約数(今回はp=6としてm=3, n=4で検証した)をとってくることで0でない二つの元(値)から乗算結果が0に式をつくることができます。

つまり、pが素数かどうかで剰余群はその性質を変えてしまうのです。

その他の証明は省きますが、pが素数の場合は剰余群Zpは剰余体と呼ばれる「体」になるのです。

自明な平方根

さて、本題に入ります。

まず、剰余体(有限体)Zpの1の自明な平方根を考えます。

わからない人はいないとは思いますが、上の式はZpからとってきたある数xの二乗のpの剰余と1のpの剰余が合同(等しい)ということを意味します。

要するに、xの二乗はpで割ると1あまるということなので、xの二乗から1を引いたものは剰余が0なことは自明です。

さて、これらの剰余が0ということはpは素数なのでx+1かx-1はpの倍数でなければいけません。つまい、以下のどちらかが成立します。

xはZpからとってきているので、xは0からp-1の範囲なです。

よって、次のように言い換えられます。

これらを変形すると次のようになります。

xはZpからとってきているのでx=p+1は実際には、

となるので、

となり、剰余体Zpにおいては1の平方根がp-1と1しかないことが示せました。

フェルマーの小定理

フェルマーの小定理によれば、pを素数とし、aをpと互いに素な整数とすると、

が成立するというものでした。

ではここで、以下の式を考えてみましょう。

これはフェルマーの小定理からnが素数であれば(aとは互いに素なので)必ず1を返します。

aは剰余体Znの元(0からn-1の中の任意の値)であるとします。

さて、2以外のすべての素数は奇数なので奇素数をnとすれば、

と表すことができます。

従って、フェルマーの小定理の指数部分を書き換えることができ、

となります。

nが奇素数であれば先程の自明な平方根の論法で、この平方根は1かn-1になります。

1であれば更にその平方根を考えていきます。

これは2の指数部分が0になるまで(平方根がとれるまで)続けることができ「0になるまでにあるsの値で平方根がn-1になるか、どんなsでも平方根が1であり続ける」のどちらかになります。

つまりこれは、nが奇素数であれば次のどちらかが成立することを意味します。

ただし、rは以下の式を満たします。

つまり、

これの対偶をとれば、

要するに

「あるaに対してrを小さくしていっても剰余がn-1にならずr=0になったときに剰余が1でなければ絶対に素数ではない」ということである。

つまり、どこかで剰余がn-1になれば “素数かもしれない” と判断できる。

このとき “素数かもしれない” という判定を下したaを「証拠」と呼ぶ。

実際には素数ではないにも関わらず、 “素数かもしれない” と判断を下すaを「強い嘘つき」と呼ぶ

強い嘘つきaは剰余体(有限体)Znの真の部分群なので(ここは証明がないのでわからない、とりあえずそうらしい)、Zpの全ての元が強い嘘つきではない。

よって、調べたい数nが合成数であることを見抜く「証拠」となるaが必ずZnに存在する。

拡張リーマン予想が正しければ、そのaが含まれる集合は高々(ln n) ^2より小さい元から生成されるらしい。

最後の方はリーマン予想が込み入ってきているのでさっぱりわからんが、要するにZnに含まれる全てのaを調べる必要はないらしい。

よくわからないのだが、なんとなく理解できた気がするので次はリーマン予想を勉強したいです。