Foro de elhacker.net

Hola!
Como va todo? Primero perdón a Kass si esto no va aquí (aunque técnicamente cualquier cosa puede ir aqui), pero realmente no se me ocurría donde ponerlo, no va en criptografía, no va en wargames, no va en programación y tampoco daba ponerlo en dudas generales porque realmente no está asociado diréctamente con la computación.

Bueno, mi duda en cuestión es sobre sistemas de ecuaciones lineales modulares.
Tengo una ecuación asi:
(x*a + k) mod m = y.

Tengo "m", tengo "x" y tengo "y". De hecho tengo múltiples "x" e "y".
Entonces se podría armar un sistema de ecuaciones asi:
(x1*a + k) mod m = x2.
(x2*a + k) mod m = x3.
...
...
(xn*a + k) mod m = x(n+1).

Necesito conseguir "a" y "k".
Hay algun algoritmo mas o menos simple para conseguirlo? (que no sea fuerza bruta claro).

Gracias!
APOKLIPTICO.

Nadie chee?? Uhh, que mal q andamos...

¡Buenas!

No se exactamente cual es la descripcion del problema.

¿x e y son vectores? ¿Es un problema recursivo? Si el problema es recursivo, igual lo puedes transformar en un sistema con una matriz mas sencilla con teoria del endomorfismo (matrices canonicas) o aplicando valores y vectores propios (diagonalizacion)...

Este tema lo tengo algo oxidado, pero deberias mirar el Teorema Chino de los restos. Te da la manera de solucionar sistemas de ecuaciones modulo m. Si quieres entender la demostracion, tendras que estudiar sobre ideales (si mal no recuerdo).

Si alguien tiene informacion mas concreta yo tambien se lo agradeceria, que como ya he dicho, eso lo tengo algo oxidado. Aunque ahora que lo has dicho, alguno de estos dias, cuando tenga tiempo, refrescare la memoria.

¡Saludos!

Para ser más claro, tengo un generador pseudo aleatorio, conocido como generador lineal congruencial.
La fórmula es la siguiente:
(x[n]*a + k) mod m = x[n+1].
(x[n+1]*a + k) mod m = x[n+2].
(x[n+2]*a + k) mod m = x[n+3].
y así sucesivamente.

Tengo el módulo "m". Y tengo que conseguir a y k para luego conseguir el "x0".

Si tienes los x_i, con dos de las 3 ecuaciones tienes suficiente. Si no conoces los x_i, entonces tienes mas incognitas que ecuaciones, y por lo tanto, el resultado dependera de algun(os) parametro(s).

¡Saludos!

Tengo infinitos xi, pero como la resuelvo? como es el algoritmo?

Pues si tienes infinitos x_i, es bien sencillo. Llamando x₀ al primero que tengas tienes estas dos ecuacion con incognitas a y k:

si tenemos c, denotaremos c' = c mod m

x1' = x0' a' + k'
x2' = x1' a' + k'

Que tiene como matriz

[x0' 1 | x1']
[x1' 1 | x2']

Dos ecuaciones con dos incognitas. Resuelvelo y ya tienes tu respuesta.

Ten en cuenta que tomar modulo mantiene las operaciones de anillo que hay en Z en Z_m Es decir

(a·b) mod m = a' b'
(a + b) mod m = a' + b'

Si obtienes como solucion de la ecuacion a₀ y k₀ cualquier a y k de la forma a⁰ + t*m , k⁰ + t*m, seran solucion de la ecuacion.

¡Saludos!
 

A ver, entonces yo tengo:
a * x0 + k = x1
a * x1 + k = x2

Igualo: a * x0 - x1 = a * x1 - x2.

Despejo a: a = (x1 - x2) / (x0-x1)

Pero eso aplicado:
x0 = 1723159081
x1 = 170289050
x2 = 1599923671
m = 2147483647

x1 - x2 mod m = 717849026
x0 - x1 mod m = 1552870031

Ahora, el tema es en la división...
A menos claro que la división modular sea otra cosa...
Que haya que multiplicarlo por el inverso modular de x0-x1 mod m.
Usando el caso especial del teorema de euler, que dice que cuando "m" es primo:
a^-1 = a^(m-2)
a = 1473215338.

Entonces: 717849026 * 1473215338 mod m = 16807. Que efectivamente era el "a" inicial.
Genial..
Ahora entonces.
k = x1- a * x0.
(16807*1723159081) mod m = 170210925.
1723159081 - 170210925 = 1552948156.

Ahora, el valor que estaba buscando, era 78125, que es lo que está fallando?

PD: Me equivoqué en la segunda cuenta. Error estúpido.
170289050 - 170210925  = 78125 (OK!)

PD2: GRACIAS!!!

¡Buenas!

Solo un detalle en tu razonamiento. Solamente existe inverso para el producto dentro del mismo anillo si m es primo, ya que en este caso Z_m es cuerpo y por lo tanto dentro de el abra inverso para el producto para cualquier elemento distinto de cero.

Si m no fuese primo, existiria al menos un elemento si m fuese un cuadrado, si no fuese un cuadrado al menos habria dos elementos distintos dentro de Z_m, cuyo producto seria m, y por lo tanto el producto de ambos seria cero (m = 0 mod m). Estos elementos no tendrian inverso para el producto.

Supongamos que ab=m con a y b != 0.

Si exitiese a^-1, se tendria que:

a^-1ab = a^-1m

(a^-1a)b = a^-1·0

1·b = 0

b = 0

Lo cual es una contradiccion. Por lo tanto ni a ni b tienen inverso para el producto.

De ahi la importancia de trabajar modulo un primo.

¡Saludos!

PD: Me alegra que lo que te he dicho te haya servido!

¡Saludos!

Guau, acabás de hacer renacer mis conocimientos de álgebra jajaja.