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

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

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

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

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

Решение

Возможно выздоровление ${\displaystyle r/s}$ из ${\displaystyle n}$ и ${\displaystyle m}$ с использованием Евклидов алгоритм, следующее.^[1][2]

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

Затем с ш такой, что ${\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}}$, иначе такой дроби не существует.

Рекомендации

1. Ван, Пол С. (1981), "p-адический алгоритм для одномерных частичных дробей", Труды Четвертого Международного симпозиума по символьным и алгебраическим вычислениям (SYMSAC '81), Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники, стр. 212–217, Дои:10.1145/800206.806398, ISBN  0-89791-047-8
2. Wang, Paul S .; Гай, М. Дж. Т.; Давенпорт, Дж. Х. (Май 1982 г.), "П-адическая реконструкция рациональных чисел", Бюллетень SIGSAM, Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники, 16 (2): 2–3, CiteSeerX  10.1.1.395.6529, Дои:10.1145/1089292.1089293.