I need to calculate $x^{-1} \mod p$ where $p$ is even. It is a cryptographic application, so the operation has to be constant time. The problem is that the constant time inversion algorithms I could find (e.g. Bernstein & Yang 1) require $p$ to be odd. There are also constant-time algorithms for inversion $\mod 2^k$ (e.g. 2).
I was thinking that I could decompose $p = q 2^k$ where $q$ is odd, calculate inverses separately modulo $q$ and $2^k$, and then recover them as I would recover an RNS-represented number, but the recovery formula (if $x = r_1 \mod q_1 $ and $x = r_2 \mod q_2$, then $x = (q_1 + q_2)^{-1} (r_1 q_2 + r_2 q_1) \mod q_1 q_2$) requires calculating an inverse itself.
1 also mentions that "One can further generalize to allow even [p], by first finding the number of shared powers of 2 in [x] and [p] and then reducing to the odd case." (notation replaced to match this question) but I can't figure out how to do that. Also the phrasing is kind of strange, since if $x$ and $p$ have shared powers of 2, there is no inverse.
Does anyone have any ideas how to proceed?
Best Answer
For the sake of closure, posting the comment by @BillDubuque as an answer.
So my problem was that the RNS recovery formula I described in my question:
$$x = (q_1 + q_2)^{-1} (r_1 q_2 + r_2 q_1) \mod q_1 q_2$$
created a vicious cycle since I didn't know how to calculate the inverse $\mod q_1 q_2$ in the first place. But in the question Bill linked, another formula was used:
$$x = r_1 + q_1 ((r_2 - r_1) q_1^{-1} \mod q_2) \mod q_1 q_2$$
Which makes it much easier since for me $q_2 = 2^k$, for which constant-time modulo operations are already implemented (and are quite simple). So to calculate the initial inverse in my question, I can decompose $x$ into an RNS, calculate inverses modulo $q_1$ and $q_2$ separately, and then merge them with the formula above. For all of these operations there are existing constant-time implementations.