Exponentiation by repeated squaring

[2/100%]
Show
LaTeX
Problem 7.13 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 7.2 "Problems"

Let

MODEXP⁡={⟨a,b,c,p⟩∣a,b,c, and p are positive binary integers  such that ab≡c( mod p)}. \begin{gathered} \operatorname {MODEXP}=\left\{ \langle a, b, c, p\rangle \mid a, b, c, \text{ and } p \text{ are positive binary integers } \\ \text{ such that } a^{b} \equiv c(\bmod p)\right\} . \end{gathered}

Show that MODEXP⁡∈P\operatorname {MODEXP} \in \mathrm{P}. (Note that the most obvious algorithm doesn't run in polynomial time. Hint: Try it first where bb is a power of 2.)

?
Problem 7.14 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 7.2 "Problems"

A permutation on the set {1,…,k}\left\{ 1, \ldots , k\right\} is a one-to-one, onto function on this set. When pp is a permutation, ptp^{t} means the composition of pp with itself tt times. Let

 PERM-POWER ={⟨p,q,t⟩∣p=qt where p and q are permutations  on {1,…,k} and t is a binary integer }. \begin{array}{r} \text{ PERM-POWER }=\left\{ \langle p, q, t\rangle \mid p=q^{t} \text{ where } p \text{ and } q \text{ are permutations } \\ \text{ on } \left\{ 1, \ldots , k\right\} \text{ and } t \text{ is a binary integer }\right\} . \end{array}

Show that PERM-POWER ∈P\in \mathrm{P}. (Note that the most obvious algorithm doesn't run within polynomial time. Hint: First try it where tt is a power of 2.)

?

References

[Sip13] Sipser M. Introduction to the Theory of Computation. 3rd ed., Cengage Learning, 2013.