 Autor
|
Tema: [Matemática] Resolviendo sistemas de ecuaciones lineales modulares. (Leído 8,697 veces)
|
APOKLIPTICO
 Desconectado
Mensajes: 3.871
Toys in the attic.
|
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
Mensajes: 3.871
Toys in the attic.
|
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
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
¡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
Mensajes: 3.871
Toys in the attic.
|
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
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
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
Mensajes: 3.871
Toys in the attic.
|
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
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
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
Mensajes: 3.871
Toys in the attic.
|
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
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
¡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
Mensajes: 3.871
Toys in the attic.
|
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.
|
|
|
|
| Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
|
Resolucion de sistemas de ecuaciones sencillos
Java
|
Debci
|
6
|
7,301
|
1 Abril 2010, 15:58 pm
por Debci
|
|
|
|
Ecuaciones Diferenciales de orden superior homogeneas lineales
Foro Libre
|
¡Micronet!
|
0
|
2,072
|
16 Octubre 2010, 03:38 am
por ¡Micronet!
|
|
|
|
Desarrollo y despliegue de Sistemas Modulares
Programación Visual Basic
|
airknightz
|
0
|
1,242
|
5 Diciembre 2013, 16:32 pm
por airknightz
|
|
|
|
S.O.S : Programa que solucione sistemas Lineales x método de Gauss :)
Programación C/C++
|
Bachanilorac
|
1
|
2,174
|
20 Noviembre 2014, 21:13 pm
por avesudra
|
|
|
|
Resolución de sistemas de ecuaciones lineales de grado "n"
Programación C/C++
|
fzp
|
0
|
2,243
|
30 Diciembre 2021, 22:38 pm
por fzp
|
 |
