Cálculo del inverso modular en JavaScript

Hola, hemos encontrado la respuesta a tu interrogante, desplázate y la encontrarás a continuación.

Solución:

Estaba revisando la definición de inverso multiplicativo modular y por lo que entiendo:

ax = 1 (mod m)
=> m is a divisor of ax -1 and x is the inverse we are looking for
=> ax - 1 = q*m (where q is some integer)
And the most important thing is gcd(a, m) = 1
i.e. a and m are co-primes

En tu caso:

ed = 1 mod((p-1)(q-1)) //p, q and e are given 
=> ed - 1 = z*((p-1)(q-1)) //where z is some integer and we need to find d

Nuevamente, a partir de la entrada de wikipedia, se puede calcular el inverso modular utilizando el algoritmo GCD euclidiano extendido que hace lo siguiente:

 ax + by = g //where g = gcd(a,b) i.e. a and b are co-primes
 //The extended gcd algorithm gives us the value of x and y as well.

En su caso, la ecuación sería algo como esto:

 ed - z*((p-1)(q-1)) = 1; //Compare it with the structure given above

 a -> e
 x -> d
 b -> (p-1)(q-1)
 y -> z

Entonces, si aplicamos ese algoritmo a este caso, obtendremos los valores de d y z.

Para ax + by = gcd(a,b), el algoritmo gcd extendido podría parecerse a (fuente):

 function xgcd(a, b)  

   if (b == 0) 
     return [1, 0, a];
   

   temp = xgcd(b, a % b);
   x = temp[0];
   y = temp[1];
   d = temp[2];
   return [y, x-y*Math.floor(a/b), d];
 

Este algoritmo se ejecuta en el tiempo O (registro (m) ^ 2), asumiendo | a |

No sé si hay una función incorporada para esto en javascript. Dudo que lo haya, y soy un fanático de los algoritmos, así que pensé que tal vez querría probar este enfoque. Puede manipularlo y cambiarlo para manejar su rango de valores y espero que lo ayude a comenzar en la dirección correcta.

Esta implementación de inverso modular puede aceptar cualquier tipo de entradas. Si los tipos de entrada no son compatibles, NaN es regresado. Además, no utiliza la recursividad.

function modInverse(a, m)  Number.isNaN(m)) 
    return NaN // invalid input
  
  a = (a % m + m) % m
  if (!a 

// Tests
console.log(modInverse(1, 2))       // = 1
console.log(modInverse(3, 6))       // = NaN
console.log(modInverse(25, 87))     // = 7
console.log(modInverse(7, 87))      // = 25
console.log(modInverse(19, 1212393831))     // = 701912218
console.log(modInverse(31, 73714876143))    // = 45180085378
console.log(modInverse(3, 73714876143))     // = NaN
console.log(modInverse(-7, 87))     // = 62
console.log(modInverse(-25, 87))    // = 80
console.log(modInverse(0, 3))       // = NaN
console.log(modInverse(0, 0))       // = NaN

Comentarios y calificaciones de la guía

---

---

Utiliza Nuestro Buscador