Алгоритмы модулярной арифметики

Если взять некое множество взаимно простых натуральных чисел m₁, m₂, …, m_r и число u, меньшее произведения m=m₁∙m₂∙…∙m_r, то u однозначно представимо остатками этого числа (u₁, u₂, …, u_r), где u₁=u mod m₁, u₂=u mod m₂, …, u_r=u mod m_r. И наоборот, совокупности остатков соответствует единственное число по модулю m. Другими словами, между числами u в указанном интервале и совокупностью его остатков по заданным модулям есть взаимно-однозначное соответствие:

u ↔ (u₁, u₂, …, u_r).

Считаем, что если целое число u рассматривается как (u₁, u₂, …, u_r), то оно имеет модулярное представление.

Операциям сложения, вычитания и умножения с числами u и v по модулю m соответствуют покомпонентные операции с их остатками по заданным взаимно простым модулям m₁, m₂, …, m_r. Утверждается, что если u ↔ (u₁, u₂, …, u_r) и v ↔ (v₁, v₂, …, v_r), то

(u+v) mod m ↔ ((u₁+v₁) mod m₁, (u₂+v₂) mod m₂, …, (u_r+v_r) mod m_r),

(u – v) mod m ↔ ((u₁–v₁) mod m₁, (u₂–v₂) mod m₂, …, (u_r–v_r) mod m_r),

(u∙v) mod m ↔ ((u₁∙v₁) mod m₁, (u₂∙v₂) mod m₂, …, (u_r∙v_r) mod m_r).

Пример. Пусть m₁=3, m₂=7 и m₃=31. Числа от 0 до 3∙7∙31–1=650 единственным образом представимы через совокупность остатков по данным модулям. Так для чисел 9, 53, 478 имеем: 9=(0, 2, 9), 53=(2, 4, 22), 478=(1, 2, 13).

53+9=62 → (2, 4, 22) + (0, 2, 9) = (2+0, 4+2, 22+9) = (2, 6, 0).

53–9=44 → (2, 4, 22) – (0, 2, 9) = (2–0, 4–2, 22–9) = (2, 2, 13).

53∙9=477 → (2, 4, 22) ∙ (0, 2, 9) = (2∙0, 4∙2, 22∙ 9) = (0, 1, 12).

Применим схему вычисления, основанную на китайском алгоритме об остатках, например, к системе сравнений , что соответствует выполненной операции вычитания над остатками. Вычисляем:

· y₁=2 mod 3;

· k₂=3, t₂=3^–1 mod 7=5, y₂=3∙(5∙(2–2) mod 7)+2=0+2=2;

· k₃=3∙7=21, t₃=21^–1 mod 31 =3, y₃=21∙(3∙(13–2) mod 31)+2=21∙2+2=44.

Для операции умножения имеем: . Вычисляем:

· y₁=0 mod 3;

· k₂=3, t₂=3^–1 mod 7=5, y₂=3∙(5∙(1–0) mod 7)+0=3∙5+0=15;

· k₃=3∙7=21, t₃=21^–1 mod 31=2, y₃=21∙(2∙(12–1) mod 31) +15 =21∙22+15=477.

Итак, операции сложения, вычитания и, самое главное, умножения могут выполняться гораздо быстрее за счет появившейся возможности параллельных (одновременных) действий по различным модулям. К сожалению, этого не скажешь об операциях деления, сравнения, определения знака числа и так далее, а без этого эффективной арифметики не построишь. Логически возможны два пути. Поиск быстродействующих алгоритмов реализации операций в модулярной арифметике или преобразование из модулярного представления в обычное, выполнение операции и обратное преобразование. Но в последнем случае теряется эффект от применения модулярной арифметики, операции перехода затратные. Однако, не все так безнадежно. Рассмотрим вариант реализации модулярной арифметики (его основы), в котором операции преобразования из обычного представления в модулярное и обратно достаточно эффективны.

Выберем в качестве модулей m_i числа вида (числа М. Мерсенна, p_i – простые числа). Особенность таких чисел в том, что в двоичном представлении они имеют вид 00…01…1. Количество единиц равно p_i.

Любое целое число u, определенное по модулю числа М. Мерсенна m=2^p–1, можно представить p-разрядным словом: , где u_i=(0, 1).

В результате сложения чисел u и v, определенным таким образом, получается (p+1)-разрядное число w: w=u+v= +w_p∙2^p. Поскольку 2^p≡1 mod (2^p–1), то w= +w_p. Перенос в старший разряд при сложении чисел эквивалентен прибавлению единицы к младшему разряду.

Умножение целого числа u на степень 2^v по модулю m=2^p–1 (w=u∙2^v mod (2^p–1)) можно представить в виде:

w= + .

Поскольку 2^p≡1 mod (2^p–1) и каждый перенос в разряд p соответствует прибавлению единицы к младшему разряду, то умножение сводится к циклическому сдвигу числа на v разрядов влево.

Пример. Пусть p=7, u=83, v=5. Имеем 83∙2⁵ mod 127=116. Двоичное представление числа u=1010011₂. Циклический сдвиг на 5 разрядов дает число 1110100₂=116₁₀.

Операция умножения многоразрядных чисел реализуется через рассмотренные примитивы (сложение, умножение на число, равное степени двойки).

Покажем, что в случае выбора в качестве модулей m_i взаимно простых чисел М. Мерсенна для перевода числа u в модулярное представление не требуется выполнять операцию деления.

Пример. Пусть m₁=2²–1=3, m₂=2³–1=7, m₃=2⁵–1=31 и используется 16 разрядов для представления чисел. Тогда m₁=0000000000000011, m₂=0000000000000111, m₃=0000000000011111. Требуется перевести число u=2149210 в модулярное представление. Схема перевода приведена на рис. 1.29. Двоичное представление числа разбивается на группы по i бит (i=2, 3, 5) справа налево. Так как числа 2^q∙i (q=0, 1, …, ) сравнимы с единицей по модулю 2ⁱ–1, то остается просуммировать числа (коэффициенты) при соответствующих степенях двойки.

Рис. 1.29.. Схема перевода числа в модулярное представление

Рассмотрим перевод чисел из модулярного представления в обычное, то есть обратимся вновь к анализу китайского алгоритма. В энциклопедии Д. Кнута упоминается коротко о результате Х. Л. Гарнера (1958 год) по способу перехода от модулярного представления числа к его обычному виду, который фактически сводится к ранее рассмотренному четвертому варианту нахождения решения (п. 1.6.2).

Напомним, что результат решение системы из r сравнений x≡c_i(mod m_i) при попарно взаимно простых числах m₁, m₂,..., m_rнаходится путем последовательности вычислений:

y₁=c₁ mod m₁,

y₂=k₂∙(t₂∙(c₂–y₁)mod m₂)+y₁,

y₃=k₃∙(t₃∙(c₃–y₂)mod m₃)+y₂,

…………………………….

y_r=k_r∙(t_r∙(c_r–y_r–1)mod m_r)+y_r–1,

где и – обратный элемент к k_i, такой, что t_i∙k_i≡1 (mod m_i). Значение y_r является ответом задачи.

Числа k_i и t_i при известных модулях m₁, m₂,..., m_r можно вычислить заранее, они становятся константами и хранятся в соответствующих элементах одноименных массивов. Тогда логика преобразования сводится к простому повторению операций, выполняемых по модулю чисел М. Мерсенна.

Не нашли, что искали? Воспользуйтесь поиском по сайту: