Correctness and bit cost of the modular inverse recurrence

First handle $c=0$: since $n\ge 2$, $\gcd (n,0)=n\mathrm{\ne }1$, so the algorithm returns NO_INVERSE, correctly. Suppose $c>0$. The initialized coefficients satisfy $r_{-1}\equiv s_{-1}c(\mathrm{m}\mathrm{o}\mathrm{d}n)$ and $r_0=c\equiv s_{0}c(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

If $r_{i-1}\equiv s_{i-1}c$ and $r_i\equiv s_{i}c$ modulo $n$, the division identity and update give

Replacing a coefficient by its least residue preserves this congruence. Induction proves $r_i\equiv s_{i}c(\mathrm{m}\mathrm{o}\mathrm{d}n)$ for every generated index.

By [F1], each positive remainder is strictly smaller than its predecessor, so the divisions terminate. By [F2], the last nonzero remainder is $d=\gcd (n,c)$. The algorithm returns an $s_i$ exactly when $d=1$; by [F3], this is exactly the unit case. If it returns, the invariant at the last nonzero index says $s_{i}c\equiv d=1(\mathrm{m}\mathrm{o}\mathrm{d}n)$, hence the returned least residue is an inverse. If $d\mathrm{\ne }1$, [F3] says no inverse exists, so NO_INVERSE is correct.

Let $B=\lceil {\log }_2(n+1)\rceil$. There are $O(B)$ divisions: in two consecutive Euclidean divisions the remainder falls below half its earlier positive value. Indeed, if $r_{i+1}\le r_i\mathrm{/}2$ this already holds; otherwise $r_{i+1}>r_i\mathrm{/}2$, so the next quotient is $1$ and $r_{i+2}=r_i-r_{i+1}<r_i\mathrm{/}2$. Thus at most two steps halve a positive remainder, which has at most $B$ bits.

Every quotient, remainder, and coefficient residue has $O(B)$ bits; each Euclidean quotient is found by binary long division in $O(B^2)$ bit operations. Each product $a_i{s}_i$ and reduction modulo $n$ also costs $O(B^2)$ by schoolbook multiplication and division. With $O(B)$ iterations from step 3.1, the total is $O(B^3)$.