Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 200
Текст из файла (страница 200)
Сформулированные ниже следствия теоремы 31.24 позволяют сделать уточнения, представляющие особый интерес. Следствие 31.25. Пусть п > 1. Если бсг1(а, и) = 1, то уравнение ах = Ь(шос1п) имеет единственное решение по модулю и. И Значительный интерес представляет весьма распространенный случай Ь = 1. При этом искомое число х является мультинликативным обратным (пш1бр!кайме 1пчегзе) к числу а по модулю п.
Следствие 31.26. Пусть п > 1. Если ясг1 (а, и) = 1, то уравнение ах = 1 (шоЫ) обладает единственным решением по модулю п. В противном случае оно не имеет решений. и Следствие 31.26 позволяет использовать запись (а г пюс1 п) для мультипликативных обратных чисел модулю и, где а и п — взаимно простые. Если бсг1 (а, и) = 1, то единственное решение уравнения ах = 1 (шодп) — целое число х, возвращаемое процедурой Ехткыою Еосшо, поскольку из уравнения бсг1 (а, п) = 1 = ах + пу следует, что ах = 1 (шог1п).
Таким образом, можно эффективно вычислить вели- чину (а г шой и) с помощью процедуры Ехтечою Еосшо. Глава 31. Теоретико-числовые алгоритмы 979 Упражнения 31.4-1. Найдите все решения уравнения 35х =— 10 (шос150). 31.4-2. Докажите, что из уравнения ах а— а ау(шос1и) следует соотношение х =— д(тос1и), если ясс1(а, и) = 1. Покажите, что условие ясс1(а,и) = 1 является необходимым, приведя контрпример при ясс) (а, и) ) 1.
31.4-3. Рассмотрим приведенную ниже модификацию строки 3 в процедуре М00(л.Ак Ь!хеАк ЕЯОАт!0х БОьУек: 3 слеп хо — х'(6/д) шос1 (и/с1) Будет ли работать такая видоизмененная процедура? Обоснуйте ответ. * 31.4-4. Пусть / (х) =/о+/1х+ .+/сх' (тос1р) — полинам степени 1 с коэффициентами /с, которые являются элементами множества Ер, где р — простое число. Говорят, что ай Ер — нуль (гего) полинома /, если / (а) =0 (пюс1р).
Докажите, что если а — нуль полинома /, то / (х) = (х — а) д (х) (пюс1р) для некоторого полинома д (х) степени $ — 1. Докаяопе методом математической индукции по $, что полинам / (х) степени 1 может иметь не более 8 различных нулей по модулю простого числа р. 31.5 Китайская теорема об остатках Приблизительно в 100 г. н.э. китайский математик Сунь-Цзы (Бцп-Тзб) решил задачу поиска целых чисел х, которые при делении на 3, 5 и 7 дают остатки 2, 3 и 2 соответственно. Одно из таких решений — х = 23, а общее решение имеет вид 23+ 1051, где 1с — произвольное целое число. "Китайская теорема об остатках*' устанавливает соответствие между системой уравнений по взаимно простым модулям (например, 3, 5 и 7) и уравнением по модулю произведения этих чисел (в данном примере, 105). Китайская теорема об остатках имеет два основных применения.
Пусть целое число и раскладывается на попарно взаимно простые множители и = и1иг... иь. Во-первых, эта теорема играет роль описательной "структурной теоремы". Согласно ей, структура Е„представляет собой декартово произведение Е„, х Е„, х х х Е„„с покомпонентным сложением и умножением по модулю и, в 1-м компоненте. Во-вторых, с помощью этого описания во многих случаях можно получить эффективные алгоритмы, поскольку работа с каждой из систем Е„, может оказаться эффективнее (в терминах битовых операций), чем работа по модулю и.
Теорема 31.27 (Китайская теорема об остатках). Пусть и = и1иг... иы где и; — попарно взаимно простые числа. Рассмотрим соответствие а + (аыаг,...,аь), (31.23) Часть ЧП. Избранные темы 980 где а 6 Е„, а; Е Е„д и а; = а шод и; при 1 = 1, 2,..., /с. Тогда отображение (31.23) является взаимно однозначным соответствием (биекцией) между множеством Е„ и декартовым произведением Е,,д х Е„, х х Е„„.
Операции, которые выполняются над элементами множества Е„, можно эквивалентно выполнять над соответствующими кортежами из lс величин путем независимого выполнения операций над каждым компонентом. Таким образом, если а (ад,аз,...,аь) и Ь + (Ъд,Ьз,...,Ьь), то справедливы соотношения (а + Ь) шос1 и > ((ад + Ьд) шод1 пд,..., (аь + Ьь) шос) иь), (31.24) (а — Ь) шос( и ~ ((ад — Ьд) шос) пд,..., (аь — Ьь) шос( пь), (31.25) (аЬ) шос1 п + ((адЬд) щи пд,..., (аьЬь) пюс1 пь) . (31.26) с, = т;(т, шос1и,) (31.27) для 1 = 1, 2,..., Ь. Уравнение (31.27) всегда вполне определено: поскольку числа т; и и, взаимно простые (согласно теореме 31.6), следствие 31.26 гарантирует существование величины (т, д дпос1 и,). Наконец, величину а можно вычислить как функцию величин (ад, аз..., аь) по формуле а на (адсд+ азсз+.
+аьсь) (тос(п). (31.28) Теперь покажем, что уравнение (31.28) обеспечивает справедливость соотношения а=а, (шос1и;) при г = 1, 2,..., й. Заметим, что еслибы' ф г, то ту=О (шос1гдд), откуда следует, что с; = т аа 0 (шод(гдд). Заметим также, что из уравнения (31.27) следует сд = 1 (шодпд). Таким образом, получаем красивое и полезное соответ- ствие с; +(0,0,...,0,1,0,...,0), дне все компоненты равны нулю, кроме 1-го, который равен 1. Векторы с; в определенном смысле образуют базис представления. Поэтому для каждого г можно Доказательсвдво. Преобразование от одного представления к другому осуществляется довольно просто.
Переход от а к (ад,аз...,аь) очень простой, и для него требуется выполнить всего 1с операций деления. Вычислить элемент а по заданным входным элементам (ад, аз..., аь) несколько сложнее, и это делается следующим образом. Сначала определим величины ги, = и/и; для 1 = 1, 2,..., Ь. Другими словами, т; — произведение всех значений и, отличных от ис т; = = пдиз. и; дгдд+д пы Затем определим Глава 31. Теоретико-числовые алгоритмы 981 записать а г— е а;с; (шодпс) = = а;гпс (тц ~ пюс1 П) (пюс1п,) = = а; (пюс1п;), что и требовалось показать: представленный метод вычисления величины а по заданным значениям а; дает результат, удовлетворяющий условию а = а; (шос1п;) для 1 = 1,2,..., к.
Это соответствие взаимно однозначное, поскольку преобразования можно производить в обоих направлениях. Наконец, уравнения (31.24)- (31.26) непосредственно следуют из результатов упражнения 31.1-6, поскольку соотношение х шод п; = (х пюс1 п) пюс1 пс справедливо при любом х и 1 = = 1,2,...,)с. И Сформулируем следствия, которые понадобятся нам в последующих разделах.
Следствие 31.28. Если пы пз,..., пь — попарно взаимно простые числа и п = = пгпз пы то для любого набора целых чисел аз, аз,... аь система уравнений х ив а а; (пюс1п;) при 4 = 1, 2,..., Iс имеет единственное решение по модулю и относительно неизвестной величины х. В Следствие 31.29. Если пы пз,..., пь — попарно взаимно простые числа и п = = пзпз пы то для любых целых чисел х и а соотношение х = а (пюс1пс) для 1 = 1, 2,..., lс выполняется тогда и только тогда, когда х = а(пюс1п).
В качестве примера применения китайской теоремы об остатках рассмотрим систему уравнений а аз 2 (шос15), а = 3 (шос113), так что аз = 2, пт = гпз = 5, аз = 3 и пз = тз = 13. Нам нужно вычислить величину а шо6 65, так как п = 65. Поскольку 13 з = 2 ( пю65) и 5 Ъ 8 (пюс(13), получаем сз = 13 (2 пюс1 5) = 26, сз = 5 (8 шод 13) = 40, 982 Часть ЧП. Избранные темы Таблица 31.4.
Иллюстрация китайской теоремы об остатках при кч = 5 н пз = 13 а= (2 26+ 3 40) (шод65) = = (52+ 120) (щод65) = = 42 (шос165) . Данный пример проиллюстрирован в табл. 31.4. На пересечении строки 1 и столбца 7' приведено значение а по модулю 65, удовлетворяющее уравнениям (а щод 5) = 4 и (а щод 13) = 7'. Обратите внимание, что в ячейке на пересечении строки О и столбца 0 содержится значение О. Поскольку с1 = 26, сдвиг вниз вдоль столбца приводит к увеличению значения а на 26. Аналогично, то, что сз = 40, означает, что сдвиг вправо вдоль строки приводит к увеличению значения а на 40.
Увеличение значения а на 1 соответствует сдвигу по диагонали вниз и вправо. Таким образом, операции по модулю и можно выполнять непосредственно, а можно перейти к представлению, в котором вычисления производятся отдельно по модулям по Эти вычисления полностью эквивалентны, и есть возможность выбирать более удобный способ. Упражнения 31.5-1. Найдите все решения уравнений х = 4(щос15) и х яа 5 (шо611). 31.5-2. Найдите все целые числа х, которые при делении на 9, 8 и 7 дают остатки 1, 2 и 3 соответственно.
31.5-3. Докажите, что при выполнении условий теоремы 31.27, если йсб (а, и) = = 1, то (а ~ шобп) + ((а шодп1),(а 1шойп1),...,(а„щобпа)). 31.5-4. Докажите, что при выполнении условий теоремы 31.27 количество корней уравнения 7" (х) = 0 (шобп), где Г" — произвольный полипом, равно произведению количества корней уравнений г (х) = 0 (щойпт), г' (х) = : — 0 (шобла),..., г" (х) я— а 0 (щос1пь). Глава 31. Теоретико-числовые алгоритмы 983 31.6 Степени элемента Рассматривать последовательность О ! 2 3 (31.29) степеней числа а по модулю и, гпе а е Е;„так же естественно, как и последовательность чисел, кратных а по модулю и. Индексация начинается от нуля; нулевой член последовательности равен ас гпос1 п = 1, а 1-й член — а' шос! п = 1.
Ниже в качестве примера приведены степени чисел 3 и 2 по модулю 7: 0 1 2 3 4 5 6 7 8 9 10 11 3'шос17 1 3 2 6 4 5 1 3 2 6 4 5 2шос(7 1 2 4 ! 2 4 1 2 4 1 2 4 В этом разделе при помощи (а) будет обозначаться подгруппа группы Е„', сгенерированная элементом а путем повторного умножения, а огс1„(а) (порядок а по модулю и) будет обозначать порядок элемента а в группе Е„'. Например, в группе Ет (2) = (1,2,4), а огс1т(2) = 3. Используя определение функции Эйлера ф(тс) в качестве размера группы Е„' (см.
упражнение 31.3), преобразуем следствие 31.19 с использованием обозначений Е„', чтобы получить теорему Эйлера и сформулировать ее для частного случая группы Ер, где р — простое число, что даст нам теорему Ферма. Теорема 31.30 (Теорема Эйлера). При любом целом значении тс ) 1 для всех аЕЕ;, ао("! =- 1(тос1п). И Теорема 31.31 (Теорема Ферма). Если р — простое число, то для всех а Е Е„' а" ~— : 1(пюс1р). ,ссоказаясельсясво. Согласно уравнению (31.20), для простых чисел р функция Эйлера равна ф (р) = р — 1. И Это следствие применимо к каждому элементу группы Ер за исключением нуля, поскольку 0 ф Ер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
