Cálculo (a^b)% MOD

Question

Deseo codificar para calcular el valor de pow (a, b)% MOD. Yo uso C++ para codificar.

Pero el problema es que el valor de b puede ser muy grande. Conozco el método log (b) time complexity. Pero, el valor de b podría no ajustarse en el tipo de datos "long long" de C++. Por ejemplo, b puede ser 1000000000 del número de Fibonacci. El cálculo exacto de un número tan grande es en sí mismo, no es posible (en límites de tiempo).

P.S. :

• pow (a, b) significa a * a * a * a * ... b veces.
• X% MOD significa el resto obtenido al dividir X por MOD.

Answer 1

Esa es una tarea típica. Por favor (o, realmente, ¡POR FAVOR!) Lea sobre el Euler's totient function.

Y luego el Euler's theorem.

El problema es que se puede reducir drásticamente a^b a a^(b% phi (MOD)). Sí, necesitará algún tipo de método de factorización de enteros, pero aún así, no hay ideas locas acerca de calcular realmente la potencia necesaria.

Hicimos tales muestras a mano en mi juventud :) Incluso cuando los números eran mucho más allá del rango de 32/64 bits.

EDITAR: Bueno, vives y aprendes. En 2008 se obtiene el resultado:

"El totient es la transformada de Fourier discreta de la mcd: (Schramm (2008))"

Así que para calcular phi (b) uno no necesita saber sus factores.

EDITAR (2):

Y el Carmichael's function es lo que necesita para calcular para obtener la respuesta correcta para todo a, b y MOD.

Answer 2

Primero: ^ en C/C++ es no el operador de poderes. De hecho, no hay operador para esto. ^ representa un bit XOR. Tendrá que usar pow(base, exp) que se puede encontrar en el encabezado math.h o cmath.

Para tales números enormes, utilizando double o long double (longitudes exactas y tipos de datos resultante y podrían variar dependiendo de la plataforma), pero en algún momento se encontrará con problemas de precisión, por lo que dependiendo de su caso de uso, el tamaño de los valores su mejor opción podría ser usar un tipo de datos personalizado (editar: por ejemplo, de una de las bibliotecas encontradas en una de las preguntas vinculadas).

Answer 3

Sugiero usar una biblioteca matemática especializada. También esto parece crypto, entonces sugiero usar una biblioteca crypto. GNU está obligado a tener uno que pueda usar. Esto se debe a que en la criptografía, en muchos casos, el exponente puede seleccionarse para ofrecer un cálculo eficiente utilizando atajos que las bibliotecas matemáticas normales no pueden asumir.

Answer 4

Para manejar números muy grandes, eche un vistazo a la biblioteca boost's Multiprecision. Tiene una función powm() que funciona bien para este propósito.

De Generic Integer Operations:

template <class Integer> 
Integer powm(const Integer& b, const Integer& p, const Integer& m); 

devoluciones b ^p% m.

Ejemplo:

#include <boost/multiprecision/cpp_int.hpp> 

boost::multiprecision::cpp_int pow("8912627233012800753578052027888001981"); 
boost::multiprecision::cpp_int mod("0x86f71688cdd2612c117d1f54bdae029"); 
boost::multiprecision::cpp_int base(12345); 

boost::multiprecision::cpp_int result = powm(base, pow, mod); 

std::cout << "result is: " << result << std::endl; 

impresiones:

result is: 5758534182572671080415167723795472693 

Answer 5

utilizo esta función para resolver este problema

UVA 374 - Big Mod

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=310

// a^b % T 

// with Exponentiation by squaring (http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Basic_method) 

// if a very large use 
// R=(unsigned long long)(R*a)%T; 

int restOfPot(long long a,int b,int T) 
{ 
    a%=T; 
    long long R=1; 

    while(b) 
    { 
     if(b&1) R=(R*a)%T; 
     a=(a*a)%T; 
     b>>=1; 
    } 

    return int(R); 
} 

Answer 6

embargo, el valor de b puede no encajar en el tipo de datos "long long" de C++. Por ejemplo, b puede ser 1000000000 del número de Fibonacci.

Por cosas como esta, hay una solución sencilla: recordar

un^(b + c) ==^un b * a^c mod d

Puede calcule el producto particular que solicitó con el mismo tipo de recursión que utiliza para calcular los números de Fibonacci: ¡no necesita números grandes ni exponenciación modular en absoluto!

Otra versión que aparece a veces es

a^(b * c) = (a^b)^c mod d

Answer 7

#include <iostream> 
#include <math.h> 
#include <stdint.h> 

using namespace std; 

int main(){ 
int64_t a, b, k, d; 
cin >> a >> b >> k; 

int64_t poew = pow(a, b); 
d = poew % k; 

cout << d; 
} 

porque int64_t tiene un rango mayor que int