nが素数であるかどうかの判定

素数判定の勉強をしています。

次の文の内容が成立する理由がわかりませんでした。
-----内容-----
n-1 = 2^(t-1) * m としたとき
とある整数a　(aは2以上n-2以下)において

もし
a^{(2^j)*m} ≡ 1 mod n かつ
a^［{(2^(j-1)}*m] ≠　±1 mod n
ならば　　a^［{(2^(j-1)}*m] -1 と　nの自明でない最大公約数がみつかりnは素数ではないと判断できる。

(ここで、jは1以上t-1以下の自然数。また記号「≠」を「not 合同」の意味で使用しています。)
-----終了-----


これはなぜなのでしょうか？　なぜ公約数が見つかるのでしょうか？
アドバイスよろしくお願いします。

No.1 ベストアンサー 回答者： proto 回答日時： 2008/05/14 18:59

整数nの素数判定にはフェールマーの小定理を応用したもう少し簡単なフェールマーテストがありますよね。

a<nに対して
　　a^(n-1)≠1 (mod n)ならばnは合成数
というものです。

ところがこの判定法はnが素数である必要条件を与えるだけで、十分条件を与えるものではありません。
現にn以下の全てのaに対してa^(n-1)≡1 (mod n)であるにもかかわらず素数でないような数が存在し、カーマイケル数(擬素数)と呼ばれています。
小さい方から挙げると561,1105,1729,...です。


このようなカーマイケル数にも対応して合成数だと判定する判定法としてラビン・ミラー(Rabin-Miler)判定法があります。
質問者様が書かれているのはまさにその判定法のように思います。
この判定法の証明は、webなどで検索して貰えれば見つかると思います。
しかしラビン・ミラー判定法にたいしても、合成数であるにも関わらす判定を通過する数として強擬素数が存在します。

また『なぜ公約数が見つかるのでしょうか？』と書かれていますが、フェールマーテストにしてもラビン・ミラーテストにしてもこれらの方法で具体的な約数がわかるわけではありません。
だからこそ「"自明でない"最大公約数がみつかり」と書かれています。
約数があることはわかるんだけど顔までは見えないという状態です。
これらのテストは、nが素数である必要条件を満たさないために合成数であると判定するだけで、具体的な約数を見つけるのには全く役に立ちません。

No.2 回答者： Tacosan 回答日時： 2008/05/14 19:08

いろいろな考え方はあると思うけど, 「p が素数なら ab ≡ 0 → a ≡ 0 または b ≡ 0」だから, x^2 ≡ 1 (mod n) かつ x ≠ ±1 (mod n) であるような x が見付かれば n は合成数です. しかも x-1 や x+1 は n と自明でない公約数を持つことも簡単にわかります (x-1 が n と自明でない公約数を持たないなら x+1 が n の倍数にならないといけないので).

で, これで合成数だとわかれば「約数」は見付かりますね＞#1. 「素因数」が見付かるとは限りませんが.