how to compute a^x %p Hi I want to calculate $a^x mod p$ where p is prime and $x$ is large. What I know is that since $p$ is prime, it forms a cyclic group with order $p$ ie $ a^p$ $mod$ $p = a$. Thus, my problem will be easier if I do $x = $$t $ $mod(p-1) $ and then compute $a^t$ $mod$ $p$. But while computing my $x$ in the earlier stage i have expression like
$x = c(2n,n)^b$  which i can compute only by using modular inverse. since here $(p-1) $ is not prime( actually an even number ) I cannot proceed with it. Can anybody help to find any progress in this.
 A: The real problem here seems to be to compute the value of the (central) binomial coefficient $\binom{2n}n$ modulo an integer $m$ (where $m+1$ is the prime number $p$, but this gives us little useful information about the factorisation of $m$, except that it $m$ is almost certainly composite).
Since you did not say that the prime $p$ was huge, I'll suppose that it is feasible to find the factorisation of $m=p-1$ effectively. Even if this is not the case, you might be able to proceed by ignoring any remaining divisor$~D$ of$~m$ for which you checked that $D$ has no prime factors less than $2n$, because $\tbinom{2n}n$ is guaranteed to be invertible modulo$~D$, and the inverse can effectively be computed using the extended Euclidean algorithm. For the prime factors $q<2n$ of $m$,  Kummer's theorem is your friend (though I guess you could get its result here by direct reasoning as well, if you had not heard about it before). It tells you that you can find the multiplicity of $q$ as factor of $\tbinom{2n}n$ by performing the addition $n+n$ numerically in base $q$ representation, and paying attention to any carries that may be generated; the number of carries gives the multiplicity you are after. Once the powers of such $q$ are dealt with, you can find the remaining factor of $\tbinom{2n}n$ by taking the fraction
$$
  \frac{2n(2n-1)(2n-2)\ldots(n+1)}{n(n-1)(n-2)\ldots1} \tag1
$$
and dividing each factor by the largest powers of such $q$ possible; the remaining quotient of products can be computed directly modulo $m$, since everything has become relatively prime to $m$.
The "direct reasoning" above amounts to simply keeping track of the factors $q$ you are simplifying by, and multiplying the end result by any excess power that was removed from the numerator but not from the denominator. Come to think of it, you can do this using only very basic theory: simply write every factor in$~(1)$ as product of all the prime factors it has common with$~m$, and a remaining part that is relatively prime with $m$; then perform separate computations for the "common" and "relatively prime" parts. Warning: the "product of common prime factors with $m$"  of a number need not be equal to its GCD with$~m$ (it could be larger); nonetheless it can be found by repeated GCD computations.
