Factoring may be easier than we think (2016)

Re:Factoring may be easier than we think (2016) by danbruc on Sunday June 30, 2019 @01:14PM (#20319223)

I have thought about this before but with even higher stakes - finding a polynomial time algorithm for a NP-hard problem - because this would not only affect encryption algorithms based on factoring.

[ Parent | on HN ]

Re:Factoring may be easier than we think (2016) by BubRoss on Sunday June 30, 2019 @01:31PM (#20319340)

For any NP hard problem would be ground breaking, but many individual NP hard problems can be approximated with imperfect but extremely effective methods.

[ Parent | on HN ]

Re:Factoring may be easier than we think (2016) by danbruc on Sunday June 30, 2019 @02:11PM (#20319545)

With an exact algorithm you could use, for example, 3-SAT to attack most if not all classical encryption algorithms. The know approximations are obviously not good enough for that, otherwise we would already be in trouble.

[ Parent | on HN ]