3
$\begingroup$

I am not sure if I should ask this question here or somewhere else.

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.

I have two unrelated questions:

  1. why this algorithm always terminates in even number of steps (or number of iterations of the loop is always even)
  2. was this algorithm invented before extended-euclidean algorithm that we use today

Algorithm: Python and SageMath implementations.

enter image description here

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Please remove the "modular-forms" tag. Modular forms have very little to do with modular arithmetic. $\endgroup$
    – Joe Silverman
    Commented Dec 10, 2016 at 19:12
  • $\begingroup$ Cross-posted to CS: cs.stackexchange.com/questions/67245/… Please do not cross-post -- it can and does lead to duplication of effort, which wastes people's time. $\endgroup$
    – Todd Trimble
    Commented Dec 14, 2016 at 12:37

1 Answer 1

Reset to default
2
$\begingroup$

As far as I can tell, this is a recasting of the usual extended GCD algorithm, so the first question is moot (and I am quite sure the extended GCD thing goes back to the ancients - perhaps to Euclid). No comment about even number of steps.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .