# Euclidean algorithm - runtime in specific case

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.

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}$$.
• Which method is faster? One invocation of the Euclidean algorithm or Hensel lifting method (I don't know this method)? I also don't understand how to solve equation like this: $$z \equiv (a^{-1})^y \pmod{2^{128}}$$ How to use one invocation of the Euclidean algorithm to find $z$? – Tom Feb 5 '20 at 14:53
• Ok, probably I understand how to solve this: $$z \equiv (a^{-1})^y \pmod{2^{128}}$$ For example if we have: $$3^{19} \cdot z \equiv 1 \pmod{2^{10}}$$ First we can solve: $$3 \cdot r \equiv 1 \pmod{2^{10}}$$ $$r=683$$ And then: $$z = 683^{19} \pmod{2^{10}} = 83$$ – Tom Feb 5 '20 at 20:17