アカウント名:
パスワード:
もし元の素数が素数であることが (たとえばパ
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
アレゲは一日にしてならず -- アレゲ研究家
素人の質問 (スコア:0)
もし元の素数が素数であることが (たとえばパ
素人な答え (スコア:0)
「素因数分解」は
「素数かどうか判定する」ことに比べてずっと大変で、
「素因数分解」は桁が2倍程度に増えるだけで、非常に時間がかかる。
ということから、暗号が成立する
(大きな2つの素数を見つけることはできるが、
そのような数をかけたものはちょっとやそっとじゃ
因数分解できない)
のではないかと。
何倍? (スコア:0)
> 「素因数分解」は
> 「素数かどうか判定する」ことに比べてずっと大変で、
> 「素因数分解」は桁が2倍程度に増えるだけで、非常に時間がかかる。
桁が2倍に増えたら、処理時間は何倍になるのですか?
「桁が2倍に増えた
Re:何倍? (スコア:0)
「この非常に時間ががかるというのは、これくらいなんですよ」
とあなたが補足すればいいのに。
答え (スコア:0)
約 e^(1.93(log 2*x)^(1/3)(log (log 2*x))^(2/3))/e^(1.93(log x)^(1/3)(log (log x))^(2/3)) 倍(x:元の数の桁数)
ぐらい(間違ってるかも)ですが、この値って、説明にほんとに必要?
Re:答え (スコア:0)
e^(1.93(log 1024)^(1/3)(log (log 1024))^(2/3)) = 303.8
e^(1.93(log 2048)^(1/3)(log (log 2048))^(2/3)) = 442.7
1024桁を倍の2048桁にしても、高々1.5倍にしかなんないよ。いくら桁を増やしても、あっと言う間に素因数分解できそうだね。
Re:答え (スコア:0)
Re:答え (スコア:0)
その説明によって「非常に増える」が間違いであることが分かった