Manejo de números enormes

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: Wolfram|Alpha Widgets: "Modular Multiplicative Inverse" - Free Mathematics Widget

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;
}

Comienza usando tipos de variables que te permitan las operaciones mencionadas.
int es enterio y es 2^16 = 65536 o sea va de 0 a 65535 en cuanto a los enteros sin signo y la mitad cuando usa signo.
Lo mejor para tu caso es usar unsigned long y ya veremos si requieres de unsigned long long para 64 bits, pero eso es otro capítulo.
Otro tema. Aca estamos en arduino y el main() de C digamos que es otro terreno pero por eso tampoco existe printf() tal como lo usas salvo en algunas placas.

Asi que comencemos definiendo que placa vas a usar?
UNO/NANO/MEGA estan limitadas.
DUE/ESP8266/ESP32/SMT32 en cambio si usan printf y al ser mas potentes tmb toleran otras cosas.

Voy a probar tu código en un NANO solo para ver como se comporta y luego hago mi comentario aquí o en otro post.

Dime como lo compilas?

NOTA: pense que estaban bien pero veo que los códigos estan mal posteados.
Todo debe postearse entre etiquetas.
Edita tu post anterior y toma cada código, lo cortas, click en </> y luego pasteas y entonces ser verá de acuerdo a las normas.

A diferencia del Python, que tiene un tipado dinámico, C y todos los lenguajes relacionados, tienen un tipado fuerte. Corre por tu cuenta reservar el tamaño de memoria que necesitas.
Por ejemplo:

void setup() {
Serial.begin(9600);
unsigned long t; 
int a=3000;
int b=3000;
t= a*b;  
  Serial.println(t);
t= (unsigned long)a*(unsigned long)b;  
  Serial.println(t);
t= 3000*3000;  
  Serial.println(t);
t= 3000UL*3000UL;  
  Serial.println(t);
}
void loop() {}

Da como resultado

21568
9000000
21568
9000000

Cuando haces dos operaciones con int el compilador no te asignara el resultado a un tipo de variable "que entre" (a diferencia de Phyton) a pesar que después el resultado se los asignes a a una variable "donde entre". Cuando tu resultado es un unsigned long, todos los operandos de la función tienen que ser unsigned long (hay excepciones pero mejor hacerlo así ) .

Saludos

He convertido el código (aún debes editarlo para que se vea convenientemente con las etiquetas) a Arduino pero en un ESP8266 que tolera printf como ya te indiqué.

#include <Arduino.h>

#include <math.h>

unsigned long numero = pow(5,3);
unsigned long modulo = 23;

struct xgcd_return {
  unsigned long x;
  unsigned long y;
  unsigned long GCD;
};

/*
  Return 1 / a (mod m).
  @a and @m must be co-primes --> a * x + m * y = 1
*/
unsigned long invmod(size_t a_Dvd, unsigned long value_m) {
  if (value_m < 2) {
      Serial.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 };
      Serial.printf("\nsolution = { 0, 1, %i };", value_m);
  }
  else if (value_m == 0) {
      //solution = { 1, 0, a_Dvd };
      Serial.printf("\nsolution = { 1, 0, %lu };", a_Dvd);
  }
  else {
      unsigned long s_pp = 1, t_pp = 0; //s_previoprevio, t_previoprevio
      unsigned long m_dvr = value_m, s_pv = 0, t_pv = 1; //Divisor, s_previo, t_previo
      Serial.printf("q, r, s, t");
      Serial.printf("\n   %lu, %i, %i", a_Dvd, s_pp, t_pp);
      Serial.printf("\n   %i, %i, %i", m_dvr, s_pv, t_pv);
    
      while(m_dvr) {
          unsigned long qtt = a_Dvd / m_dvr; //Nos quedamos con la parte entera
          //unsigned long rmr = a_Dvd % m_dvr; //Remainder
          unsigned long s_c = s_pp - qtt * s_pv;
          unsigned long t_c = t_pp - qtt * t_pv;
          Serial.printf("\n%i, %lu, %i, %i", qtt, a_Dvd%m_dvr, s_c, t_c);
          
          /* Si la solucion se publicara aqui
          //Return (x, y, GCD) : a * x + b * y = gcd(a, b)
          unsigned long x = s_pv;
          unsigned long y = t_pv;
          unsigned long GCD = m_dvr;
          */
          
          //en la siguiente iteracion
          unsigned long 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;
      }
  }

  //Serial.printf("\n(x, y, g): %i, %i, %i", solution.x,solution.y,solution.GCD);
  if (solution.GCD != 1) {
      Serial.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
          //Serial.printf("\nx: %i",solution.x);
          //Serial.printf("\nm: %i",value_m);
          //Serial.printf("\nResto de %i / %i = %i",solution.x,value_m,(solution.x+value_m));
          return ((solution.x+value_m));
      }
      else {
          //Serial.printf("\nx: %i",solution.x);
          //Serial.printf("\nm: %i",value_m);
          //Serial.printf("\nResto de %i / %i = %i",solution.x,value_m,solution.x % value_m);
          return (solution.x % value_m);
      }
  }
}

