Hola, tengo un par de funciones en Python que sirven para calcular el inverso multiplicativo modular de un número.
Por ejemplo, el I.M.M. de 125 módulo 23 es igual a 7 según esta calculadora: https://www.wolframalpha.com/widgets/view.jsp?id=680a55df94d709f3d5a8cbcea6ccd6b0
En mi caso el número al que quiero calcular el I.M.M. será una potencia. Por ejemplo, 5^3 que es lo mismo que 125.
Quiero pasar el código a C++ y no sé cómo manejarlo, porque con números pequeños funciona, pero cuando introduzco números grandes elevados a exponentes grandes, hace aguas por todas partes. Pienso que es porque los valores son mayores a unsigned long. He probado también con size_t, pero tampoco.
¿Podéis ayudarme? Dejo los códigos listos para copiar/pegar a un compilador online con el ejemplo anterior.
Ejemplo invmod(5³,23) en Python:
numero = pow(5,3)
modulo = 23
def invmod(value_a, value_m):
"""
Return 1 / a (mod m).
@a and @m must be co-primes --> a * x + m * y = 1
"""
if value_m < 2:
raise ValueError("modulus must be greater than 1")
x, y, g = xgcd(value_a, value_m)
if g != 1:
raise ValueError("no invmod for given @a and @n")
else:
return x % value_m
def xgcd(a_Dvd, b_dvr):
#Extended Euclid GCD algorithm.
#Return (x, y, g) : a * x + b * y = gcd(a, b) = g.
if a_Dvd == 0:
return 0, 1, b_dvr
if b_dvr == 0:
return 1, 0, a_Dvd
s_pv, s_pp = 0, 1
t_pv, t_pp = 1, 0
print("q, r, s, t")
print(" {}, {}, {}".format(a_Dvd,s_pp,t_pp))
print(" {}, {}, {}".format(b_dvr,s_pv,t_pv))
while b_dvr:
qtt = a_Dvd // b_dvr
s_c = s_pp - qtt * s_pv
t_c = t_pp - qtt * t_pv
print("{}, {}, {}, {}".format(qtt, a_Dvd%b_dvr, s_c, t_c))
#En la siguiente iteracion
a_Dvd, b_dvr = b_dvr, a_Dvd % b_dvr
s_pp, s_pv = s_pv, s_c
t_pp, t_pv = t_pv, t_c
return s_pp, t_pp, a_Dvd
print("invmod({}, {}) = {}".format(numero,modulo,invmod(numero, modulo)))
Ejemplo invmod(5³,23) en C++:
#include <iostream>
#include <math.h>
using namespace std;
int numero = pow(5,3);
int modulo = 23;
struct xgcd_return
{
int x;
int y;
int GCD;
};
int invmod(size_t a_Dvd, int value_m) {
/*
Return 1 / a (mod m).
@a and @m must be co-primes --> a * x + m * y = 1
*/
if (value_m < 2) {
printf("modulus must be greater than 1");
return 0;
}
/*
Extented Euclid GCD algorithm.
Return (x, y, GCD) : a * x + b * y = gcd(a, b)
*/
xgcd_return solution = { 0, 0, 0 };
if (a_Dvd == 0) {
//solution = { 0, 1, value_m };
printf("\nsolution = { 0, 1, %i };", value_m);
}
else if (value_m == 0) {
//solution = { 1, 0, a_Dvd };
printf("\nsolution = { 1, 0, %lu };", a_Dvd);
}
else {
int s_pp = 1, t_pp = 0; //s_previoprevio, t_previoprevio
int m_dvr = value_m, s_pv = 0, t_pv = 1; //Divisor, s_previo, t_previo
printf("q, r, s, t");
printf("\n %lu, %i, %i", a_Dvd, s_pp, t_pp);
printf("\n %i, %i, %i", m_dvr, s_pv, t_pv);
while(m_dvr) {
int qtt = a_Dvd / m_dvr; //Nos quedamos con la parte entera
//int rmr = a_Dvd % m_dvr; //Remainder
int s_c = s_pp - qtt * s_pv;
int t_c = t_pp - qtt * t_pv;
printf("\n%i, %lu, %i, %i", qtt, a_Dvd%m_dvr, s_c, t_c);
//en la siguiente iteracion
int m_dvr_temp = m_dvr;
m_dvr = a_Dvd % m_dvr; //Remainder
a_Dvd = m_dvr_temp;
s_pp = s_pv;
t_pp = t_pv;
s_pv = s_c;
t_pv = t_c;
//Solucion
solution.x = s_pp;
solution.y = t_pp;
solution.GCD = a_Dvd;
}
}
//printf("\n(x, y, g): %i, %i, %i", solution.x,solution.y,solution.GCD);
if (solution.GCD != 1) {
printf("\nno invmod for given @a and @n");
return 0;
}
else {
if (solution.x<0) { //si el resultado es negativo C++ no hace bien el modulo
//printf("\nx: %i",solution.x);
//printf("\nm: %i",value_m);
//printf("\nResto de %i / %i = %i",solution.x,value_m,(solution.x+value_m));
return ((solution.x+value_m));
}
else {
//printf("\nx: %i",solution.x);
//printf("\nm: %i",value_m);
//printf("\nResto de %i / %i = %i",solution.x,value_m,solution.x % value_m);
return (solution.x % value_m);
}
}
}
int main()
{
int resultado = invmod (numero, modulo);
printf("\ninvmod (%i, %i)= ", numero, modulo);
printf("%i",resultado);
return 0;
}
