Manejo de números enormes

International Español Software
4

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