void setup() {
  Serial.begin(115200);
  unsigned long resultado = invmod (numero, modulo);
  Serial.printf("\ninvmod (%i, %i)= ", numero, modulo);
  Serial.printf("%i",resultado);
}

Convertir el código de C++ a arduino es lo de menos, lo he puesto así para que pudiérais comprobar rápidamente lo que digo copiando el código en un compilador online. He puesto el ejemplo con números muy pequeños para que veais el funcionamiento, pero la base de número es del orden de 1564557354 y el exponente es un número aleatorio que puede variar entre 1 y 1000. Imaginad el número que sale de la operación 1564557354^1000. Python lo maneja sin problemas, pero en C++ a partir de 1564557354^2 ya no sé hacerlo. Con unsigned long no tengo ni para empezar.

Para vuestra sencillez, aquí tenéis el código en Python para 1564557354^2, listo para ejecutar:

El código en C++. En la primera operación, pow(1564557354, 2), ya da resultados erróneos, y tan sólo he elevado a 2, imaginad si elevo por 1000. Python da 2447839713955481316 mientras que C++ 18446744071562067968:

Creo que lo que necesitas es una librería para trabajar con números de precisión arbitraria. Parece ser que para Arduino hay esta: https://www.arduino.cc/reference/en/libraries/gmp-ino/

Esto servirá, recuerdo haber leído un artículo de Nick Gammon, a ver si lo encuentro.
Hablaba de números super grandes.
Lo encontreeeeeeeeeeeeeee!!!!!!!!!

 BigNumber Num = "67411411944031530524562029520200239450929984281572279077458355238873731477537";

Acá tienes la librería

Eso es lo que te estamos diciendo, tu código en C++ tiene errores en el manejo de tipos, por eso da resultados erróneos el programa. No puedes hacer una adaptación de un código de Phyton sin tener en cuenta la diferencia en manejos de tipos: dinámico en uno y estricto en el otro.

Bueno he llegado hasta

1564557354^50 = 5978481980109475712822030153757829327463589753598053197600968435072353321849121226011761431386203036987814278940055593124357831552614265910916742072210685279271714363821791701984109985991894185483931851346149376

Creo que es un comienzo no?

#include <Arduino.h>

// BigNumber test: powers
#include "BigNumber.h"

void setup ()
{
  Serial.begin (115200);
  Serial.println ();
  BigNumber::begin ();  // initialize library

  Serial.println ("--- powers of 2 ---");
  
  BigNumber a = 1564557354;

  for (int i = 1; i <= 100; i++)
  {
    Serial.print ("1564557354^");
    Serial.print (i);
    Serial.print (" = ");
    BigNumber p = a.pow (i);
    Serial.println (p);
  }  // end of for loop

}  // end of setup

void loop () { }

IMPORTANTE!! No son correctos
Era demasiado bueno.
Evidentemente funciona para potencia de 2^ potencias de 3^ pero no para potencias de 1564557354^
Los números no son correctos mas allá que vi tantos que pensé que lo eran

Es muy posible que el limite este establecido en este define

#define MUL_BASE_DIGITS 80

Que ahora no encuentro donde lo vi.
La limitación es de RAM. Lo probé en un NANO.
Hay que pasar a placas con mas RAM.
Probaré un ESP8266 o un ESP32.

En un ESP8266 con esta base 123456 llego hasta exponente 100

