• Document: МОДУЛЬНАЯ АРИФМЕТИКА
  • Size: 176.55 KB
  • Uploaded: 2018-12-08 18:48:04
  • Status: Successfully converted


Some snippets from your converted document:

МОДУЛЬНАЯ АРИФМЕТИКА В некоторых приложениях удобно выполнять арифметические операции над целыми числами, заданными в так называемом модульном представлении. Это представление предполагает, что целое число представлено вычетами (остатками) по модулям из множества попарно взаимно простых чисел. Вычет числа a по модулю m обозначают a mod m . Например, 34 mod 5 = 4; –8 mod 3=–2 mod 3=1. В этом разделе под размерностью задачи мы будем понимать не количество чисел на входе алгоритма, как например, в задаче сортировки, а количество битов, использованных для записи числа. Алгоритм, получающий на вход целые числа a1 , a 2 ,..., a k называется полиномиальным, если его время работы ограничено многочленом от log 2 a1 , log 2 a 2 , …, log 2 a k , т.е. многочленом от длин исходных данных (в двоичной системе счисления). k −1 Если p 0 , p1 , ..., p k −1 – это k попарно взаимно простых чисел и p = ∏ pi , то i =0 любое целое число u , такое что 0 ≤ u ≤ p − 1 , можно однозначно представить множеством его вычетов u 0 , u1 , ..., u k −1 , где u i = u mod pi , 0 ≤ i ≤ k − 1 . Обычно пишут u ↔ (u 0 , u1 ,..., u k −1 ) . Сложение, вычитание и умножение легко выполняются, если их результаты заключены между 0 и p − 1 , т.е. если их можно рассматривать как вычисления по модулю p . Пусть два целых числа u и v заданы их множествами вычетов, т.е. u ↔ (u 0 , u1 ,..., u k −1 ) и v ↔ (v0 , v1 ,..., v k −1 ) . Тогда операции сложения, умножения и вычитания определяются следующим образом: u + v ↔ ( w0 , w1 ,..., wk −1 ) , где wi = (u i + vi ) mod pi ; (1) u − v ↔ ( x 0 , x1 ,..., x k −1 ) , где xi = (u i − vi ) mod pi ; (2) uv ↔ ( y 0 , y1 ,..., y k −1 ) , где y i = u i vi mod pi . (3) Рассмотрим пример. Пусть p 0 = 2 , p1 = 5 , p 2 = 7 . Получаем p = 2 × 5 × 7 = 70 . Тогда 6 ↔ (0,1,6) , так как 6 mod 2 = 0 , 6 mod 5 = 1 , 6 mod 7 = 6 . Аналогично, 9 ↔ (1,4,2) , 54 ↔ (0,4,3) . В силу (1) 6 + 9 ↔ (1,0,1) , так как (0 + 1) mod 2 = 1 , (1 + 4) mod 5 = 0 , (6 + 2) mod 7 = 1 но нетрудно убедиться, что 15 ↔ (1,0,1) . Согласно (2) и (3) получаем : 6 − 9 ↔ (1, 2, 4) – это модульное представление числа –3. 6 × 9 ↔ (0,4,5) – это модульное представление числа 54. Операция деления в модульной арифметике не определена. Преимущество модульного представления состоит в том, что арифметические операции могут быть реализованы с меньшими вычислительными затратами, чем при обычном представлении, так как вычисления выполняются независимо для каждого модуля. Следующая теорема доказывает, что соответствие u ↔ (u 0 , u1 ,..., u k −1 ) является взаимно однозначным. КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ k −1 Пусть p 0 , p1 ,..., p k −1 попарно взаимно простые целые числа, p = ∏ pi и i =0 u i = u mod pi . Тогда соответствие u ↔ (u 0 , u1 ,..., u k −1 ) между целыми числами u в интервале [0, p) и наборами вида (u 0 , u1 ,..., u k −1 ) , 0 ≤ u i < pi при 0 ≤ i < k ,

Recently converted files (publicly available):