Racionální rekonstrukce (matematika) - Rational reconstruction (mathematics)

V matematice racionální rekonstrukce je metoda, která umožňuje obnovit a racionální číslo z jeho hodnoty modulo A dostatečně velký celé číslo.

Problémové prohlášení

V problému racionální rekonstrukce je jedna uvedena jako hodnota vstupu ${ displaystyle n equiv r / s { pmod {m}}}$. To znamená,${ displaystyle n}$ je celé číslo s vlastností, která ${ displaystyle ns equiv r { pmod {m}}}$. Racionální číslo ${ displaystyle r / s}$ není známo a cílem problému je získat jej z dané informace.

Aby byl problém řešitelný, je nutné předpokládat, že modul ${ displaystyle m}$ je dostatečně velký vzhledem k ${ displaystyle r}$ a ${ displaystyle s}$Typicky se předpokládá, že rozsah možných hodnot ${ displaystyle r}$ a ${ displaystyle s}$ je známo: ${ displaystyle | r |$ a ${ displaystyle 0$ pro některé dvojčíselné parametry ${ displaystyle N}$ a ${ displaystyle D}$. Kdykoli ${ displaystyle m> 2ND}$ a existuje řešení, je jedinečné a lze ho najít efektivně.

Řešení

Je možné se vzpamatovat ${ displaystyle r / s}$ z ${ displaystyle n}$ a ${ displaystyle m}$ za použití Euklidovský algoritmus, jak následuje.^[1][2]

Jeden dává ${ displaystyle v = (m, 0)}$ a ${ displaystyle w = (n, 1)}$. Jeden pak opakuje následující kroky, dokud první složka z w se stává ${ displaystyle leq N}$. Dát ${ displaystyle q = left lfloor { frac {v_ {1}} {w_ {1}}} right rfloor}$, dát z = proti − Q w. Nové proti a w jsou pak získány uvedením proti = w a w = z.

Pak s w takhle ${ displaystyle w_ {1} leq N}$, jeden dá druhou složku pozitivní kladením w = −w -li ${ displaystyle w_ {2} <0}$. Li ${ displaystyle w_ {2}$ a ${ displaystyle gcd (w_ {1}, w_ {2}) = 1}$, pak zlomek ${ displaystyle { frac {r} {s}}}$ existuje a ${ displaystyle r = w_ {1}}$ a ${ displaystyle s = w_ {2}}$, jinak žádná taková část neexistuje.

Reference