123456^100 = 141651168940626040157173922295237694614407777111544929689914197215146037495716786002181514731502873952752208030711253307891310800045294972947142889897546596311778001481494350554032710769350421462376714987249722830547951312118519834558204292797510714465501274866500440431911234712671638258387067887030220472817288171611494820369323344867858431232828843615679582021753004875875074756298915946141612348303044632387866341223891372523873802426701213600095087751157822483552890441037881153637257214553128381370597376

Increíble.
Vamos con el objetivo del OP

Con la base y con esponente 100 llega.

Bueno y el limite para tu base es el exponente 903.


No son todos los números y no se quien puede comprobarlos, jajaja

Disfruta.

Esto en un ESP8266, tal vez un ESP32 que tiene mas RAM llegue a 1000.

#include "BigNumber.h"

void setup ()
{
  Serial.begin (115200);
  Serial.println ();
  BigNumber::begin ();  // initialize library

  Serial.println ("--- powers of 2 ---");
  
  BigNumber a = 1564557354;
  int i = 903;
  //for (int i = 900; i <= 902; i++)   {
    Serial.print("1564557354^"+String(i)+" = ");
    BigNumber p = a.pow(i);
    Serial.print(p);
    Serial.println();
  //}  // end of for loop

}  // end of setup

void loop () { }

Implementa esos numerotes utilizando listas enlazadas, de esa manera tendrás números tan grandes como lo permita la RAM de tu chip. Además, y de manera afortunada, deberás crear tus propios algoritmos para llevar a cabo las operaciones que necesitas.

Según la calculadora HiperCalc Pro (Android) al menos hay coincidencia en los primeros 15 dígitos (2.74883598026039*10^919) los otros 904 son inverificables. :wink:

De paso, solo por probar, la calculadora llega hasta el exponente 108, luego ya da desbordamiento así que si llegaste al 903 es muy bueno (suponiendo que el resultado es correcto, claro).

Corregí el programa posteado originalmente

#include <iostream>
#include <math.h>
using namespace std;

long numero =   2447839713955481316; //pow(1564557354, 2);
int modulo = 23;

struct xgcd_return
{
   long x;
   long y;
 long GCD;
};

