Question

Give a polynomial-time algorithm for computing,${\mathbf{a}}^{{\mathbf{b}}^{\mathbf{c}}}\mathbf{mod}\mathbf{}\mathbf{p}$ given a,b,c, and prime p.

Short answer

An Algorithm:

Use Fermat’s little theorem

${\mathrm{a}}^{\mathrm{p}-1}\equiv 1\mathrm{mod}\mathrm{p}$

Apply on$a^{b^c}$ with twice modular exponentiation operation

${\mathrm{a}}^{{\mathrm{b}}^{\mathrm{c}}}\equiv {\mathrm{a}}^{{}^{}\left({\mathrm{b}}^{\mathrm{c}}\right)\mathrm{mod}\mathrm{p}-1}\mathrm{mod}\mathrm{p}$

Return a,b,c,p

The algorithm runs in $O\left(n^3\right)$time.

Step-by-step solution

Explain Polynomial time algorithm

If an algorithm solves the problem with the $\mathit{O}\left(m^k\right)$number of steps for a given input, then the algorithm is a polynomial time algorithm.

Give a polynomial-time algorithm for computing,abcmod p,

Consider the Fermat’s little theorem to solve the modular exponentiation.An Algorithm:

Use Fermat’s little theorem

${\mathrm{a}}^{\mathrm{p}-1}\equiv 1\mathrm{mod}\mathrm{p}$

Apply on with twice modular exponentiation operation

$a^{b^c}\equiv a^{\left(b^c\right)}modp-1)modp$

Return a,b,c,p

The above algorithm runs in $O\left(n^3\right)$time.

Therefore, a polynomial time algorithm ahs be obtained to compute $a^{b^c}\mathrm{mo}dp$.