Euclidean algorithm - runtime in specific case

Question

I'm going to solving many times this specific equations:

$$2^{x+y} \cdot c - a^{y} \cdot z = 1$$

in which $$a$$ can be equal to: $$-7,-5,-3,-1,1,3,5,7.$$ And $$x+y$$ will be equal to $$128.$$ It has to be done with euclidean algorithm, but how many step it requires in average in this specific case?

I know that euclidean algorithm requires at most $$5\log_{10}b$$ steps (Wikipedia), where b is the smaller number, but in this case we don't know which number will be smaller, $$2^{x+y}$$ or $$a^{y}.$$ That's why I have a problem with this case.

Answer 1

Your problem amounts to solving $2^{128} c - a^y z = 1$. I assume you are given $a,y$ and must find $c,z$ that satisfy the equation.

I suggest you first solve $$a^y z \equiv 1 \pmod{2^{128}}.$$ This has as solution $$z \equiv (a^{-1})^y \pmod{2^{128}},$$ so you can find a solution for $z$ by computing the inverse of $a$ modulo $2^{128}$ (using one invocation of the Euclidean algorithm; or by a Hensel lifting method if you prefer), and raising it to the $y$th power using a fast exponentiation algorithm. Then, compute $c = (1 + a^y z)/2^{128}$.