Factoring composite numbers into nearly equal factors

Re:Factoring composite numbers into nearly equal factors by nokita on Monday February 07, 2022 @06:37PM (#30253089)

I think it needs to be poly in the number of bits, not just the number, otherwise factoring would be poly, and it isn't.

[ Parent | on HN ]

Re:Factoring composite numbers into nearly equal factors by dmdox on Monday February 07, 2022 @09:23PM (#30254228)

This is polynomial time in the number of bits.

I did make one mistake. I forgot to mention the half-integer case for x and y, which requires some additional logic. I implemented it fully python:

N is 256-bit a sample number.

[ Parent | on HN ]