4
$\begingroup$

The complexity of modular addition is known: $g + p \mod N$ (for $|p| \approx |g| \approx |N|$) can be computed in $O(n = |N|)$.

The complexity of modular multiplication is open though some results are known: by Toom-Cook $g * p \mod N$ can be performed in $O(n^{1.465})$ and by Schönhage–Strassen in $O(n \log n \log \log n)$.

Modular exponentiation can be performed in $O(M(n) k)$ where $M(n)$ is the complexity of multiplication and $k$ is the length in bits of the exponent by the square-and-multiply algorithm.

I am looking for results about the modular arithmetic in general. Are there better complexity results for performing modular exponentiation (over the 'naive' square-and-multiply)? What results are known for modular exponentiation of power towers of height h?

(For $h = 3$: $g^{g^{g}} \mod N$ and for general $h$: $g^{g^{g^{g^{...^g}}}} \mod N$)

$\endgroup$
  • $\begingroup$ Your notation seems unclear. What does $ n $ mean in $ O(M(n)k) $? Is $ n $ the modulus? $\endgroup$ – Zsbán Ambrus Jun 19 '15 at 22:48
  • $\begingroup$ I did take a shortcut in notation, though it is standard and should be understandable based on the context of the question. n is the length of the input (number of digits in the modulus). $\endgroup$ – Ross Snider Jun 19 '15 at 23:15
  • $\begingroup$ Edited the comment to specify $n = |N|$. Thank you for helping to clarify. Please let me know if the question needs some additional clarification. $\endgroup$ – Ross Snider Jun 19 '15 at 23:24
5
$\begingroup$

Sorry if this answer doesn't tell anything nontrivial, but you don't seem to imply these results in the questionm.

Consider first the problem of computing a modular exponentiation $ a^r \mod m $.

You say above that you can compute this by repeated squaring modulo $ m $, and that this needs $ O(\log r) $ multiplications. This is true, and it's certainly a practical algorithm for some range of inputs. But for other inputs, it's not the best you can do. The important case I want to talk about comes up when $ r $ is very large.

First, let $ c = gcd(a, m) $ and $ b = a/c $ and we'll compute the result as the product of the $ c^r \mod m $ and $ b^r \mod m $ values. If $ \log_2 m < r $ then $ c^r \equiv 0 $, otherwise computer $ c^r $ by the simple algorithm with $ \log r $ multiplications. Now we need a number $ s $ such that $ b^s \equiv 1 $, from which we can compute $ b^r $ as $ b^{r \mod s} $. The Euler phi function $ s = \varphi(m) $ is such a number. To compute $ s $, you need the integer factorization of $ m $, which takes $ O(m^\epsilon) $ time.

If the exponent $ r $ is so large that even $ \log r $ is significantly greater than $ m $, then reducing the exponent this way gives a faster method for the modular exponentiation. Alternately, if you have a problem where the inputs are constrained so you always know the factorization of $ m $, such as if you take only prime or power of two exponents, then this method is worth already when $ r $ is significantly greater than $ m $.

This case of the faster method comes up when you want to evaluate an exponential tower $ a^{r^t} \mod m $, supposing $ t $ is significantly larger than $ m $. For this, first compute $ s = \varphi(m) $ like above, then compute $ r^t \mod s $ by some modular exponentiation algorithm, then compute $ a^{r^t} $ as above. As $ r^t $ is large, this is faster than the simple method of first computing $ r^t $ and then doing $ O(\log(r^t)) $ modular multiplications. You can apply this to any exponential tower, thus recursively computing the exponential tower modulo $ m $. If you have an exponential tower of at least four levels and the final exponent is of comparable size to $ m $, such as in a tetration, then it is very likely that the logarithm of final exponent will be much greater than $ m $, so again this method is worth to compute a tetration.

$\endgroup$
  • $\begingroup$ Thanks Zsban. I am looking for general algorithms in this case where the factorization of the modulus may not be known. That's not to say this isn't a good addition. Thank you for the write-up. $\endgroup$ – Ross Snider Jun 19 '15 at 23:58
  • $\begingroup$ I think the algorithm is relevant, because it's useful for computing a modular tetration $ a\uparrow\uparrow h \mod m $ where $ h $ and $ m $ are of comparable size. You asked about tetration in the question, which is why I thought this was relevant. There could of course be a nontrivial algorithm for tetration that's significantly faster than this, in which case maybe this isn't relevant afterall, but I don't know of such an algorithm. $\endgroup$ – Zsbán Ambrus Jun 20 '15 at 0:09
  • $\begingroup$ Absolutely it is relevant in the case the factorization of the modulus is known. +1 :) $\endgroup$ – Ross Snider Jun 20 '15 at 0:15
  • 2
    $\begingroup$ For tetration, note also that the iterated Euler function $\phi^{(h)}(m)$ converges to $1$ after $\sim\log m$ iterations, and in particular, $a\uparrow\uparrow h\bmod m$ is constant (as a function of $h$) for $h\ge\log m$ or so. Thus, you won’t need more than $O(\log m)$ factorizations. One can easily generalize this to the modular Ackermann function; the argument in mathoverflow.net/a/165938 is not written with complexity in mind so the bounds are wasteful, but if you think about what really happens there, you’ll see that tetration is actually the hardest case. $\endgroup$ – Emil Jeřábek supports Monica Jun 20 '15 at 7:51
  • $\begingroup$ @Jeřábek: Wow, I didn't realize that the moduluses go to 1 so quickly. That's even better than I thought. $\endgroup$ – Zsbán Ambrus Jun 20 '15 at 15:07

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.