あなたは、素数判定アルゴリズムをいくつ知っているだろうか？ 素数判定について少し調べてみると、大抵は試し割り法や、少し踏み込んでもMiller-Rabinテストが紹介されて終わるのが関の山だ。理論に興味のある人なら、AKSテストという名前を聞いたことがあるかもしれない。確かに、これらさえ知っておけば生きていく上で困ることはない。 しかし――それだけが素数判定の世界ではない。 素数が整数論のあらゆる場所に現れるように、素数判定法もまた、驚くほど多様に存在する。単純に割り算を繰り返すだけの素朴な方法から、合同式や群論的な性質を利用した手法、さらには楕円曲線やGauss和といった高度な数学的道具に支えられたアルゴリズムまで、整数論のあらゆる道具が登場する。また、すべての整数に対して汎用的に使える方法だけでなく、特定の形の数に対してのみ強力に機能する、いわば専用アルゴリズムのような判定法も存在する。 このように見ていくと、「素数かどうかを判定する」というごく単純な問題の背後に、非常に豊かな世界が広がっていることが分かるだろう。 本書『素数判定法集覧』は、そうした「素数判定法の全体像」を一望するための一冊である。 試し割り法のような素朴な方法から始まり、Fermatテスト、Eulerテスト、Solovay-Strassenテスト、Miller-Rabinテストといった確率的手法、LucasテストやBaillie-PSWテスト、さらにはAPRテストやAKSテスト、楕円曲線法を紹介する。また、理論だけでなく極力Pythonによる実装例も掲載した。数式だけではイメージしにくい部分も、実際に動かしてみることで理解が進むことがあるだろう。 個々の記事は、なるべく単体でも読めるように意識して記述している。興味のある手法だけをつまみ読みすることも可能だ。しかし一方で、最初から順番に読み進めていくことで、より自然に理解が積み上がるようにも意図している。最終的には、必要に応じて参照する辞書のように使っていただければ幸いである。 なお、数学的な道具そのものの詳細な解説については、他書に委ねている部分も多い。本書はあくまで「素数判定法」に焦点を当てており、その背景にある理論を網羅的に解説することを目的としてはいない。そのため、必要に応じて参考文献や教科書を参照しながら読み進めることを推奨する。 【想定する読者】 本書は、単に素数判定を「使いたい」人よりも、「理解したい」「楽しみたい」人に向いている。 ・整数論や暗号理論、アルゴリズムに興味がある方 ・素数が大好きでたまらない、へんたいふしんしゃさん