КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Модулярная арифметикаМногие арифметические алгоритмы основываются на вычислениях по некоторому целому модулю k, или, как говорят, на модулярных вычислениях; соответственно, говорят о модулярной арифметике. Далее в этом параграфе мы считаем k фиксированным целым положительным числом. Целые a и b называют сравнимыми по модулю k и пишут a ≡ b (mod k), (22.1) если k | (a - b), т. е. если k является делителем разности a - b. Соотношение вида (22.1) называется сравнением. Изложение основ теории сравнений можно найти в любом учебнике алгебры1. Мы приведем основные элементарные факты этой теории, не останавливаясь на их доказательстве: (i) бинарное отношение сравнимости по модулю k является отношением эквивалентности на множестве целых чисел Z; (ii) если a г ≡ b г (mod k) и a2 ≡ b2 (mod k), то aг±a2 ≡ bг± b2 (mod k) и aгa2 ≡ bгb2 (mod k); (iii) каждое целое число a сравнимо по модулю k в точности с одним целым числом из множества {О,1,..., k - 1}. В силу (i) множество Z разбивается на классы эквивалентности по модулю k (кратко: классы по модулю k), и, согласно (ii), эти классы образуют кольцо, если считать, что сумма двух классов — это класс, содержащий сумму каких-либо чисел, взятых по одному из складываемых классов, а произведение — это, соответственно, класс, содержащий произведение каких-либо чисел, взятых по одному из перемножаемых классов. Нулем этого кольца является класс, содержащий число 0. Для введенного кольца используется обозначение Zk, его называют кольцом вычетов по модулю k (вычет—это в данном случае другое название класса эквивалентности по модулю k). Любое множество {a0, a ъ ■■■,ak-1} чисел, взятых по одному из каждого класса по модулю k, называется полной системой представителей по модулю k. Множество I k = {0,1,... k -1}, См., например, [14, § 42, 43] и [22, гл. 4, § 4, п. 2]. Глава 5. Битовая сложность указанное в (iii), называется канонической (или начальной) полной системой представителей по модулю к. Иногда используется и симметричная полная система представителей: §fc = jr-Ltil..,-1,0,1,..., UJ}, которая является симметричной (при условии игнорирования знаков) только при нечетном к: например, §3 = {-1>0>1} и §4 = = {-1,0,1,2}. Пусть для изображения элементов кольца Zfc используется система 1к. Операциям сложения и умножения в Zk соответствуют обычные сложение и умножение в Z с последующей заменой полученного результата остатком от его деления на к. Если некоторому элементу кольца Zk соответствует число а системы 1к, то противоположному (обратному по сложению) элементу будет соответствовать число к - а, если а Ф 0, и число 0, если а = 0. Исследуем битовую сложность операций в кольце Zfc. Будем считать размером входа битовую длину т числа к и ограничимся верхними асимптотическими оценками. Для операций сложения и нахождения противоположной величины имеем, очевидно, оценку 0(т). Использование операции наивного умножения целых чисел приводит к оценке 0{т2) для сложности умножения в Zk. Эта оценка, разумеется, сохраняется и при использовании более быстрого умножения и деления в Z. Как известно, в случае простого к кольцо Zfc является полем. При составном к это кольцо полем не является и, более того, содержит делители нуля: если к = pq, р > 1, q > 1, то произведение элементов Zfc, изображаемых числами р, q е 1к, равно нулю. Допустим, что к является простым и примем для этого простого числа обозначение р, по-прежнему считая его битовую длину равной т. Нахождение обратного к элементу кольца Z p, представленному целым ненулевым числом а&1р, может быть выполнено с помощью расширенного алгоритма Евклида. Так как р и а, очевидно, взаимно просты, то c помощью расширенного алгоритма Евклида можно найти s и t такие, что sp + ta = l. Получаем ta = l (mod р), т.е. обратным к классу, содержащему а, является класс, содержащий t. В силу (9.13) имеем \t\<p; если t < 0, то заменяем t на t + р (напомним, что мы используем элементы системы 1р для изображения элементов поля Z p). Пример 22.1. Для р = 13, а = 5 получаем с помощью расширенного алгоритма Евклида 2 • 13 + (-5) • 5 = 1, и отсюда 8 = -5 + 13 является обратным для 5 в Z13 (проверка подтверждает это: 5-8 = 1 (mod 13)). § 22. Модулярная арифметика Как следствие предложения 21.3 получаем такое утверждение. Предложение 22.1. Пусть расширенный алгоритм Евклида основывается на некоторых алгоритмах деления с остатком и умножения, битовые затраты каждого из которых применительно к целым v иw допускают оценку O (log v log w). Тогда битовая сложность обращения в поле Zp с помощью расширенного алгоритма Евклида допускает оценку O (log2 p) при использовании числа p в качестве размера входа и, соответственно, оценку O(m2) при использовании в этом качестве битовой длины m числа p. Несомненным достоинством алгоритма обращения, основанного на расширенном алгоритме Евклида, состоит в том, что с его помощью обращение возможно всякий раз, когда обращаемое число и модуль взаимно просты, а не только тогда, когда модуль—простое число. Например, можно определить a такое, что 5 a = 1 (mod 6)—среди чисел, входящих в 16, значением a является 5. В этом смысле применимость этого алгоритма шире, чем, например, алгоритма, основанного на малой теореме Ферма. Малая теорема Ферма. Пусть p — простое число, a — произвольное целое. Тогда ap=a (mod p). (Путь доказательства показан в задаче 108.) Если a не делится на p, то согласно этой теореме ap~2 является обратным к a по простому модулю p. Но это, вообще говоря, неверно для составных p. Например, неверно, что 55 = 1 (mod 6). С помощью расширенного алгоритма Евклида возможно обращение по модулю k любого числа a, взаимно простого с k; если a е1 k или a е§ k, то это обращение имеет битовую сложность O (teg2 k) или O(m2), коль скоро в качестве размера входа используется m = A(k). Пример 22.2. Уже говорилось, что вопрос о возможности распознавания простоты со сложностью O{md) с некоторым d е N представляет большой интерес и что, скажем, алгоритм пробных делений (примеры 1.2, 4.1, 5.2) не обладает указанным свойством даже при рассмотрении не битовой сложности, а сложности по числу делений, причем как в худшем случае, так и в среднем. Если для некоторого a eZ, не делящегося на n, мы обнаружим, что не выполняется сравнение an ≡ a (mod n), (22.2) Глава 5. Битовая сложность то по малой теореме Ферма из этого можно заключить, что n не является простым. Если фиксировано число a такое, что 1 < a < n, то использование бинарного алгоритма возведения в степень с заменой результата каждого из умножений остатком от деления на n позволяет вычислить an и проверить выполнение сравнения (22.2), затратив O (log3 n), или, что то же самое, O(mъ) битовых операций, где m = A(n). Однако это не позволяет утверждать, что мы можем на основе этого распознавать простоту n за O{m?) битовых операций, так как существует бесконечно много составных n таких, что (22.2) выполняется для любых a, взаимно простых с n. Это так на Напомним, что алгоритм со сложностью O{md), где m — размер входа, d е N, называют алгоритмом с полиномиально ограниченной сложностью или полиномиальным. В задаче распознавания простоты числа за размер входа берется количество m двоичных цифр числа n или же log2 n. После долгих поисков, в которых принимали участие разные исследователи, алгоритм с полиномиально ограниченной битовой сложностью был в 2002 г. предложен тремя индийскими математиками— М. Агравалом, H. Кайалом и H. Саксеной1. Этот алгоритм получил в литературе название AKS по первым буквам фамилий авторов. Мы обсудим лишь главную идею алгоритма AKS, основанием которого служит следующее необходимое и достаточное условие простоты числа n. Предложение 22.2. Пусть a е Z, n eN взаимно просты, тогда n является простым, если и только если выполнено полиномиальное сравнение (x - a) n = xn - a (mod n), (22.3) которое надо понимать так, что числовые коэффициенты при одинаковых степенях x в полиномах, расположенных в левой и правой частях, сравнимы по модулю n. Доказательство. Пусть n —простое. Если n = 2, то выполнение (22.3) проверяется непосредственно, и остается рассмотреть случай случая 1 < k < n равны соответственно и 0. При этом (k) делится на n, так как n простое (см. задачу 107). Коэффициенты при xn в обеих частях (22.3) равны 1, свободные члены соответственСм. [42]. § 22. Модулярная арифметика но равны (-а)" и -а. В силу нечетности п достаточно показать, что ап = а (mod п), а это сравнение выполняется в силу малой теоремы Ферма. Мы доказали, что если п — простое, то выполнено (22.3). Пусть теперь п — составное. Пусть, далее, простое q и ZeN+ таковы, что ql | п и при этом неверно, что ql+1 | п. Имеем ГпЛ (n - q + l)(n - q + 2)... n q q! Так как q | п, то произведение (п - q + 1)(п - q + 2)... (п - 1) не делится на q; при этом один из входящих в п множителей, равных q, сократится со знаменателем. Поэтому (п ] не делится на ql. Помимо этого,
Дата добавления: 2014-01-11; Просмотров: 732; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |