2
$\begingroup$

I am trying to solve the following problem.
I need to find the value of
$ a^{(b^x)} \bmod m $ where $a,b$ are integers and
$ x = \pmatrix{n\\0}^2 + \pmatrix{n\\1}^2 + ... + \pmatrix{n\\n}^2 $ the value of $n$ can be upto $10^5$
and $m = 1000000007$ which is a prime
Also note that its $a^{b^x}$ which is not equal to $a^{bx}$
Also by solving $c$ it comes out to be $\pmatrix{2n\\n}$
also $\pmatrix{2n\\n}$ satisfies the relation $ a_n = a_{n-1} (4n-2)/n $ where $a_0 = 1$
I have reached the fact that $a^{b^c} \bmod m$ is equivalent to
$ a^{b^d \bmod \phi(m)} \bmod m $ where $d=c \bmod \phi(\phi(m))$

but i am unable to calculate the value of $c$ as it involves a denominator term and modulo inverse is not possible since $\phi(\phi(m)) = 500000002$ is not a prime.
Can anyone suggest me any approach or any possible thing that I missed.
Thanks.

  • 0
    well don't worry got it!! thnks so much for your help..2012-07-21

0 Answers 0