フェルマーテストによる素数判定最近の主な更新 2005-11-25 - 細かな修正 2005-11-22 - 第二版 2004-09-12 - 初版 概要 本稿では，確率的素数判定法の一つであるフェルマーテストについて述べる． 1章ではフェルマーテストの理論的基礎であるフェルマーの小定理を導く．2章 では，フェルマーテストの Python による実装を与える．3章では，フェルマー テストによる素数判定が誤る原因となる，擬素数の存在について述べる． 1 フェルマーの小定理 フェルマーテストの準備として，以下ではフェルマーの小定理とよばれる定理 を導く．まず，次の補題が成り立つ． 補題 1.1 素数 p と 自然数 r （0 < r < p）に対し， pCr = p! / (r!(p-r)!) ≡ 0 (mod p) が成り立つ． 証明 p! は p で割りきれる．一方，r!(p-r)! は p よりも小さい自然 数の，複
試行除算による素数判定
