Интервальные методы перевода — различия между версиями

Материал из Модулярная арифметики
Перейти к: навигация, поиск
 
(не показана одна промежуточная версия этого же участника)
Строка 16: Строка 16:
  
  
:<math>{P_i}^{\phi(p_i)} \equiv 1\pmod p_i</math> (3),
+
:<math>{P_i}^{\varphi(p_i)} \equiv 1\pmod {p_i}</math> (3),
  
  
где <math>\phi(p_i)</math> - – функция Эйлера.  
+
где <math>\varphi(p_i)</math> - – функция Эйлера.  
Причём если <math>p_i</math> – простое число, то <math>\phi(p_i) = p_i - 1</math>.  
+
Причём если <math>p_i</math> – простое число, то <math>\varphi(p_i) = p_i - 1</math>.  
  
 
   
 
   
Строка 26: Строка 26:
  
  
:<math>A = \left| \sum _{i = 1}^{n} {P_i}^{\phi(p_i)} \cdot \alpha_i \right| \pmod P</math> (4).
+
:<math>A = \left| \sum _{i = 1}^{n} {P_i}^{\varphi(p_i)} \cdot \alpha_i \right| \pmod P</math> (4).
  
 
Для определения номера интервала <math>l_A</math>, подставим выражение (4) в (1):
 
Для определения номера интервала <math>l_A</math>, подставим выражение (4) в (1):
  
 
:<math>l_A = \left [\frac {A}{p_i}\right ]</math>
 
:<math>l_A = \left [\frac {A}{p_i}\right ]</math>

Текущая версия на 13:00, 23 января 2015

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

Рассмотрим СОК, заданную системой оснований 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 ] (1),

в котором находится число A, и по цифре \alpha_i числа A в СОК по модулю p_i, т.е.


A = p_i \cdot l_A + {\alpha}_i (2).


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


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


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


Число A можно представить в виде


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

Для определения номера интервала l_A, подставим выражение (4) в (1):

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