In responding to

Fast computation of multiplicative inverse modulo q

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.

couldbe implemented in quasi-linear time. But this comes at the cost of making the algorithm much more complicated (which may be a pedagogical flaw or feature, depending on one's point of view), and it will still be slower than just computing the extended gcd. $\endgroup$ – AVS Oct 12 '10 at 18:45