0
$\begingroup$

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.

Improve this question
$\endgroup$
1
$\begingroup$

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}$.

Improve this answer
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Tom Feb 5 '20 at 14:53
  • $\begingroup$ 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$$ $\endgroup$ – Tom Feb 5 '20 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.