Complexity of the inverse modulo a composite number Supposing $M$ is a composite number and supposing $a$ is an integer such that $a^{-1}\mod M$ exists,  can we compute $a^{-1} \bmod M$ by using $O(\log^{b}(M))$ ring operations in the RAM model, where $b&gt;0$ and is some fixed number?

I'm interested in the case where $a$ and $M$ are of similar sizes.

When we apply the Euclidean algorithm, we compute the remainder of an integer divided by another. It is not clear to me if this can be done in unit time in the RAM model using only ring operations.
Let us call the function which takes $(a,b)$ to $r$ such that $a = bq + r$ with $r &lt; b$ (and all of $a,b,q,r$ nonnegative integers) the Remainder function. This function cannot be computed at all using only ring operations in the integers: any function that can be computed using only ring operations is a polynomial of its inputs, so if the Remainder function could be computed using only ring operations, it would follow that $Remainder(a,b) = f(a,b)$ for some integer polynomial $f$. For any fixed $b &gt; 1$, the function $g(x) = f(x,b)$ would then be a univariate polynomial. Now, $g(b+1) = 1$, so $g(x)$ is not identically zero; but $g(x) = 0$ whenever $b | x$, so $g(x)$ has infinitely many zeroes, a contradiction.

However, if you allow $&lt;$ in addition to ring operations, then the Remainder function can be computed in polynomially many steps (in the number of bits of the input) as follows: start with $q=1$ and check if $qb &gt; a$ (if so, then the remainder is just $a$). Otherwise, multiply $q$ by $2$ repeatedly until $qb &gt; a$. Then do binary search on $q$ to find $q$ such that $qb \leq a$ and $(q+1)b &gt; a$, and finally output $a - bq$. This takes $O(\log (a/b))$ ring operations and comparisons; on most standard Boolean models of computation each such operation can be done in nearly $O(\log a)$ time.