3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – Joshua Grochow Aug 21 '14 at 16:10
  • $\begingroup$ 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. $\endgroup$ – T.... Aug 21 '14 at 17:08
  • 1
    $\begingroup$ It can be, same proof works as for standard Euclidean alg. $\endgroup$ – domotorp Aug 21 '14 at 19:13
  • $\begingroup$ @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... $\endgroup$ – Joshua Grochow Aug 22 '14 at 21:57
  • 4
    $\begingroup$ @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. $\endgroup$ – D.W. Aug 24 '14 at 3:53
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – T.... Dec 13 '14 at 13:37
  • 1
    $\begingroup$ 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$. $\endgroup$ – Joshua Grochow Dec 14 '14 at 6:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Dec 14 '14 at 6:11
  • 1
    $\begingroup$ 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... $\endgroup$ – Joshua Grochow Dec 14 '14 at 20:40
  • $\begingroup$ I am just curious if it could have other applications. AFAIK no one has used remainder polynomials anywhere explicitly. $\endgroup$ – T.... Dec 14 '14 at 23:03
0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Gilles Aug 26 '14 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.