Reconstrucción racional (matemáticas)

En matemáticas, la reconstrucción racional es un método que permite recuperar un número racional a partir de su valor módulo un número entero suficientemente grande .

Planteamiento del problema

En el problema de reconstrucción racional, se le da como entrada un valor . Es decir, es un número entero con la propiedad de que . Se desconoce el número racional y el objetivo del problema es recuperarlo a partir de la información dada. ${\displaystyle n\equiv r/s{\pmod {m}}}$ ${\displaystyle n}$ ${\displaystyle ns\equiv r{\pmod {m}}}$ ${\displaystyle r/s}$

Para que el problema tenga solución, es necesario suponer que el módulo es suficientemente grande en relación con y . Normalmente, se supone que se conoce un rango para los posibles valores de y : y para algunos dos parámetros numéricos y . Siempre que existe una solución, la solución es única y se puede encontrar de manera eficiente. ${\displaystyle m}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle |r|<N}$ ${\displaystyle 0<s<D}$ ${\displaystyle N}$ ${\displaystyle D}$ ${\displaystyle m>2ND}$

Solución

Utilizando un método de Paul S. Wang , es posible recuperarse y utilizar el algoritmo euclidiano , de la siguiente manera. ^{[1] [2]} ${\displaystyle r/s}$ ${\displaystyle n}$ ${\displaystyle m}$

Se pone y . Luego se repiten los siguientes pasos hasta que el primer componente de w se convierta en . Ponga , ponga z = v  −  qw . Los nuevos v y w se obtienen poniendo v = w y w = z . ${\displaystyle v=(m,0)}$ ${\displaystyle w=(n,1)}$ ${\displaystyle \leq N}$ ${\displaystyle q=\left\lfloor {\frac {v_{1}}{w_{1}}}\right\rfloor }$

Entonces con w tal que , uno hace que el segundo componente sea positivo poniendo w = − w if . Si y , entonces la fracción existe y y , en caso contrario no existe tal fracción. ${\displaystyle w_{1}\leq N}$ ${\displaystyle w_{2}<0}$ ${\displaystyle w_{2}<D}$ ${\displaystyle \gcd(w_{1},w_{2})=1}$ ${\displaystyle {\frac {r}{s}}}$ ${\displaystyle r=w_{1}}$ ${\displaystyle s=w_{2}}$

Referencias

1. Wang, Paul S. (1981), "Un algoritmo p-adic para fracciones parciales univariadas", Actas del Cuarto Simposio Internacional sobre Computación Simbólica y Algebraica (SYMSAC '81) , Nueva York, NY, EE. UU.: Association for Computing Machinery , págs. 212–217, doi :10.1145/800206.806398, ISBN 0-89791-047-8, S2CID  10695567
2. Wang, Paul S.; chico, MJT ; Davenport, JH (mayo de 1982), "Reconstrucción P-adic de números racionales", Boletín SIGSAM , 16 (2), Nueva York, NY, EE. UU.: Association for Computing Machinery: 2–3, CiteSeerX 10.1.1.395.6529 , doi :10.1145/1089292.1089293, S2CID  44536107 .