素数の判定はクラスP
素数が面白いのは、何もリーマン予想があるからだけではありません。「何の役に立つんだ」と思われる方もおられるでしょうが、実は結構重要（特に暗号理論に）なのが、素数判定法です。ある自然数が素数かどうかを判定するのは、しかしながら、そう簡単なことではありません。
歴史的にも現実にも有名なのが、エラトステネスの篩に代表される。「篩法」です。簡単に言えば、その自然数より小さな素数で順に割っていって、余りが出なければ（割り切れれば）合成数、割り切れなければ素数というもので、例えば９１が素数かどうかを判定するには、
２で割っても１余りが出る［1≡91 (mod 2)］。
３で割っても１余りが出る［1≡91 (mod 3)］。
以下、
3≡91 (mod 4)、1≡91 (mod 5)、1≡91 (mod 6)、0≡91 (mod 7)
おっと、７で割り切れちゃいましたね（7¦91）。なので、91は合成数だと（素数でない）わかります。これが原始的？篩法で、何のことはない、極めて単純な方法です。ただ、この方法で大きな数の方まで素数判定していくと、どんどん必要な計算量が増えていき、しかも比喩的表現で良ければ、「指数関数的」に増大していくので、巨大な数の判定は事実上不可能になります。もちろん、もっといいアルゴリズムが数多く提案されてきましたが、例えば、自然数nの素数判定にせいぜいlog(n)の多項式で表される時間で十分な判定法は見つかっていませんでした。
ここに登場したのが、マニンドラ・アグラヴァル博士指導下、当時学部学生だったニーラージュ・カヤル博士とナイティン・ザクセナ博士で、実質上、二人の学部の卒業論文として提出されたのが、AKS素数判定法です。ちなみにAKSは３博士のイニシャルから取られています。簡単にアルゴリズムを紹介すると、2以上の自然数、nの素数性判定には、
1．nが任意の自然数mの累乗で表されるなら、言うまでもなくnは合成数となり、ここで終了。そうでなければ２へ。
2．np≡1 (mod r)となる最小の自然数をpとしたとき、p>4(logn)2となる最小のrを見いだす。
3．
の間の自然数、qを置く。1から順に大きくしていくのが通常。ここで、φはオイラーのtotient関数で、［］はガウス記号（中身を超えない最大の整数）である。
4．ある自然数2≦q≦rに対して、qとnの最大公約数が2以上でかつn未満であれば、nは（当たり前ですが）合成数で、計算終了。
5．nがr以下なら、nは素数と結論でき、計算終了。
6．
なら、nは合成数で計算終了。そうでないならqを1増分して４へ。
7．nは素数である。
実際の計算量は結構多いので、実用的というわけではありませんが、log(n)の多項式で表される時間量（正確には決定的多項式時間）で判定可能であることが証明されたことはなかなか衝撃を持って迎えられました。しかも、当時学部学生のニーラージュ・カヤル博士とナイティン・ザクセナ博士の卒業研究だというのが二重の驚きです。P≠NP問題に関しては、別途触れさせて頂きますが、クラスPでないと考えられていた問題が、クラスPだと証明されてしまったわけで、その意義は十分に大きいものがあります。
これをお読みの大学生の皆さん。卒業論文で驚異的な研究を行える余地は十分にあるはずです。私には昔の話ですが、皆さんの前途は明るいのです。
歴史的にも現実にも有名なのが、エラトステネスの篩に代表される。「篩法」です。簡単に言えば、その自然数より小さな素数で順に割っていって、余りが出なければ（割り切れれば）合成数、割り切れなければ素数というもので、例えば９１が素数かどうかを判定するには、
２で割っても１余りが出る［1≡91 (mod 2)］。
３で割っても１余りが出る［1≡91 (mod 3)］。
以下、
3≡91 (mod 4)、1≡91 (mod 5)、1≡91 (mod 6)、0≡91 (mod 7)
おっと、７で割り切れちゃいましたね（7¦91）。なので、91は合成数だと（素数でない）わかります。これが原始的？篩法で、何のことはない、極めて単純な方法です。ただ、この方法で大きな数の方まで素数判定していくと、どんどん必要な計算量が増えていき、しかも比喩的表現で良ければ、「指数関数的」に増大していくので、巨大な数の判定は事実上不可能になります。もちろん、もっといいアルゴリズムが数多く提案されてきましたが、例えば、自然数nの素数判定にせいぜいlog(n)の多項式で表される時間で十分な判定法は見つかっていませんでした。
ここに登場したのが、マニンドラ・アグラヴァル博士指導下、当時学部学生だったニーラージュ・カヤル博士とナイティン・ザクセナ博士で、実質上、二人の学部の卒業論文として提出されたのが、AKS素数判定法です。ちなみにAKSは３博士のイニシャルから取られています。簡単にアルゴリズムを紹介すると、2以上の自然数、nの素数性判定には、
1．nが任意の自然数mの累乗で表されるなら、言うまでもなくnは合成数となり、ここで終了。そうでなければ２へ。
2．np≡1 (mod r)となる最小の自然数をpとしたとき、p>4(logn)2となる最小のrを見いだす。
3．
の間の自然数、qを置く。1から順に大きくしていくのが通常。ここで、φはオイラーのtotient関数で、［］はガウス記号（中身を超えない最大の整数）である。
4．ある自然数2≦q≦rに対して、qとnの最大公約数が2以上でかつn未満であれば、nは（当たり前ですが）合成数で、計算終了。
5．nがr以下なら、nは素数と結論でき、計算終了。
6．
なら、nは合成数で計算終了。そうでないならqを1増分して４へ。
7．nは素数である。
実際の計算量は結構多いので、実用的というわけではありませんが、log(n)の多項式で表される時間量（正確には決定的多項式時間）で判定可能であることが証明されたことはなかなか衝撃を持って迎えられました。しかも、当時学部学生のニーラージュ・カヤル博士とナイティン・ザクセナ博士の卒業研究だというのが二重の驚きです。P≠NP問題に関しては、別途触れさせて頂きますが、クラスPでないと考えられていた問題が、クラスPだと証明されてしまったわけで、その意義は十分に大きいものがあります。
これをお読みの大学生の皆さん。卒業論文で驚異的な研究を行える余地は十分にあるはずです。私には昔の話ですが、皆さんの前途は明るいのです。