In responding to 


[Fast computation of multiplicative inverse modulo q](https://mathoverflow.net/questions/40997/fast-computation-of-multiplicative-inverse-modulo-q/41631#41631)


I mentioned an algorithm for computing the inverse of $a \mod p$ different from the extended Euclidean algorithm, hoping that someone could tell me how its speed stacks up against other algorithms. Since no one did, I'm asking directly if someone can tell me.


To compute the inverse of a modulo p, you can run the Euclidean algorithm starting with $p^2$ and $ap+1$, comparing the size of each remainder with $p$. The first remainder less than $p$ that appears will be an inverse for $a \mod p$. 


This will always take either the same number of steps to reach the inverse as it takes to reach $\gcd(a,p)=1$ using the Euclidean algorithm with $a$ and $p$, or else one additional step, depending on whether the least positive residue of an inverse of $a$ is greater than $p/2$ or less than $p/2$.
Thus, it requires approximately the same number of computations as the first half of the extended Euclidean algorithm (albeit with bigger numbers initially), excepting an extra comparison with $p$ at each step.


Question: How does the speed of this algorithm compare to others?


Aside: Pedagogically, this is nice since the second half of the extended Euclidean algorithm is the one my students tend to mess up. However, assuming our ultimate goal is for students to understand why they're doing what they're doing, perhaps the extended Euclidean algorithm is preferable.



Computation of inverses modulo p followup
Here is a tidy way to solve $ax+by=gcd(a,b)$. Start with the matrix
$$\left(\begin{array}{ccc}
 1&0&a\\
 0&1&b\\
 \end{array}\right)
$$
Suppose $a\ge b$. Then replace row 1 by row 1 minus $t$ times row 2, where $t=\lfloor a/b\rfloor$. Repeat this operation until the last entry in one of the two rows is zero. If the other row is $x,y,d$ then $ax+by=d$ and $d=gcd(a,b)$. This is very simple to program, and avoids the back-substitutions that students find confusing. 


Most of the speedups of the Euclidean Algorithm described in Knuth's Art of Computer Programming v2 work here also.


