0
$\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$
  • $\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$ – David Richerby Oct 5 '18 at 15:23
  • $\begingroup$ Sorry i wrote c, corrected it now. Thats p in the modular exponentiation $\endgroup$ – Muhammad Usman Qureshi 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$ – Muhammad Usman Qureshi 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$ – David Richerby 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$ – Muhammad Usman Qureshi Oct 5 '18 at 17:11
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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Muhammad Usman Qureshi 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$ – Muhammad Usman Qureshi 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$ – Muhammad Usman Qureshi 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.