アカウント名:
パスワード:
もし元の素数が素数であることが (たとえばパ
一方 Primarity in P の論文を読むと、今までの積み重ねから とうとうできたかという感想を持ちました。 超天才というよりは日頃の鍛錬の成果なのかなぁと思いました。
sakamoto さんの記事の丸かっこ内に書いてあるとおり、「誤る可能性はあるけど高速なアルゴリズム」を使ってたのですよ。
# もちろん確定的なテストも使ってますが、あまりに遅いものは使ってないと思います。 # トリビアですが、確率的な素数テストを通過してしまう合成数を「擬素数」と呼びます。
決定性の多項式時間で判定できるのは、そんなのは紀元前から出来ていますよ。ただ遅かっただけで。
またこういう嘘を平気で書くもんなあ。モデレートダウンもされてないし。元のコメントでリンクされている論文の冒頭にもはっきりと
In 1983, Adleman, Pomerance, and Rumely achieved a major breakthrough by giving a deterministic algorithm for primality that runs in (log n)O(log log log n) time (all the previous deterministic algorithms required expon
決定性の多項式時間で判定できるのは、そんなのは紀元前から出来ていますよ。ただ遅かっただけで。 またこういう嘘を平気で書くもんなあ。
またこういう嘘を平気で書くもんなあ。
そう考えれば、x=2^n-1が素数かどうか判定するのにO(2^n)かかるアルゴリズムも、多項式時間アルゴリズムということになってしまいますからね。
すいません、 (log n)O(log log log n)って O(log n) にはならないのですか?
そんなのは紀元前から出来ていますよ を肯定しているのでしょうか???
たとえば、3からsqrt(n)までのすべての奇数で割ってみるという 一番素朴なアルゴリズムの計算量は、割り算が定数時間としてO(n^0.5)となります。ここで問題のサイズとしてnそのものをとれば、この素朴アルゴリズムは立派な多項式時間アルゴリズムと解釈できるわけです。
しかし常識的にはln nをサイズとして考えるべきなので、そうすると計算量はO(2^((ln n)/2))となり、桁数の指数関数となります。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
※ただしPHPを除く -- あるAdmin
素人の質問 (スコア:0)
もし元の素数が素数であることが (たとえばパ
Re:素人の質問 (スコア:2, 参考になる)
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人の質問 (スコア:1)
逆は証明されてなかったような。
すなわち、何らかの画期的な方法を使えば素因数分解せずとも
RSAを解ける可能性がないことは否定されてなかったような。
# まぁこれもあまたの数学者が挑戦してきたことだと思うので
# 超天才でもない限りちょっとした気合や根性ではできないと思うけど。
Re:素人の質問 (スコア:1)
一方 Primarity in P の論文を読むと、今までの積み重ねから とうとうできたかという感想を持ちました。 超天才というよりは日頃の鍛錬の成果なのかなぁと思いました。
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人の質問 (スコア:0)
Re:素人の質問 (スコア:1, 興味深い)
sakamoto さんの記事の丸かっこ内に書いてあるとおり、「誤る可能性はあるけど高速なアルゴリズム」を使ってたのですよ。
# もちろん確定的なテストも使ってますが、あまりに遅いものは使ってないと思います。
# トリビアですが、確率的な素数テストを通過してしまう合成数を「擬素数」と呼びます。
Re:素人の質問 (スコア:0)
Re:素人の質問 (スコア:0)
またこういう嘘を平気で書くもんなあ。モデレートダウンもされてないし。元のコメントでリンクされている論文の冒頭にもはっきりと
Re:素人の質問 (スコア:1)
そう考えれば、x=2^n-1が素数かどうか判定するのにO(2^n)かかるアルゴリズムも、多項式時間アルゴリズムということになってしまいますからね。
Re:素人の質問 (スコア:0)
すいません、 (log n)O(log log log n)って O(log n) にはならないのですか?
O(log n)なら桁数って思えるのですが。
あと、
> そう考えれば、x=2^n-1が素数かどうか判定するのにO(2^n)かかるアルゴリズムも、
> 多項式時間アルゴリズムということになってしまいますからね。
と書いているということは、
> 決定性の多項式時間で判定できるのは、そんなのは紀元前から出来ていますよ
を肯定しているのでしょうか???
例えば通常の10進数で考えて(2進数にしても基本的には
Re:素人の質問 (スコア:1)
たとえば、3からsqrt(n)までのすべての奇数で割ってみるという 一番素朴なアルゴリズムの計算量は、割り算が定数時間としてO(n^0.5)となります。ここで問題のサイズとしてnそのものをとれば、この素朴アルゴリズムは立派な多項式時間アルゴリズムと解釈できるわけです。
しかし常識的にはln nをサイズとして考えるべきなので、そうすると計算量はO(2^((ln n)/2))となり、桁数の指数関数となります。
Re:素人の質問 (スコア:0)
正しいのは(log n)^O(log log log n)です。だからO(log n)にはなりません。準指数関数時間であって多項式時間ではありません。
2002年?1983年?どっち (スコア:0)
ちょっとお願い (スコア:0)
モデレータのほとんどは専門知識を持っていませんし、
英語に堪能なわけでもありません。
大多数は一般的な人たちです。
あなたのような専門家にコメントの形で
補完していただければ助かります。
また、わたしも自分の専門分野については
補完するつもりです。