Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
As stated in the question, I am trying to write a generic solver for $2^{(x+1)^2}$ modulo $m$ where $m$ is not prime. Normally you can just do exponentiated squaring with modulus to get the answer, but the problem I have is that $(x+1)^2$ is too large to store in a standard datatype like unsigned long long in C++. Doing $2^{(x+1)^2~mod~m}~mod ~m$ is also wrong.
Is there any way to get around this problem?
Are you trying to solve for $x$, or compute that power of $2$ given $x$?
If the latter, and assuming $m$ is odd, you can use Euler's theorem: $2^a \equiv 2^{a\ \bmod\ \phi(m)} \pmod m$. Of course, here $m$ must be small enough to factor efficiently, or you must have some special knowledge of $\phi(m)$.
In the worst case, you can always rewrite $2^{(x+1)^2} = (2^{x+1})^{x+1}$, where $x+1$ presumably fits inside an integer, and so each exponentiation can be done using repeated squaring.
