Miller-Rabin 素数判定と Pollard-Rho 素因数分解
Miller-Rabin 素数判定
Miller-Rabin 法は、フェルマーの小定理と二次探査定理を組み合わせた確率的素数判定アルゴリズムです。以下の手順で動作します。
偶数および 0, 1, 2 は事前に判定します。
判定対象の奇数 n に対し、n - 1 = 2s × d（d は奇数）と分解します。
小さな素数 a を基底として選び、ad mod n を計算し、その後 s 回の平方と二次探査を行います。
最 ...
5月28日 04:02 投稿