Рациональная реконструкция (математика)
- Рациональная реконструкция — метод восстановления рационального числа по его значению по модулю большого целого числа.
- Задача реконструкции задается значением n ≡ r/s (модификация m).
- Цель проблемы — восстановить неизвестное рациональное число r/s из предоставленной информации.
- Для разрешимости задачи необходимо предположить, что модуль m достаточно большой по отношению к r и s.
- Предполагается, что диапазон возможных значений r и s известен.
- Решение существует, уникально и может быть найдено эффективно при определенных условиях.
- Метод, предложенный Полом С. Ван, использует евклидов алгоритм для исправления r/s от n и m.
- Процесс решения включает вычисление новых v и w, проверку существования дроби r/s и определение ее значений.
Полный текст статьи: