News for hackers. Stuff that matters.

A comment on Mystery Math Whiz and Novelist Advance Permutation Problem. Parent comment

Re:Mystery Math Whiz and Novelist Advance Permutation Problem by chupasaurus on Tuesday November 06, 2018 @06:38AM (#18390073)
RSA algorithm is based upon factorization, reverse problem for which is in NP. If a solution's difficulty is a low degree polinom (3 or lower, but I might be wrong) it could be used to get private keys from public ones in a matter of days.
[ Parent | on HN ]
Re:Mystery Math Whiz and Novelist Advance Permutation Problem by nabla9 on Tuesday November 06, 2018 @08:22AM (#18390706)
The proof itself would not give factorization algorithm.

Even if P = NP, prime factorization can be very time consuming to solve. The prime factorization problem is in the NP class, but we don't know if it is NP-hard.

[ Parent | on HN ]
Re:Mystery Math Whiz and Novelist Advance Permutation Problem by raverbashing on Tuesday November 06, 2018 @09:50AM (#18391436)
Factorization is not NP, it's "easier"
[ Parent | on HN ]
Re:Mystery Math Whiz and Novelist Advance Permutation Problem by chupasaurus on Wednesday November 07, 2018 @03:38AM (#18397832)
It's definitely in the class, but it's undecided which subclass it belongs to.
[ Parent | on HN ]