//+------------------------------------------------------------------+
//|                                                          Not.mqh |
//|                                   Copyright 2026, Niquel Mendoza |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2026, Niquel Mendoza"
#property link      "https://www.mql5.com"
#property strict


/*
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+

Unca congruencia modular se define como:
 a = b  (mod N)

Lo que quiere decir que:
si divbises a y b por separod entre N sus residuos (modulo) son iguales

Por lo tnato
si  restas a-b los reidus se anulan por loq eu divir N entre a-b da una division exacta
con residuo 0

A su vez  al dar una division exacta, se cumple que, hay un numero K qeu si lo multiplcamos con
N es igual a (a-b)
  digmoas:
  c = (a-b)
  entonces
  c / n = k (k=cociente)  y r=0

  por lo que

  c = n*k+0 osea c=n*k

Ahora todo esto es una intruddccion vamos con lo de verdad RSA
en RSA se usa mucho esto.. diria que giura en todo a esto


Aparte hay una propiedad interesnate que luego se usa para obtener el "d" priuvado
apartir de lo publico

El invesro modular (inveso multiplcativo
numero x que si multicpls con y da 1) dice qeu si tenemos un numero a y queremos buscar su inverso muñltiplciatvio.
en el sitema normzal R por ejemplo

 se busca un numero qeu si lo multiplcaos con a da 1

  a * x = 1
  entonces
  x = 1/a facil

  El tema es que en aritmem modular solo existen enteros no fraciones
  Tampoco es que las pdoamso represtar dado que nuestro Z esta actoac a N (valor del modulo) valores
  Ni mas ni mesno

Asi qeu ahi va masmoes igual solo que:

 a*x = 1 (mod N)

Dice x cuimple qeu si lo mutlcionas por a y divos todo eso por N obtner un resto de 1...
Esto se usa como dije para el cauclo de d (pero con N = phi(n))
Ademas para que exista x se cumple qeu

 gdc(a, n) = 1 (son coprimos)

Esto se demuesta como:
  supongoamos que d = gdc(a, n) = d > 1 osea a o n son compuestos
  entonces:
   a | d  y  n | d

  Por contradicion digmoas que si existe un inversox que cumpla es decir

 a*x = 1 (mod N)

 Usando una propeida que meicone antes eso quere deicr que

  (ax-1) / n  da una division exacta

  por lo que (usando la deinficno de division)

  (ax-1) = n *  y  (donde y es un entero)

  rescribiendo:

  ax-ny=1

  pero tambein  =  a  = d * k   y n  = d * z

  (dk)x - (dz)y = 1

  d(kx - zy) = 1

  o

  d *  j  = 1

  eso quiere decir qeu si multoapcl d por un numero J nos da 1..
  pero dijisqmos que D > 1
  enotnces no eixtne ningun numero en este sistema que si lo multpcloas por d nos de 1
  por ejemplo si d fuera 2 * x = 1   x debria de ser  1/2 pero dijismos que eso no eixte
  en este sitema

  Aparte ioncialete dijismoq que para que d¨*j sea vlaidao para  en caso exista
  dicho inverso neceisaria d=1
  lo cual unciamte se cumple para coprimos..

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
  // Inverso modular
  // En aritmaetica modular que luego se usa en RSA por jemeplo
  // Neceistmoas un inverso x que se deifne como
  // (x*a) = 1  (MOD n)
  // Osea un numero x que al multiplcarlo por 1 y esto lo dividmos por n
  // su resto sea 1
  // para esto se cumple que gdc(n,a)=1 osea n y a son coprimos
  // Ahora para encontralo usaremos un teroema del gdc:
  // tal que:
  // gdc(a,b) = ax+by
  // En nuestro caso como defines qeu el gdc=1
  // entonces:
  // ax+by=1
  // ahora:
  // a=this,  b=n (mod)
  // si lo ecrimos como un mod
  // ax+by = 1  (MOD n)
  // pero
  // this * x + n * y = 1  (mod n)  ny es multiplo de N
  // por loq ue n * y no afecta en esta operacion (es como que da una veulta completa)
  // asi que this * x = 1  (mod n)  justo lo qeu buscamosm incialete
  // entonces esta funcino retorna dicho x




//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
 El gdc ext, como lo he llegado a comprender en su forma simple, es basicamnte lo mismo que el gdc bin normal
 solo que en vez de llevar dos varaibles u\v, llevas  A\B\C\D los coeficintes de las dos ecuaciones
  ll A = 1, B = 0;    u = A*a0 + B*b0 
  ll C = 0, D = 1;    v = C*a0 + D*b0 
  
  La idea, es la misma que el bin pero trabajmos como si lo estiamso hacienco con una ecuacion como la que se muestra
  osea que en los pasos como u-=v esa resta se hace "a nivel" de ecuacion tal que
  
  u-v = A*a0 + B*b0 - C*a0 + D*b0
  
  Y asi... en la parte de ">> 1" donde volvemos impar a U aplica lo mismo. tenermos que ir acutlziando los coeficinestes
  ahora la pregunta? por que A\B\C\D basicamnte por que el gdc bin devolvimaos el "resto previo" pero 
  ahora se nos pide esto:  ax+by osea como una euccion con dos varialbes x\y y es basicamnte el sistema
  en el que estamos trabajando... por eso al final del bucle
  
  X e Y temrinadn ciendo C\D los coeficientes que recontruyen v... basiamtne esos coefiintges nos dicen
  el numero de veces que mulpacio el a y b orignal y sumado ambos procuocts nos da el v actua...
  y como el gdc es ese mismo v.. enotnces justo ahi tenemos la respeusta dado que tenemos su forma de reoncutrirslo
  
  en resumen trabajsmo igual qeu el bin pero como "ecuiaciones" con sus coeficinete
  sluego esos mismo coeficintes seran el x\y final que devolveremos
  
  tambien podemos verlo como un sistema de eucaicon matricial
  (  
    u,
    v 
  )
  
  y la matriz de coeficientes
  (
    a  b
    c  d
         )
   pero baimante es eso en vez de u\v piensacol como lo mismo pero trabajcon con una euccion
   entonces cada cosa que hagmos con u\v tendremos que ir acutlizaion los coeifinces que nos dan la respuesta
   
   
  en c:
  
  ll euclides_extendido_binario(ll a, ll b, ll *x, ll *y)
 {
  if(a == 0)
   {
    *x = 0;
    *y = 1;
    return b;
   }
  if(b == 0)
   {
    *x = 1;
    *y = 0;
    return a;
   }

  int negA = a < 0, negB = b < 0;
  if(negA)
    a = -a;
  if(negB)
    b = -b;


  int shift = 0;
  while(es_par(a) && es_par(b))
   {
    a >>= 1;
    b >>= 1;
    shift++;
   }

  ll a0 = a, b0 = b;
  ll u = a, v = b;
  ll A = 1, B = 0;   
  ll C = 0, D = 1;  

  while(u != 0)
   {
    while(es_par(u))
     {
      u >>= 1;
      if(es_par(A) && es_par(B))
       {
        A >>= 1;
        B >>= 1;
       }
      else
       {
        A = (A + b0) >> 1;
        B = (B - a0) >> 1;
       }
     }

    while(es_par(v))
     {
      v >>= 1;
      if(es_par(C) && es_par(D))
       {
        C >>= 1;
        D >>= 1;
       }
      else
       {
        C = (C + b0) >> 1;
        D = (D - a0) >> 1;
       }
     }

    if(u >= v)
     {
      u -= v;
      A -= C;
      B -= D;
     }
    else
     {
      v -= u;
      C -= A;
      D -= B;
     }
   }

  ll gcd = v << shift;

  *x = negA ? -C : C;
  *y = negB ? -D : D;
  return gcd;
 }        

 
 
 //+------------------------------------------------------------------+
 //|                                                                  |
 //+------------------------------------------------------------------+
       /*
      El metodo dos parte de interpeteat a:
      a*b
      como dos polinomios
      a=a1*x^m+a0
      b=b1*x^m+b0

      donde:
      a1=parte alta
      a0=parte baja
      x=base
      m=(numero de digitos del numero en si entre 2)

      Esto es posible dado que expresamos el numero como dos partes (tipo) notacion
      cientiica una base elevado a la mitad de digitiso*valorbajo + valor ato ejemplo
      120000 ()
      x=10
      m=3 (6/2)
      a=120*10^3+0=120000

      Ahora si mulltiplacas estos dos polinomios tal que:
      a*b= (a1*x^m+a0) * (b1*x^m+b0)
      =
            (a1*x^m+a0) *
            (b1*x^m+b0)
       --------------------
      = (a1*x^m)(b1*x^m)+a0(b1*x^m)+b0(a1x^m)+(a0b0)
      Ahora reordenamos

      a1b1x^m2+a0(b1*x^m)+b0(a1x^m)+(a0b0)

      Podemos sacar a x^m como factor comun ahi
      x^m(a0b1+b0a1)

      Queda:

      a1b1x^m2+x^m(a0b1+b0a1)+a0b0

      Ahora la idea por lo qeu entendi es que ahora mismo estasmo ejecutnado una multiplacion de toda la vida
      ahora la idea es simplificar
      para eso (a0b1+b0a1) esto que podemos verlo como (ab+cd) tenemos aqui 4 terminos..
      diferentes por lo qeu no podemos factoriuzalo lo qeu si es que podemos aprovechar
      algo interesante:
      (a+b)(c+d) = ac+ad+bc+bd
      Esto es multiplacion de binomios..
      la idea e sque si interpatmaos ese a0b1+b0a1 como eso nos da:

      (a0+a1)(b0+b1) =
      a0b0+a0b1+a1b0+a1b1

      Nota que eligmos esa convinacion para poder aplicar el truco que usaremos ahora
      Esto si te das cuenta ciertas partes ya las tenemos... a0b0 y b1a1 ya los tenemso calculados
      entonces renombrando:

      (a0+a1)(b0+b1) = z0 + a0b1+a1b0 + z2

      donde:
        z2 = b1a1
        z0 = a0b0
      reordenmoas la parte izq:

      = (a0b1+a1b0) + z0 + z2   (no imprta el orden dado que es suma propiedad comutativa)

      ahora pasamos al otro lado

      z2 - z0 - (a0+a1)(b0+b1) = a0b1+a1b0

      o tambien:

      a0b1+a1b0 =  (a0+a1)(b0+b1) - z0 - z2

      bueno entonces con eso ya podemos calucalr lo que nos falta para tener z1 con 3 multiplaciones
      (z0, z2 y la de ()()) en vez de 4...


      entcones la funcion seira algo asi

      primero calcullkos z0 y z2 primero eso y luego z1 (a0b1+a1b0)
      sale claucalos = (a0+a1)(b0+b1) - z0 - z2

      luego de eso aplicas el x^m

      Ejemplo multipllacar

      10
      45

      x=10
      m=1


      a = 1*10^1+0 , osea que a1=1, a0=0
      b = 4*10^1+5 , osea que b1=4, b0=5

      calculomoes z0 (b1a1 ) y z2 (a0b0)

      z0=1*4=4
      z2=0*5=0

      ahora z1

      z1=(a0+a1)(b0+b1) - z0 - z2

      remplazando:

      (0+1)(5+4) - 0 - 4
      (1)(9) - 0 - 4
      9 - 0 - 4
      9 - 4
      z1=5

      final remplzamos en:



      z0x^m2+x^mz1+z2 = 4*100+10*5+0= 400 + 50 + 0 = 450
      */


*/
//+------------------------------------------------------------------+