3 ms·
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.
by nokita 5y ago
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.
- dmdox 5y agoThis 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: https://gdl.space/obiyukevit.py https://gdl.space/obiyukevit.py N is 256-bit a sample number.