1 respuesta
Espero que tu sepas inglés porque yo no me entero de nada. Deduzco lo que dicen por el ejemplo que hay en la pegunta 4.
Aquí hablan primero de el módulo sea primo
ax:~ b (mod p)
Entonces dicen que hay que multiplicar la congruencia por el entero más cercano a p/a, luego se restan las cantidades múltiplos de p y tenemos que llegar a un número a' tal que
|a'| <= |a|/2
Se repite el proceso varias veces y cada vez a es más pequeño hasta que sea 1 (o -1 supongo). Y el numero de pasos a dar no es mayor que el logaritmo en base 2 de a
Veamos un ejemplo
18x :~ 19 (mod 79)
79/18 = 4.38...
el entero más cercano es 4 multiplicamos por él
72x :~ 76 (mod 79)
Ahora sustituimos 72 por el número congruente 72-79 = -7 ya que consiste en que a disminuya lo máximo posible en valor absoluto, el signo no importa. Por eso mismo también sustituiremos 76 por 76-79=-3
-7x :~ -3 (mod 79)
Ahora 79/(-7) = -11.28... Tomamos -11 y multiplicamos por él
77x :~ 33 (mod 79)
Reducimos restando 79 donde haga falta
-2x :~ 33 (mod 79)
Ahora 79/2 = -39.5 tomaremos el -40 me gusta más
80x :~ -1320 (mod 79)
Reducimos el primer coeficiente
X :~ -1320 (mod 79)
No habría ningún problema en dar -1320 como respuesta, lo que pasa es que parece mas elegante dar la respuesta que está en el intervalo 0 a 78, para ello hay que sumar un múltiuplo de 79
1320/ 79 = 16.70...
Le sumaremos 17·79 = 1343
-1320+1343 = 23
Luego x=23, vamos a comprobarlo, recuerdo que la ecuación inicial es
18x :~ 19 (mod 79)
18·23 = 414
414 /79 = 5.24...
414 - 5·79 = 414 - 395 = 19
Luego está bien la solución.
Y eso es todo.
