Prove that the following language can $be$ decided $in$ polynomial time, $i.e.,$ that

$L=\{($:$a$:$)|ais$ a positive integer represented $in$ binary and $a^a-=1151(mod2731)\}inP$

Note that $if$ #$d(a)is$ the number $of$ binary digits $ofa,$ then $to$ multiply $aby$ itself $a-1$ times,

would require $(a$#$d(a{)}^2)$ bit operations which $is$ exponential $in$ #$d(a).In$ other words, the

obvious algorithm $is$ not polynomial. Hint. Review the Number Theory segment $ofCS135$ for

ideas.