- 178 名前：１３２人目の素数さん [02/09/05 22:26]
- 「時間が本質的に違わない」の意味を、
素因数計数問題が易しければ、素因数分解問題も易しい
とするのであれば、本質的に違いはある、と思うに一票
素因数の個数を教えてもらっても、そんなに素因数分解
問題が易しくなった気がしない。
たとえば、RSA とかで使われている
n = p q (p, q: 素数)
は、はじめから素因数の個数が2個とわかっているけど、
効率的に素因数分解せよ、と言われればどうして良いか
わからん。
もちろん、素因数分解問題がそもそも易しいのであれば、
(そうじゃないだろと思ってるが...)両者の時間は
本質的に同じ、ということになるが。
