# Are bijective polynomials of degree $2 \bmod 2^m$ efficiently inverted?

Take a bijective polynomial of degree $$2 \bmod 2^{64}$$ like:

$$m = (n(n+1)/2)\ \bmod 2^{64}$$

It is bijective and can trivially be inverted for numbers up to $$2^{32}$$ by calculating $$\lfloor\sqrt{2m}\rfloor$$ . For all other numbers the inversion is not that trivial but I have the feeling it could be done without brute force.

• Welcome to Cryptography. Is this homework? – kelalaka Feb 12 at 17:49
• @kelalaka No, cryptography is a hobby, hashing part of my research, but I'm missing essential mathematical education, I was hoping someone could point me in the right direction. I legitimately do not know if it is efficiently inverted, if not it could be a novel one-way function. – Wolfgang Brehm Feb 12 at 18:07
• It can be efficiently inverted - does that answer your question? – poncho Feb 12 at 18:09
• @poncho How do you know it can be efficiently inverted? – Wolfgang Brehm Feb 12 at 18:11
• Because I figured out how to invert it. It's not that hard, you can figure it out as well (it's a technique that comes in useful time to time). Hint: the lower $i$ bits of $m$ depend solely on the lower $i+1$ bits of $n$ ; any other bits of $n$ have no effect... – poncho Feb 12 at 19:41

As pointed out in the comments by poncho m only depends on the lower i+1 bits of n . Therefore n can be reconstructed by testing the four possible states of the the two most significant bits at a time, starting with the first ones, then choosing the combination that produces the correct binary suffix to expand iteratively.