<p>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 <em>at all</em> using <em>only</em> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-12-13T13:37:57.463Z
your argument does not preclude the fact that there could be a polynomial for computing remainder modulo $b$ for number upto some absolute value $A$ and if $log_b A\sim \log_2 b$, we may get quick remaindering operations using ring operations?
Turbo
CC BY-SA 3.0
2014-12-14T06:10:23.347Z
Of course there is such a polynomial: for any given upper bound A, you are then only asking for finitely many values of the polynomial (namely, that it agrees with $Rem(x,b)$ on all integers $|x| \leq A$), so you can find such a polynomial by interpolation. Without further argument, one gets a degree upper bound of $2A$. Since the interpolated points look like a "sawtooth" with peaks and valleys with a period of $b$, the polynomial has at least $A/b$ extreme points in the range $-A \leq x \leq A$, so it must have degree at least $1+A/b$.
Joshua Grochow
CC BY-SA 3.0
2014-12-14T06:11:25.560Z
BTW, the model you are suggesting is very similar to Mulmuley's "algebraic RAM without bit operations," which is essentially nonuniform polynomials, except that the nonuniformtiy can depend both on the number of inputs and on the total bitlength of the inputs.
Joshua Grochow
CC BY-SA 3.0
2014-12-14T20:40:42.470Z
Following up on the last comment: there are even polynomials that will extract the $i$-th bit of any number of size bounded by $A$; so if you want to go with that setting, it really isn't very different from just considering the full Boolean setting. The place where RAMs without bit operations can differ from Boolean algorithms is in parallel complexity (PRAM without bit ops), but that seems to me like a separate question...
Joshua Grochow
CC BY-SA 3.0
2014-12-14T23:03:52.293Z
I am just curious if it could have other applications. AFAIK no one has used remainder polynomials anywhere explicitly.
Turbo
CC BY-SA 3.0
2014-12-14T23:05:57.737Z
If the ith bit extraction can be generalized to subset of bit extractions may be it could be useful in factorial extraction from shamir's technique?
Turbo
CC BY-SA 3.0
2017-04-03T11:49:17.703Z
the degree gap $1+A/b<deg<2A$ is very large in particular when $A=cb$ where $c$ is constant. Is there a better estimate?
Turbo
CC BY-SA 3.0
2017-04-03T15:23:54.777Z
@Turbo: Actually, the lower bound should be something like $1 + (2A/b - 2)$, since both the beginning and end of each interval of the form [kb, k(b+1)-1] are extreme points, so each such interval has *two* extreme points, except that the endpoints of the whole interval [-A,A] need not be extreme points (hence the minus 2). So the actual bound is between $2A/b-1$ and $2A$. Some quick numerical experiments using Lagrange interpolation in sympy ($A \leq 10$, $2 \leq b \leq 10$) suggest that the degree is always exactly 2A. It would be nice if someone could prove this... :)
Joshua Grochow
CC BY-SA 3.0
2017-04-03T18:35:21.320Z
interesting        $  $
Turbo
CC BY-SA 3.0
2017-04-03T19:50:48.507Z
@Turbo: I think degree 2A should be provable by looking at the second derivative (and using the fact that, within an interval $[kb, k(b+1)-1]$, the points to be interpolated lie on a line).
Joshua Grochow
CC BY-SA 3.0
2017-04-03T20:06:28.880Z
thank you but it trying to see if it makes sense at $b\in\{A,A+1,\dots,2A\}$.
Turbo
CC BY-SA 3.0
2017-04-03T23:52:03.280Z
@Turbo: oh, well, I was assuming that rem(x, b) is always nonnegative, and that you're interpolating for all x in [-A, A].
Joshua Grochow
CC BY-SA 3.0
2017-08-20T22:28:36.977Z
@JoshuaGrochow is comparison ($<$,$=$,$>$) in $TC0$?
Turbo
CC BY-SA 3.0
2017-08-21T19:47:53.153Z
@777: Yes. Equality is in $AND \cdot NC^0$. Subtraction is in $AC^0$, and comparison-against-0 is similarly easy (e.g., using two's complement representation, it is in $AND \cdot NC^0$).
Joshua Grochow
CC BY-SA 4.0
2021-12-18T08:18:58.463Z
Is computing $m$ such that $am\equiv1\bmod n$ in $NC^1$ when $a$ is given and $n$ is prime?
Turbo
CC BY-SA 4.0
2021-12-18T08:34:23.687Z
Or in $NC$ at all?
Turbo
CC BY-SA 4.0
2021-12-18T18:58:10.230Z
I think this is open. It's basically the extended Euclidean gcd algorithm, which iirc is a candidate for being intermediate between NC and P-complete.
Joshua Grochow
CC BY-SA 3.0
2014-08-27T03:33:10.807Z
2014-08-27T03:33:10.807Z
Joshua Grochow
<p>If a reverse of a modulo $M$ exists, it means that $\gcd(a,M)=1$, so you can just use the extended Euclidean algorithm to find $x$ and $y$ that satisfy $ax+My=1$. From here $x$ will be the reverse modulo $M$. And the running time of the extended Euclidean algorithm is $O(\log(\max(a, M)))$. Here you have $b=1$.</p>

CC BY-SA 3.0
2014-08-26T20:47:19.923Z
Under what model is this complexity for the extended Euclidean algorithm valid? $M$ may be large (bignum) in the sense that arithmetic operations take $P(\log M)$ time and not $O(1)$.
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2014-08-26T20:34:01.217Z
2014-08-26T21:24:03.617Z
2014-08-26T21:24:03.617Z
Tigran
<p>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?</p>

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

<p>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.</p>

CC BY-SA 3.0
2014-08-21T16:10:01.663Z
Can you be more specific about what you mean by "arithmetic computations"? For example, do you allow the operation of integer-division-with-remainder? If so, then I think this question is too easy for this site: the usual extended Euclidean algorithm works just as well for finding inverses modulo a composite (when they exist) as modulo a prime. If you do not allow such operations, the question may become more interesting...
Joshua Grochow
CC BY-SA 3.0
2014-08-21T17:08:24.030Z
when we apply euclidean algorithm, we compute forms of type $a=bq+r$ where $r<q$? It is not clear to me if this can be done in unit time in RAM model using only ring operations. That is why I posted the question. If it is too elementary please post it to cs.stackexchange.
Turbo
CC BY-SA 3.0
2014-08-21T19:13:37.023Z
It can be, same proof works as for standard Euclidean alg.
domotorp
CC BY-SA 3.0
2014-08-22T21:57:03.010Z
@domotorp: Again, it depends what J.A. means by "only ring operations." If J.A. really means what he writes - *only* ring operations - then I don't think it can be done, since one seems to need either a truncated division or a comparison operator somewhere in there. However, these are both very natural operations to include when the ring is the integers...
Joshua Grochow
CC BY-SA 3.0
2014-08-23T03:10:51.883Z
Could you sketch your comparison operator algorithm and tell its complexity property?
Turbo
CC BY-SA 3.0
2014-08-23T09:34:32.493Z
@Joshua: I agree that it would help to know the exact formulation of the problem.
domotorp
CC BY-SA 3.0
2014-08-24T03:53:43.053Z
@J.A, please edit the question to specify precisely what you mean.  Don't just drop clarifications in the comment thread; comments exist only to help you improve the  question.  We shouldn't have to read the comments to understand exactly what your question is.  In your case, it is not at all in your question what constraints you have in mind (it wasn't even clear to me that you were imposing any constraints about what operations are allowed).  I suggest you add to the question a description of exactly what operations are allowed, and mention why the extended Euclidean algorithm won't work.
D.W.
<algebraic-complexity>
Complexity of the inverse modulo a composite number
Turbo
# Complexity of the inverse modulo a composite number

(Asked by: username_0 on 2014-08-20)

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>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.

**Tags:** algebraic-complexity
> **Comments:**
> **username_1**: Can you be more specific about what you mean by "arithmetic computations"? For example, do you allow the operation of integer-division-with-remainder? If so, then I think this question is too easy for this site: the usual extended Euclidean algorithm works just as well for finding inverses modulo a composite (when they exist) as modulo a prime. If you do not allow such operations, the question may become more interesting...  
> **username_0**: when we apply euclidean algorithm, we compute forms of type $a=bq+r$ where $r<q$? It is not clear to me if this can be done in unit time in RAM model using only ring operations. That is why I posted the question. If it is too elementary please post it to cs.stackexchange.  
> **username_2**: It can be, same proof works as for standard Euclidean alg.  
> **username_1**: @domotorp: Again, it depends what J.A. means by "only ring operations." If J.A. really means what he writes - *only* ring operations - then I don't think it can be done, since one seems to need either a truncated division or a comparison operator somewhere in there. However, these are both very natural operations to include when the ring is the integers...  
> **username_0**: Could you sketch your comparison operator algorithm and tell its complexity property?  
> **username_2**: @Joshua: I agree that it would help to know the exact formulation of the problem.  
> **username_3**: @J.A, please edit the question to specify precisely what you mean.  Don't just drop clarifications in the comment thread; comments exist only to help you improve the  question.  We shouldn't have to read the comments to understand exactly what your question is.  In your case, it is not at all in your question what constraints you have in mind (it wasn't even clear to me that you were imposing any constraints about what operations are allowed).  I suggest you add to the question a description of exactly what operations are allowed, and mention why the extended Euclidean algorithm won't work.  

---

## 2 answers

### Answer by username_1 on 2014-08-27. Score: 5 | Accepted answer

Let us call the function which takes $(a,b)$ to $r$ such that $a = bq + r$ with $r < 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 > 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 $<$ 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 > a$ (if so, then the remainder is just $a$). Otherwise, multiply $q$ by $2$ repeatedly until $qb > a$. Then do binary search on $q$ to find $q$ such that $qb \leq a$ and $(q+1)b > 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.

> **Comments:**
> **username_0**: your argument does not preclude the fact that there could be a polynomial for computing remainder modulo $b$ for number upto some absolute value $A$ and if $log_b A\sim \log_2 b$, we may get quick remaindering operations using ring operations?  
> **username_1**: Of course there is such a polynomial: for any given upper bound A, you are then only asking for finitely many values of the polynomial (namely, that it agrees with $Rem(x,b)$ on all integers $|x| \leq A$), so you can find such a polynomial by interpolation. Without further argument, one gets a degree upper bound of $2A$. Since the interpolated points look like a "sawtooth" with peaks and valleys with a period of $b$, the polynomial has at least $A/b$ extreme points in the range $-A \leq x \leq A$, so it must have degree at least $1+A/b$.  
> **username_1**: BTW, the model you are suggesting is very similar to Mulmuley's "algebraic RAM without bit operations," which is essentially nonuniform polynomials, except that the nonuniformtiy can depend both on the number of inputs and on the total bitlength of the inputs.  
> **username_1**: Following up on the last comment: there are even polynomials that will extract the $i$-th bit of any number of size bounded by $A$; so if you want to go with that setting, it really isn't very different from just considering the full Boolean setting. The place where RAMs without bit operations can differ from Boolean algorithms is in parallel complexity (PRAM without bit ops), but that seems to me like a separate question...  
> **username_0**: I am just curious if it could have other applications. AFAIK no one has used remainder polynomials anywhere explicitly.  
> **username_0**: If the ith bit extraction can be generalized to subset of bit extractions may be it could be useful in factorial extraction from shamir's technique?  
> **username_0**: the degree gap $1+A/b<deg<2A$ is very large in particular when $A=cb$ where $c$ is constant. Is there a better estimate?  
> **username_1**: @Turbo: Actually, the lower bound should be something like $1 + (2A/b - 2)$, since both the beginning and end of each interval of the form [kb, k(b+1)-1] are extreme points, so each such interval has *two* extreme points, except that the endpoints of the whole interval [-A,A] need not be extreme points (hence the minus 2). So the actual bound is between $2A/b-1$ and $2A$. Some quick numerical experiments using Lagrange interpolation in sympy ($A \leq 10$, $2 \leq b \leq 10$) suggest that the degree is always exactly 2A. It would be nice if someone could prove this... :)  
> **username_0**: interesting        $  $  
> **username_1**: @Turbo: I think degree 2A should be provable by looking at the second derivative (and using the fact that, within an interval $[kb, k(b+1)-1]$, the points to be interpolated lie on a line).  
> **username_0**: thank you but it trying to see if it makes sense at $b\in\{A,A+1,\dots,2A\}$.  
> **username_1**: @Turbo: oh, well, I was assuming that rem(x, b) is always nonnegative, and that you're interpolating for all x in [-A, A].  
> **username_0**: @JoshuaGrochow is comparison ($<$,$=$,$>$) in $TC0$?  
> **username_1**: @777: Yes. Equality is in $AND \cdot NC^0$. Subtraction is in $AC^0$, and comparison-against-0 is similarly easy (e.g., using two's complement representation, it is in $AND \cdot NC^0$).  
> **username_0**: Is computing $m$ such that $am\equiv1\bmod n$ in $NC^1$ when $a$ is given and $n$ is prime?  
> **username_0**: Or in $NC$ at all?  
> **username_1**: I think this is open. It's basically the extended Euclidean gcd algorithm, which iirc is a candidate for being intermediate between NC and P-complete.  

---

### Answer by username_4 on 2014-08-26. Score: 1

If a reverse of a modulo $M$ exists, it means that $\gcd(a,M)=1$, so you can just use the extended Euclidean algorithm to find $x$ and $y$ that satisfy $ax+My=1$. From here $x$ will be the reverse modulo $M$. And the running time of the extended Euclidean algorithm is $O(\log(\max(a, M)))$. Here you have $b=1$.

> **Comments:**
> **username_5**: Under what model is this complexity for the extended Euclidean algorithm valid? $M$ may be large (bignum) in the sense that arithmetic operations take $P(\log M)$ time and not $O(1)$.  

---

