フェルマーの小定理を使った素数テストを追う - Line 1: Error: Invalid Blog('by Esehara' )

今日のラーメン 稲荷屋 概要 素数を検査する方法には、いわゆる「ふるい法」と呼ばれる方法を使った決定的な方法と、「だいだいこのような式に該当するならば、素数だろう」といった推測に基づく、確率的な方法がある。確率的な方法の一つに、「フェルマーの小定理」を利用したテスト方法がある。しかし、これは「カールマイケル数」と呼ばれる合成数が引っかかる。 はじめに 暫らくの間、『はじめての数論』を読みながら、素数判定について調べていた。そして、素数チェックの方法として有名な「フェルマーテスト」が紹介されていた。そういえば、この「フェルマーテスト」について調べたことなかったな、と思ったので、改めて実装しながら理解したことをメモしたいと思う。 フェルマーの小定理 まず、「フェルマーテスト」の方法は、「フェルマーの小定理」から作られたものである。 「フェルマーの小定理」は次のようになる。素数になる任意の数(こ

[sexmachinegunmu]

フェルマーの小定理を使った素数テストを追う - Line 1: Error: Invalid Blog('by Esehara' )