[dmdox]

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:

https://gdl.space/obiyukevit.py

N is 256-bit a sample number.