初心者のための素数判定

『初心者のための素数判定』は、与えられた数が素数かどうかを判定する方法である素数判定に関する学部レベルの数学の本であり、この問題を多項式時間で解く最初の方法であるAKS素数判定を中心にしています。これはLasse Rempe-GillenとRebecca Waldeckerによって書かれ、もともとドイツ語でPrimzahltests für Einsteiger: Zahlentheorie, Algorithmik, Kryptographie（Vieweg+Teubner、2009年）として^{出版されました。 [1] [2]これは}Primality Testing for Beginnersとして英語に翻訳され、2014年にアメリカ数学会によって学生数学図書館シリーズの第70巻として出版されました。 ^{[2] [3] [4] [5]} 2番目のドイツ語版は2016年にSpringerによって出版されました。

『初心者のための素数判定』は7章から成り、2つのパートに分かれています。4章は数論と計算複雑性理論の背景資料、3章はAKS素数判定に関するものです。^{[1] [5]}

第 1 章には、一意に素因数分解する算術の基本定理、二項定理、最大公約数を求めるユークリッドの互除法、素数列を生成するエラトステネスのふるいなど、整数論に関する基礎的な内容が含まれています。第 2 章では、算術における基本的な計算のアルゴリズム、計算可能性の概念、多項式時間アルゴリズム、ランダム化、非決定性多項式時間など、アルゴリズムとその複雑性の研究を開始します。ランダム化アルゴリズムでは、ランダムな時間の経過後に常に正しい答えを返すラスベガス アルゴリズム(クイックソートなど) と、間違った答えを得る可能性が小さいモンテ カルロ アルゴリズム(多項式恒等テストのシュワルツ-ジッペルの補題に基づくアルゴリズムで例示) の違いを紹介します。第3章では、中国剰余定理、フェルマーの小定理、それに基づくフェルマー素数判定など、整数論に関する追加資料が提供される。また、多項式とモジュラー算術を使った計算も紹介する。本書の前半は、素数定理（弱められた形式）、暗号における素数の応用、ランダム多項式時間で実行される広く使用されているミラー・ラビン素数判定など、素数と素数判定の歴史に関する第4章で締めくくられる。^[5]

第 5 章では、フェルマーの小定理を数値から多項式に一般化し、この一般化に基づくランダム素数判定法を紹介します。第 6 章では、AKS 素数判定法の正しさの背後にある重要な数学的結果を示し、第 7 章では、この判定法自体について説明します。^[5]アルゴリズムの正しさと多項式実行時間の両方が厳密に証明されています。^[3]各章には演習が含まれており、本の最後のセクションでは、いくつかの演習の解答が提供されています。^{[1] [2]}別の付録では、数論の未解決の問題をいくつか挙げています。^[3]

主に学部数学の学生を対象としていますが、「初心者のための素数テスト」は背景知識をほとんど必要とせず、中等学校の上級生にも適している可能性があります。^{[2] [3]}これは、このレベルの学生を対象に、著者がドイツで運営している夏期プログラムに基づいており、学生に最新の研究を紹介することを目的としています。^[4]

査読者のロビン・チャップマンとジェフリー・エーメは、この本の全体的な内容はおそらく学部生の数論コースのメイン教科書として使うには軽すぎるが、そのようなコースや暗号学のコースの補足としては良いかもしれないことに同意している。^{[3] [4]}査読者のフレデリック・グリーンは、この本を数学研究全般への良い入門書として推奨しており、素数判定のクイックリファレンスとして研究者が使用することを提案している。^[5]