5
$\begingroup$

I am not sure if I should ask this question here or somewhere else. In fact, I initially asked my question here at mathoverflow.net but it was marked as off-topic

Background: I was searching through random mathematics paper that are related to cryptography and I came across this paper (page 3). I just read the abstract and algorithm itself, I don't understand Chinese. It offers new method to find a Modular inverses. It has some interesting properties that I observed:

  1. during each step iteration of the loop: $x_{11} * x_{22} + x_{12} * x_{21} = m$ which is good to validate the result during each iteration
  2. algorithm terminates in even number of steps for some unknown reason

In abstract section, author says this method was invented by this mathematicians.

My question is, why does this algorithm always terminate in aeven number of steps (or number of iterations of the loop is always even)?

Algorithm to calculate: $a^{-1} (\bmod m)$:

$\text{xgcd}(a, m):$

$\quad x_{11} \leftarrow 1, x_{21} \leftarrow 0, x_{12} \leftarrow a, x_{22} \leftarrow m$

$\quad \text{While }(x_{12} > 1) \text{ do}$

$\quad \quad \text{If }(x_{22} > x_{12}) \text{ then}$

$\quad\quad\quad\quad q \leftarrow \Big\lfloor\frac{x_{22} - 1}{x_{12}}\Big\rfloor$

$\quad\quad\quad\quad r \leftarrow x_{22} - q ~x_{12}$

$\quad\quad\quad\quad \begin{pmatrix}x_{11} & x_{12}\\x_{21} & x_{22}\end{pmatrix} \leftarrow \begin{pmatrix}x_{11} & x_{12}\\q~x_{11} + x_{21} & r\end{pmatrix} $

$\quad\quad \text{If }(x_{12} > x_{22}) \text{ then}$

$\quad\quad\quad\quad q \leftarrow \Big\lfloor\frac{x_{12} - 1}{x_{22}}\Big\rfloor$

$\quad\quad\quad\quad r \leftarrow x_{12} - q~x_{22}$

$\quad\quad\quad\quad \begin{pmatrix}x_{11} & x_{12}\\x_{21} & x_{22}\end{pmatrix} \leftarrow \begin{pmatrix}q~x_{21} + x_{11} & r\\x_{21} & x_{22}\end{pmatrix}$

$\quad \text{Return } x_{11}$

$\endgroup$
4
$\begingroup$

You can replace:

$$ ~~q \leftarrow \Big\lfloor\frac{a - 1}{b}\Big\rfloor $$ $$ r \leftarrow a - q ~b $$

By $q, r \leftarrow \text{divmod}(a, ~ b)$

Algorithm terminates in even number of steps for some unknown reason

Those matrices assignments seem to be a fancy way of writing:

$$ \gcd(m_0, \color{blue}{a_0}) = \gcd(a_0, \color{red}{m_0 \pmod{a_0}}) = \gcd(\color{red}{m_1}, \color{blue}{\underbrace{a_0 \pmod{m_1}}_{a_1}}) = \dots = \gcd(m_n, 1)$$

So $a_i$ decreases every $2$ iterations, and $\gcd$ stops when $a_n = 1$.

Of course, you're not interested in computing the $\gcd$ per see, since you already know it's $1$, but finding the integers such that $Xm + Ya = gcd(m, a) = 1$.

$\endgroup$
  • $\begingroup$ So, I get this is not a "new" algorithm, but rephrasing the one that is usually attributed to Euclid? (Ah: wikipedia mentions the same name as linked in the question) $\endgroup$ – Hendrik Jan Dec 12 '16 at 23:42
  • $\begingroup$ @HendrikJan, I don't get what you're asking... (sometimes my English fails me). But OP's algorithm is finding the modular inverse of $a \mod{m}$, which can be computed using the Extended Euclidean Algorithm to solve $ax + by = \gcd(a,b)$, but I'm not sure who came up with it first. $\endgroup$ – Aristu Dec 13 '16 at 0:44
  • $\begingroup$ According to wikipedia Euclid's algorithm was probably known before Euclid (300BC) and Qin Jiushao is around 1200. I was just asking for an explicit confirmation that these algorithms were similar. But I think you answered that. $\endgroup$ – Hendrik Jan Dec 13 '16 at 15:51
2
$\begingroup$

Assuming you replace that second if with else if, the explanation of an even number of iterations is simple; you are repeatedly computing remainders, so each iteration swaps which of $x_{12}$ and $x_{22}$ is bigger. Each iteration alternately decreases $x_{12}$ or $x_{22}$ starting with $x_{22}$. Since the loop ends after decreasing $x_{12}$, you must go through an even number of iterations.

$\endgroup$

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.