Интервальные методы перевода

Материал из Модулярная арифметики
Версия от 16:55, 22 октября 2014; Isaeva (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Достаточно эффективными методами перевода чисел из СОК в ПСС являются интервальные методы, основанные на интервальных характеристиках чисел. Одна из таких характеристик – номер интервала.

Рассмотрим СОК, заданную системой оснований p_1, p_2, \ldots, p_n с объёмом диапазона P = p_1\cdot p_2\cdot \ldots \cdot p_n. Выберем дробящий модуль p_i и проведём дробление заданного диапазона на интервалы путём деления P на модуль p_i. Тогда количество интервалов m = P_i = \frac {P}{p_i}, а длина интервала определяется величиной модуля.

В результате величину любого числа A, заданного в СОК по выбранным основаниям, можно определить по номеру интервала:

l_A = \left [\frac {A}{p_i}\right ],

в котором находится число A и по цифре \alpha_i числа A в СОК по модулю p_i, т.е. A = p_i \cdot l_A + {\alpha}_i.


Так как (p_i, P_i) = 1, то по теореме Эйлера:

{P_i}^{\phi(p_i)} \equiv 1\pmod p_i,

где \phi(p_i) - – функция Эйлера. Причём если p_i – простое число, то \phi(p_i) = p_i - 1.

Подставляя выражение для A в ..., получаем

A = \left| \sum _{i = 1}^{n} {P_i}^{\phi(p_i)} \cdot \alpha_i \right| \pmod P

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация