forked from nique_372/BigNumberByLeo
136 lines
4.2 KiB
MQL4
136 lines
4.2 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
|
|
|
|
*/
|
|
//+------------------------------------------------------------------+
|