Euclidean algorithm - runtime in specific 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}$.