Рациональная реконструкция (математика)

В математике рациональная реконструкция — это метод, позволяющий восстановить рациональное число по его значению по модулю числа достаточно большого целого .

Постановка задачи

В задаче рациональной реконструкции в качестве входных данных задается значение $n\equiv r/s{\pmod {m}}$. То есть, $n$ целое число со свойством, которое $ns\equiv r{\pmod {m}}$. Рациональное число $r/s$ неизвестно,и цель задачи — восстановить его по заданной информации.

Для того чтобы задача была разрешима, необходимо предположить, что модуль $m$ достаточно велика по отношению к $r$ и $s$.Обычно предполагается, что диапазон возможных значений $r$ и $s$ известно: $|r|<N$ и $0<s<D$ где-то на двоихчисловые параметры $N$ и $D$. В любое время $m>2ND$ и решение существует, оно уникально и может быть найдено эффективно.

Решение

Используя метод Пола С. Ванга , можно восстановить $r/s$ от $n$ и $m$ используя алгоритм Евклида , следующим образом.

Один ставит $v=(m,0)$ и $w=(n,1)$. Затем повторяются следующие шаги до тех пор, пока первый компонент w не станет $\leq N$. Помещать $q=\left\lfloor {\frac {v_{1}}{w_{1}}}\right\rfloor$, положим z знак равно v - qw . Новые v и w затем получаются путем помещения v = w и w = z .

Тогда с w таким, что $w_{1}\leq N$, вторую компоненту можно сделать положительной, положив w = − w , если $w_{2}<0$. Если $w_{2}<D$ и $\gcd(w_{1},w_{2})=1$, то дробь ${\frac {r}{s}}$ существует и $r=w_{1}$ и $s=w_{2}$, иначе такой дроби не существует.