393 lines
10 KiB
MQL4
393 lines
10 KiB
MQL4
//+------------------------------------------------------------------+
|
|
//| 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
|
|
*/
|
|
|
|
|
|
*/
|
|
//+------------------------------------------------------------------+
|