素数判定の勉強をしています。
次の文の内容が成立する理由がわかりませんでした。
-----内容-----
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ベストアンサー
- 回答日時:
整数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
- 回答日時:
いろいろな考え方はあると思うけど, 「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. 「素因数」が見付かるとは限りませんが.
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 大学数学 「条件:t進表現において、何乗しても右から2桁が変わらない2桁の自然数が存在する。」 上記 7 2023/06/28 22:25
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- 数学 大学数学 代数学の問題です。 もしわかる方がいらっしゃいましたらぜひ教えてください。 宜しくお願いし 1 2022/11/30 13:34
- Ruby 初心者プログラミング 3 2022/10/12 11:31
- 計算機科学 ASCIIの 誤り 1 2022/11/09 02:03
- 数学 ヒストスプライン平滑化をする際の節点の決め方ついて教えてください。 9 2022/08/08 16:17
- 数学 ユークリッドの互除法、合同式の問題について 1 2022/05/08 11:49
- 数学 離散フーリエ逆変換が周波数分割数をNにできる理由について 4 2022/09/18 12:56
- 国家公務員・地方公務員 公務員試験の数的処理で苦戦しています。 1 2023/01/30 08:56
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
演算子法なににつかう
-
AとBはn次正方行列とする。 積A...
-
マクローリンの定理でのθが含ま...
-
【遊びのピタゴラスイッチはな...
-
lim[x→+∞](x^n/e^x)=0 の証明
-
2^220を221で割った時の余りを...
-
至上最難問の数学がとけた
-
代数学の問題
-
オイラーの多面体定理の拡張
-
三角形の3辺の長さの性質の証明
-
複素平面で代数方程式の解を含...
-
入試で定理の名前を忘れてしま...
-
x^100を(x+1)^2で割ったときの...
-
量子化定理とは?
-
合同方程式
-
e^x > Σ[k=0→n](x^k/k !) の証...
-
陰関数の定理がわかりません
-
可換群で同型,や非同型の判定の...
-
複素関数と実関数のテーラー展...
-
大学受験数学で「中国剰余定理...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
過去に 「ii) f(z)=1/(z^2-1) r...
-
【遊びのピタゴラスイッチはな...
-
直角三角形じゃないのに三平方...
-
大学の記述入試で外積は使えま...
-
lim[x→+∞](x^n/e^x)=0 の証明
-
定理と法則の違い
-
至上最難問の数学がとけた
-
実数の整列化について
-
十分性の確認について
-
AとBはn次正方行列とする。 積A...
-
ほうべき(方巾)の定理について
-
ファルコンの定理は解かれまし...
-
パップスギュルダンの定理について
-
オイラーの多面体定理の拡張
-
微分形式,微分幾何学の参考書
-
ディリクレ指標について( mod=5...
-
x^100を(x+1)^2で割ったときの...
-
nを整数とする。このとき、n^2...
-
大学数学 解答
-
4.6.8で割るとあまりはそれぞれ...
おすすめ情報