He probado la librería y no me funciona. El código ha sido:
#include <stdio.h>
#include <gmp-ino.h>
unsigned long base1 = 5;
unsigned long exponente1 = 3;
unsigned long modulo = 23;
unsigned long resultado;
int invmod(unsigned long base, unsigned long exponente, unsigned long value_m) {
struct xgcd_return
{
int x;
long y;
long GCD;
};
/*
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 };
mpz_t a_Dvd; mpz_init(a_Dvd); //Dividendo
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 };", mpz_get_ui (a_Dvd)); //convierto a_Dvd a unsigned long para poder imprimirlo
}
else {
mpz_ui_pow_ui (a_Dvd, base, exponente);
mpz_t m_dvr; mpz_init(m_dvr);
mpz_set_ui (m_dvr, value_m); //Copio el valor de value_m a m_dvr
mpz_t m_dvr_temp; mpz_init(m_dvr_temp);
mpz_t qtt; mpz_init(qtt);
//mpz_t s_c; mpz_init(s_c);
int s_pp = 1;
int s_pv = 0;
mpz_t t_pp; mpz_init(t_pp); mpz_set_ui (t_pp, 0);
mpz_t t_pv; mpz_init(t_pv); mpz_set_ui (t_pv, 1);
mpz_t t_c; mpz_init(t_c);
//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) {
//mpz_divexact (qtt, a_Dvd, m_dvr); //creo que falla si existe resto
mpz_cdiv_r (qtt, a_Dvd, m_dvr); //Nos quedamos con la parte entera
//int rmr = a_Dvd % m_dvr; //Remainder
int s_c = s_pp - mpz_get_si (qtt) * s_pv;
//t_c = t_pp - qtt * t_pv;
mpz_mul (t_c, qtt, t_pv); //tc = qtt * t_pv;
mpz_sub (t_c, t_pp, t_c); //t_c = t_pp - t_c;
//printf("\n%i, %lu, %i, %i", qtt, a_Dvd%m_dvr, s_c, t_c);
//en la siguiente iteracion
mpz_set (m_dvr_temp, m_dvr); //m_dvr_temp = m_dvr;
mpz_mod (m_dvr, a_Dvd, m_dvr); //m_dvr = a_Dvd % m_dvr; //Remainder
mpz_set (a_Dvd, m_dvr_temp); //a_Dvd = m_dvr_temp;
s_pp = s_pv;
mpz_set (t_pp, t_pv); //t_pp = t_pv;
s_pv = s_c;
mpz_set (t_pv, t_c); //t_pv = t_c;
}
//Solucion
solution.x = s_pp;
solution.y = mpz_get_si (t_pp);
solution.GCD = mpz_get_si (a_Dvd);
mpz_clear (a_Dvd);
mpz_clear (m_dvr);
mpz_clear (m_dvr_temp);
mpz_clear (qtt);
mpz_clear (t_pp);
mpz_clear (t_pv);
mpz_clear (t_c);
}
//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);
}
}
}
void setup() {
Serial.begin (115200);
Serial.println ();
Serial.println (invmod(base1, exponente1, modulo));
}
void loop() {
}
Y la salida por monitor serie:
User exception (panic/abort/assert)
--------------- CUT HERE FOR EXCEPTION DECODER ---------------
Abort called
>>>stack>>>
ctx: cont
sp: 3ffffe30 end: 3fffffc0 offset: 0000
3ffffe30: 3fffff78 00000001 00000020 40100914
3ffffe40: 000000fe 00000000 00000000 00000000
3ffffe50: 00000000 00000000 00000000 3fffff6c
3ffffe60: 00000001 000000e3 3ffef494 3ffee688
3ffffe70: 3fffff54 00000000 00000001 4020367e
3ffffe80: 3fffff6c 00000000 3ffffea0 40203690
3ffffe90: 3fffff6c 00000000 00000001 40202312
3ffffea0: 0000001f 80000000 00000020 ffffffff
3ffffeb0: 00000001 00000001 3ffef494 401008ea
3ffffec0: 3ffef44c 3ffef484 00000000 402012e8
3ffffed0: 3fffff6c 00000000 00000000 00000001
3ffffee0: 00000001 00000001 00000000 3ffef47c
3ffffef0: 00000000 3ffef494 3ffef494 40201030
3fffff00: fffffffe 00000001 3fffff54 3ffee688
3fffff10: 00000003 5d41402a 00000017 40202601
3fffff20: 00000003 5d41402a 00000017 40202860
3fffff30: 00000002 00000001 3ffef484 00000001
3fffff40: 00000001 3ffef454 00000001 00000001
3fffff50: 3ffef44c 00000001 00000000 3ffef474
3fffff60: 00000001 00000001 3ffef45c 00000001
3fffff70: 00000000 3ffef47c 00000003 00000001
3fffff80: 3ffef464 00000000 3ffee620 40202c1c
3fffff90: 3fffdad0 00000000 3ffee620 4020290c
3fffffa0: feefeffe feefeffe 3ffee674 4020320c
3fffffb0: feefeffe feefeffe 3ffe85f0 40100b9d
<<<stack<<<
--------------- CUT HERE FOR EXCEPTION DECODER ---------------
ets Jan 8 2013,rst cause:2, boot mode:(3,6)
load 0x4010f000, len 3460, room 16
tail 4
chksum 0xcc
load 0x3fff20b8, len 40, room 4
tail 4
chksum 0xc9
csum 0xc9
v00044e90
~ld