Como se indica en la pregunta, estoy tratando de escribir un solucionador genérico para $2^{(x+1)^2}$ módulo $m$ donde $m$ no es primo. Normalmente puedes simplemente hacer la exponenciación al cuadrado con módulo para obtener la respuesta, pero el problema que tengo es que $(x+1)^2$ es demasiado grande para almacenarse en un tipo de datos estándar como unsigned long long en C++. Hacer $2^{(x+1)^2~mod~m}~mod ~m$ también es incorrecto.
¿Hay alguna manera de evitar este problema?
¿Estás intentando resolver para $x$, o calcular esa potencia de $2$ dado $x$?
Si es lo último, y asumiendo que $m$ es impar, puedes usar el teorema de Euler: $2^a \equiv 2^{a\ \bmod\ \phi(m)} \pmod m$. Por supuesto, aquí $m$ debe ser lo suficientemente pequeño como para factorizar eficientemente, o debes tener algún conocimiento especial de $\phi(m)$.
En el peor de los casos, siempre puedes reescribir $2^{(x+1)^2} = (2^{x+1})^{x+1}$, donde $x+1$ presumiblemente cabe dentro de un entero, y así cada exponenciación se puede hacer usando la elevación repetida al cuadrado.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