int invmod( long 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 {
        long s_pp = 1, t_pp = 0; //s_previoprevio, t_previoprevio
        long m_dvr = value_m, s_pv = 0, t_pv = 1; //Divisor, s_previo, t_previo
        printf("q, r, s, t");
        printf("\n   %ld, %ld, %ld", a_Dvd, s_pp, t_pp);
        printf("\n   %ld, %ld, %ld", m_dvr, s_pv, t_pv);

        while(m_dvr) {
            long qtt = a_Dvd / m_dvr; //Nos quedamos con la parte entera
            //int rmr = a_Dvd % m_dvr; //Remainder
             long s_c = ( long)s_pp -  ( long)qtt * ( long) s_pv;
          long  t_c =( long) t_pp - ( long)qtt * ( long)t_pv;
            printf("\n%ld, %ld, %ld,%ld ", qtt, a_Dvd%m_dvr, s_c, t_c);

            //en la siguiente iteracion

            long a = a_Dvd % m_dvr; //Remainder
            a_Dvd=m_dvr;
            m_dvr=a;
            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 (%lu, %i)= ", numero, modulo);
    printf("%i",resultado);

    return 0;
}

si reemplazo el valor pow(1564557354, 2) por el valor resultante de tu codigo Pyhton ( 2447839713955481316)
La salida es

screen
Que es igual a tu salida Phyton
screen02

Pero cuando utilizo pow(1564557354, 2) el resultado es diferente ( de hecho este valor coincide con algunas calculadoras online)
screen01

Pow en C++ da error porque trabaja con floats, es solo una aproximación.

#include <iostream>
#include <math.h>
using namespace std;
constexpr long int_pow(long b, long e)
{
    return (e == 0) ? 1 : b * int_pow(b, e - 1);
}


long numero =   int_pow(1564557354, 2); //2447839713955481316;
int modulo = 23;

struct xgcd_return
{
   long x;
   long y;
 long GCD;
};


int invmod( long 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 {
        long s_pp = 1, t_pp = 0; //s_previoprevio, t_previoprevio
        long m_dvr = value_m, s_pv = 0, t_pv = 1; //Divisor, s_previo, t_previo
        printf("q, r, s, t");
        printf("\n   %ld, %ld, %ld", a_Dvd, s_pp, t_pp);
        printf("\n   %ld, %ld, %ld", m_dvr, s_pv, t_pv);

        while(m_dvr) {
            long qtt = a_Dvd / m_dvr; //Nos quedamos con la parte entera
            //int rmr = a_Dvd % m_dvr; //Remainder
             long s_c = ( long)s_pp -  ( long)qtt * ( long) s_pv;
          long  t_c =( long) t_pp - ( long)qtt * ( long)t_pv;
            printf("\n%ld, %ld, %ld,%ld ", qtt, a_Dvd%m_dvr, s_c, t_c);

            //en la siguiente iteracion

            long a = a_Dvd % m_dvr; //Remainder
            a_Dvd=m_dvr;
            m_dvr=a;
            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 (%lu, %i)= ", numero, modulo);
    printf("%i",resultado);

    return 0;
}

screen04

@IgnoranteAbsoluto Gracias por la librería, le echaré un ojo

@PeterKantTropus Entiendo lo que quieres decir y lo que pregunto aquí es cómo solucionarlo.

@Surbyte Gracias por tu increíble ayuda. He ejecutado tu código con 1564557354^903 en mi ESP-12F y el resultado es correcto. Voy a hacer pruebas con otros números.

@fjrg76 me puedes mostar un ejemplo simple para ver cómo se haría?

@PeterKantTropus Gracias, le echo un ojo a tu código.

@Surbyte He estado probando y, efectivamente, llego hasta 1564557354^903. Si elevo a 904 el monitor serie muestra esto:

--- powers of 2 ---
1564557354^904 = 
--------------- CUT HERE FOR EXCEPTION DECODER ---------------

Soft WDT reset

>>>stack>>>

ctx: cont
sp: 3ffffca0 end: 3fffffc0 offset: 01a0
3ffffe40:  00000000 00000932 3fff155c 4020113e  
3ffffe50:  00000003 3fff3b44 3fff65b7 3fff53ac  
3ffffe60:  3fff536c 00000000 00000932 40201832  
3ffffe70:  3fff44bc 3fff53cc 3fff883c 3fff153c  
3ffffe80:  3ffef414 3fff538c 3fff53ac 3fff534c  
3ffffe90:  3fff536c 0000061c 3ffe85e0 401006bf  
3ffffea0:  3ffffee0 0000207a 00000931 00000000  
3ffffeb0:  3fff3b64 00000020 000004e3 3fff44bc  
3ffffec0:  feefeffe 00001265 3fffff20 3fff3b64  
3ffffed0:  3fffff80 00000e15 00000000 4020191c  
3ffffee0:  3fff3b64 00000001 3ffef3ec 4020113e  
3ffffef0:  00001264 00000000 3fff2804 3fffff24  
3fffff00:  3fffff13 00000000 00000003 00000000  
3fffff10:  3fffff80 00000000 00000001 40201dd4  
3fffff20:  3fff3b64 3fff2804 3ffe85e0 401006bf  
3fffff30:  00000000 00000000 3ffee518 3ffee580  
3fffff40:  3fffdad0 00000020 3ffef3ec 3ffee580  
3fffff50:  3fffff70 3fffff94 3fffff7c 402022c1  
3fffff60:  3fffdad0 00000000 3ffee518 402021a9  
3fffff70:  40205758 3ffef3ec 00000000 40205758  
3fffff80:  3ffef344 00000000 00000000 000e000f  
3fffff90:  00000000 40205758 3ffef3bc feefeffe  
3fffffa0:  feefeffe feefeffe 3ffee56c 40202d20  
3fffffb0:  feefeffe feefeffe 3ffe85dc 40100b51  
<<<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
v00043200
~ld

Es un gran paso. Con exponentes de 900 ya se pueden hacer cositas. Me gustaría llegar a 1000, pero los exponentes cercanos a 1000 forman números que crecen mucho.

Edito: tras hacer pruebas me he percatado de que a BigNumber sólo se le puede asignar valores comprendidos entre -2147483648 y 2147483647.

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