elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: AIO elhacker.NET 2021 Compilación herramientas análisis y desinfección malware


+  Foro de elhacker.net
|-+  Foros Generales
| |-+  Foro Libre (Moderador: Kasswed)
| | |-+  [Matemática] Resolviendo sistemas de ecuaciones lineales modulares.
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [Matemática] Resolviendo sistemas de ecuaciones lineales modulares.  (Leído 7,494 veces)
APOKLIPTICO


Desconectado Desconectado

Mensajes: 3.871


Toys in the attic.


Ver Perfil
[Matemática] Resolviendo sistemas de ecuaciones lineales modulares.
« en: 1 Diciembre 2010, 02:52 am »

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.
En línea

AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
APOKLIPTICO


Desconectado Desconectado

Mensajes: 3.871


Toys in the attic.


Ver Perfil
Re: [Matemática] Resolviendo sistemas de ecuaciones lineales modulares.
« Respuesta #1 en: 2 Diciembre 2010, 03:40 am »

Nadie chee?? Uhh, que mal q andamos...
En línea

AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: [Matemática] Resolviendo sistemas de ecuaciones lineales modulares.
« Respuesta #2 en: 2 Diciembre 2010, 04:11 am »

¡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!
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
APOKLIPTICO


Desconectado Desconectado

Mensajes: 3.871


Toys in the attic.


Ver Perfil
Re: [Matemática] Resolviendo sistemas de ecuaciones lineales modulares.
« Respuesta #3 en: 2 Diciembre 2010, 11:41 am »

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".
En línea

AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: [Matemática] Resolviendo sistemas de ecuaciones lineales modulares.
« Respuesta #4 en: 4 Diciembre 2010, 19:36 pm »

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

¡Saludos!
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
APOKLIPTICO


Desconectado Desconectado

Mensajes: 3.871


Toys in the attic.


Ver Perfil
Re: [Matemática] Resolviendo sistemas de ecuaciones lineales modulares.
« Respuesta #5 en: 4 Diciembre 2010, 19:55 pm »

Tengo infinitos xi, pero como la resuelvo? como es el algoritmo?
En línea

AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: [Matemática] Resolviendo sistemas de ecuaciones lineales modulares.
« Respuesta #6 en: 4 Diciembre 2010, 22:27 pm »

Pues si tienes infinitos xi, es bien sencillo. Llamando x0 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 Zm Es decir

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

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

¡Saludos!
 
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
APOKLIPTICO


Desconectado Desconectado

Mensajes: 3.871


Toys in the attic.


Ver Perfil
Re: [Matemática] Resolviendo sistemas de ecuaciones lineales modulares.
« Respuesta #7 en: 5 Diciembre 2010, 01:40 am »

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!!!
« Última modificación: 5 Diciembre 2010, 02:13 am por APOKLIPTICO » En línea

AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: [Matemática] Resolviendo sistemas de ecuaciones lineales modulares.
« Respuesta #8 en: 5 Diciembre 2010, 03:51 am »

¡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 Zm 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 Zm, 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!
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
APOKLIPTICO


Desconectado Desconectado

Mensajes: 3.871


Toys in the attic.


Ver Perfil
Re: [Matemática] Resolviendo sistemas de ecuaciones lineales modulares.
« Respuesta #9 en: 5 Diciembre 2010, 05:17 am »

Guau, acabás de hacer renacer mis conocimientos de álgebra jajaja.
En línea

AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines