1
$\begingroup$

I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student).

  1. Is it poly time only for base 2, i.e in binary or will it remain poly time algorithm even if i run it in decimal system i.e base 10?

  2. If I'm calculating $(a^b) \bmod p$, where $1<a<11$, $1 < b \leq (p-1)/2$, and we run this modular exponentiation at most $p/2$ times, all this being done in decimal base 10 system, will it still be poly time?

  3. Even if this is poly time, and this is a big IF, can this process actually be completed in reasonable time in terms of the real worldly time?

$\endgroup$
6
  • $\begingroup$ What's $p$? Is it a number in your input? If so, since that number takes only $\log p$ bits, so looping up to $p$ could take time up to $2^{\text{input length}}$, which is exponential. $\endgroup$ Oct 5 '18 at 15:23
  • $\begingroup$ Sorry i wrote c, corrected it now. Thats p in the modular exponentiation $\endgroup$ Oct 5 '18 at 16:57
  • $\begingroup$ Wiki says complexity of doing the modular exponentiation one time is O ( log b). So doing it p/2 time should be O ((p/2)log b) is that right? Coz that can still be counted as a poly time algorithm $\endgroup$ Oct 5 '18 at 16:59
  • $\begingroup$ If $p$ is a fixed constant and not part of the input then, yes, the running time is polynomial. $\endgroup$ Oct 5 '18 at 17:10
  • $\begingroup$ It is a fixed number, a will also be fixed, i might vary b only in the limit mentioned. But in calcultating the modulus p will be used, so it will be part of the input $\endgroup$ Oct 5 '18 at 17:11
1
$\begingroup$

With regards to (3), there's a fairly simple algorithm to compute large exponents.

exp(a, b) =
  if b is even
     let half = exp(a , b/2)
     return half * half
  else
    return a * exp(a, b-1)

This will be logarithmic in the magnitude of $b$, meaning the number of multiplications is linear in the number of bits used to represent $b$. It's also a very general algorithm: it works for normal exponentiation, matrices, modular arithmetic, etc. The complexity will change depending on the complexity of your multiplication operation.

$\endgroup$
0
$\begingroup$

First of all, by the direct method, you have to multiply $b-1$ times the a and take a modular reduction.

  1. As stated in Wikipedia, the mathematical calculation are performed for any base $b$. In complexity theory the base is constant doesn't affect the class of the algorithm; the time is $\mathcal{O}(log\; exponent)$, for any base.

  2. See,1.

  3. Bigger exponent doesn't change the class. For polynomial time algorithms, sometimes have huge multipliers that they can be slower than exponential algorithms, up to some $n>0$, eventually, we will have the expected result. To determine the exact running time, in general, you have to mention the code, the compiler, the CPU and memory, number of cpus/cores and the exponent and the base itself. Than you can talk bout a bit more exact timings.

$\endgroup$
7
  • $\begingroup$ Thanks alot for the answer. One more question came to mind regarding the Exponentiation. Even if we take the indirect approach of exponentiation by squaring should we take mod at every step of multiplication? Becoz if we dont do that we might have a problem of memory overflow. On the other hand if we take modulo p at every step wouldn't that increase the complexity from O(log exp) to O(p log exp)? $\endgroup$ Oct 6 '18 at 17:36
  • $\begingroup$ And for the third question i didnt ask a bout a change in exponent. I meant it might be in poly time in complexity terms, but if we run such an algorithm will the result be achieved in a time that matters? $\endgroup$ Oct 6 '18 at 17:55
  • $\begingroup$ Well, polynomial time algorithms, sometimes have huge multipliers that they can be slower than exponential algorithms, up to some $n$, eventually, we will have the expected result. To determine the matter of the time, in general, you have to mention the code, the compiler, the cpu and memory, number of cpus/cores and the exponent and the base itself. Than we can talk bout a bit more exact timings $\endgroup$
    – kelalaka
    Oct 6 '18 at 18:01
  • $\begingroup$ Oh ok. And what about the issue with the modular exponentiation by squaring method, if we take modulo p at every step how can that still remain (log b) or j log exp )? $\endgroup$ Oct 6 '18 at 21:08
  • $\begingroup$ adding a constant amount of computation doesn't change the class. The affecting the class start with something that depends on the input size as $\log n$ something etc. If the answer is ok, Please close. $\endgroup$
    – kelalaka
    Oct 12 '18 at 8:33

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.