WCt377N61X https://blog.hatena.ne.jp/WCt377N61X/ Legalscapeテックブログ https://tech.legalscape.co.jp/ その他 Legalscape のしろくまです。 今日は確率的素数判定法について話したいと思います。 フェルマーの小定理 が素数のとき と互いに素な について が成り立ちます 確率的素数判定法: フェルマーテスト フェルマーの小定理の対偶を取ると、次のようなことが言えます。 と互いに素な について、 ならば、n は合成数である。 このことを利用した素数判定法をフェルマーテストといいます。 このような を が合成数である「証拠」と言うことにします。 実際に Python でフェルマーテストを実行してみると # 91 = 13*7 print([pow(i, 91-1, 91) for i in range… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftech.legalscape.co.jp%2Fentry%2F2026%2F07%2F06%2F165930" title="64bit の素数判定は7回の操作で完了する - Legalscapeテックブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/W/WCt377N61X/20260706/20260706165830.jpg Hatena Blog https://hatena.blog 2026-07-06 16:59:30 rich https://tech.legalscape.co.jp/entry/2026/07/06/165930 1.0 100%