Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 218
Текст из файла (страница 218)
Поскольку 2 ~ 30, выполняются строки 3 — 5. В строке 3 вычисляется значение хо = ( — 7)(16) пюг( 100 = 95. В цикле в строках 4 — 5 выводятся два решения уравнения, равные 95 и 45. Процедура МопиеАк-1лнеАк-ЕООАт10н-Яоечек работает следуюшим образом. В строке 1 вычисляются величина з( = ясс)(а,п), а также значения х' и у', такие, что з( = ах'+ пу', что свидетельствует о том, что х' удовлетворяет исходному уравнению ах' =— з( (пюд и).
Если з( не является делителем числа 6, то уравнение решений не имеет согласно следствию 31.21. В строке 2 проверяется, делится ли 6 на 4 если не делится, то в строке б выводится сообшение об отсутствии решений заданного уравнения. В противном случае в строке 3 в соответствии с теоремой 31.23 вычисляется решение хо уравнения ах ь— а 6 (гпоб и). Если найдено одно решение, то согласно теореме 31.24 остальные с( — 1 решений можно получить путем добавления величин, кратных (и/с(), по модулю и. Это и делается в цикле Гог в строках 4 и 5, где с шагом (п/с)) выводятся все с( решений по модулю и„начиная с хо. Процедура Монгол.Ак-1ечеАк-Е00Ат~он-Бои)ек выполняет О(!я и + ясс)(а,п)) арифметических операций, поскольку процедура Ехтенпеп-Еисшп 993 Тлела 36 Теоретико-числоеые алгорыпыы выполняет 0(1кп) арифметических операций, а каждая итерация цикла 1ог в строках 4 и 5 выполняет фиксированное количество арифметических операций.
Сформулированные ниже следствия теоремы 31.24 позволяют сделать уточнения, представляющие особый интерес. Следствие 31.25 Для любого п > 1 из ксг)(а, и) = 1 следует, что уравнение ах = 5 (гпог1 п) имеет единственное по модулю п решение. Значительный интерес представляет распространенный случай 5 = 1. При этом искомое число х является мультннлнкетнвным обратным (пш1йрйсайче 1пчегзе) к числу а по модулю п. Следствие 31.26 Для любого п ) 1 из ясг)(а, п) = 1 следует, что уравнение ах = 1 (апой п) имеет единственное по модулю п решение. В противном случае оно не имеет решений. Благодаря следствию 31.26 можно использовать запись а ' щи п для мультипликативного обратного к а по модулю п, когда а и п взаимно простые.
Если ксс1(а, и) = 1, то единственным решением уравнения ах вз 1 (шог1 и) является целое число х, возвращаемое процедурой Ехтннпнп-Епсь1О, поскольку из уравнения Кса(а,п) =1= ах+ пу следует, что ах ив я 1 (шос) п). Таким образом, а ' пюг1 и можно эффективно вычислить с помощью процедуры Ехтнмпнп-Епсь1О. Упражнения 31.4.1 Найдите все решения уравнения 35х = — 10 (пюб 50). 31.4.2 Докажите, что из уравнения ах ив з ау (гпог) п) вытекает х = у (гпог) п), если ксг)(а, п) = 1. Покажите, что условие кои(а, и) = 1 является необходимым, приведя контрпример с ксг)(а, и) ) 1. 31.4.3 Рассмотрим следующее изменение строки 3 процедуры МОО13ьлк-ЫнелкЕ(.ЮАТ!ОХ-БОЬЧЕК, 3 хо = х'(5/Ы) пюг) (и/И) Будет лн работать такая видоизмененная процедура? Обоснуйте ответ.
маклин Чаеме УП. Избранные темы 31.4.4 * Пусть р — простое число, а 3'(х) = Уо + ~~х+ ° + 1ех' (щось р) — полинам степени 8 с коэффициентами 1ы взятыми из Ер. Мы говорим, что а Е Е„является кулем 1, если 1(а) г— в 0 (пюб р). Докажите, что если а является нулем 1„ то 1(х) = (х — а)д(х) (шое( р) для некоторого полинома д(х) степени 1 — 1.
Докажите по индукции по 1, что если р простое, то полинам 1(х) степени 1 может иметь не более 1 различных по модулю р нулей. 31.5. Китайскаи теорема об остатках Около 100 г. н.э. китайский математик Сунь-Цзы (Зип-Тзб) решил задачу поиска целых чисел х, которые при делении на 3, б и 7 дают остатки 2, 3 и 2 соответственно. Одно из таких решений — х = 23, а общее решение имеет вид 23 + 1051, где )е — произвольное целое число.
"Китайская теорема об остатках" устанавливает соответствие между системой уравнений по взаимно простым модулям (например, 3, 5 и 7) и уравнением по модулю произведения этих чисел (в данном примере это число 105). Китайская теорема об остатках имеет два основных применения. Пусть целое число и раскладывается на попарно взаимно простые множители и = изиз ..
иь. Во-первых, эта теорема играет роль описательной "структурной теоремы", которая описывает структуру Е„как идентичную структуре декартового произведения Е„, х Е„, х .. х Е„„с покомпонентным сложением и умножением по модулю и; в 1-м компоненте. Во-вторых, с помощью этого описания во многих случаях можно разработать эффективные алгоритмы, поскольку работа с каждой из систем Е„, может оказаться эффективнее (в терминах битовых операций), чем работа по модулю и. Теорема 31.27 ~Китайская теорема об остатках) Пусть и = изиз иы где и, — попарно взаимно простые числа.
Рассмотрим соответствие а <-> (аз,аз,...,аь), (31.27) где а е Е„, а; е Е„и а, = а гаое( и, при 1 = 1,2,..., 1с. Тогда отображение (31.27) является взаимно однозначным отображением (биекцией) между Е„и декартовым произведением Е„, хЕ„, х х Е„„. Операции, которые выполняются над элементами Е„, можно эквивалентно выполнять над соответствующими Й-кортежами, независимо выполняя операции нак каждым компонентом в соответствующей системе.
То есть, если а <-~ (аз, аз,...,аь), Ь (Ьз,бз,...,Ь ), Глава 51. Теоретико-числовое алгортеиеы 995 то (а + Ь) пюс1 п ~+ ((а1+ Ь1) пюс( пы..., (аь + Ьь) пюс1 пь), (31.28) (а — Ь) щос1 п ~+ ((а1 — Ь1) пюс1 пы..., (аь — Ьь) пюс) иь), (31.29) (аЬ) пюс1 п с-+ (а1Ь1 пюс1 пы..., аьЬь пюс1 пь) . (31.30) с; = т,(ги, ' пюб и,) (31.31) для 1 = 1, 2,..., )с.
Уравнение (31.31) всегда вполне определено: поскольку числа ти; и п, взаимно простые (согласно теореме 31.6), следствие 31.26 гарантирует существование величины т, 1 пюс1 п,. Наюнец величину а можно вычислить как функцию от аы аз, ..., аь следукнцим образом: а = (а1с1+азсз+. +акса) (пюс1 и) . (31.32) Теперь покажем, что уравнение (31.32) гарантирует выполнение соотношения а = а; (пюс( п,) для 1 = 1, 2,..., Iс.
Заметим, что если 5 ~ 1, то т = 0 (щос) и,), откуда следует, что с =— ги = 0 (пюс1 п,). Заметим также, что из уравнения (3!.31) следует с, = 1 (щос) и,). Таким образом, мы получаем красивое и полезное соответствие с, с+ (0,0,...,0,1,0,...,0), где все компоненты равны нулю, кроме 1-го, который равен единице.
Векторы с, в определенном смысле образуют базис представления. Поэтому для каждого 1 можно записать а = а,с; (пю<1 п,) = а,т,(т, щос1 и,) (щос( и,) : — а; (гпос) и;), что и требовалось показать: представленный метод вычисления величины а по заданным значениям а, дает результат, удовлетворяющий ограничениям а = а; (шос1 тн) для 1 = 1,2,..., )с. Это соответствие взаимно однозначное, поскольку преобразования можно выполнять в обоих направлениях.
Наконец уравнения (31.28Я31.30) непосредственно следуют из результатов упр. 31.1.7, поскольку соотношение х щос) п. = (х щос) и) пюс1 и, справедливо при любом х и 1 = 1, 2,..., Iс. Доказаввачьсввяо. Преобразование одного представления в другое осуществляется достаточно прямолинейно. Переход от а к (ам аз,...,аь) очень простой, и для него требуется выполнить всего )с операций "щосГ'. Вычислить элемент а по заданным входным элементам (ам аз,...,аь) несколько сложнее, и это можно сделать следующим образом.
Сначала определим величины гп, = и/и, для 1 = 1, 2,..., Iс; таким образом, т; представляет собой произведение всех значений и, отличных от и,". т, = п1пз и; 1п,+1 пы Затем определим Часть Рзд Избранные темы 996 Сформулируем следствия, которые понадобятся нам в последуюших разделах. Следствие 31.28 Если пы пз,..., иь попарно взаимно простые и и = пзпз пы то для любых целых чисел аы аз,..., аь система уравнений х = а, (пюс1 пз), где 1 = 1, 2,..., к, имеет единственное решение по модулю п относительно неиз- вестной величины х. где 1 = 1, 2,..., зс, выполняется тогда и толью тогда, когда х = а (пюс1 и) В качестве примера применения китайской теоремы об остатках предположим, что дана система уравнений = 2 (пюс1 5), —= 3 (гпоб 13), так что а1 = 2, и1 = зпз = 5, аз = 3 и пз = пт1 = 13, и необходимо вычислить а пзос1 65, поскольку и = п1из = 65.
Так как 13 ~ ьв 2 (аспас( 5) и 5 ' = 8 (шоб 13), имеем 13(2 шос1 5) = 26, 5(8 пюб 13) = 40 сз = а = 2. 26+ 3 40 (шос1 65) =— 52+ 120 (гпос1 65) :— 42 (пюб 65) . Данный пример проиллюстрирован на рис. 31.3. Таким образом, операции по модулю п можно выполнять непосредственно, а можно перейти к представлению, в котором вычисления проводятся отдельно по модулям ио т.е. выбирать более удобный способ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
