質問: 素因数分解について ものすごく大きな素数二つを掛け合わせた数を素因数分解することは難しい、というようなことを本で読みました。 これって暗号を作ることにも利用されているみたいですが、どうしてこの数を素因数分解することが難しいのでしょうか?
回答: > で、素因数分解はnp完全なんです。 なぜここだけ間違いを? 素因数分解は回答例が与えられた場合、多項式時間でその回答が正しいか確認できるが、回答を多項式時間で得るアルゴリズムは存在を知られていない。 素因数分解はnp問題ではあるが、np完全であるとは証明されていないようです