Алгоритмы - построение и анализ (1021735), страница 200
Текст из файла (страница 200)
В цикле в строках 4-5 выводятся два решения уравнения, равные 95 и 45. Опишем работу процедуры Моогл.лк Ьпчелк ЕОилтюы Боьчкк. В строке 1 вычисляется величина г1 = бсг1 (а, п), а также величины х' и у', такие что Н = ах'+ + пу', что свидетельствует о том, что х' удовлетворяет исходному уравнению. Если 4 не является делителем числа Ь, то уравнение решений не имеет согласно следствию 31.21. В строке 2 проверяется, делится ли Ь на д; если нет, то в строке 6 выводится сообщение об отсутствии решений заданного уравнения.
В противном случае в строке 3, в соответствии с теоремой 31.23, вычисляется решение ха уравнения ах аз Ь (шос1п). Если найдено одно решение, то, согласно теореме 31.24, остальные Н вЂ” 1 решений можно получить путем добавления величин, кратных (п7'й) по модулю и. Это и делается в цикле 1ог в строках 4-5, где с шагом (п(й) по модулю и выводятся все Н решений, начиная с хо. В процедуре Мооиык Ьпчклк ЕОилтюы Яоьчек выполняется 0(18п + + ясг1(а, и)) арифметических операций, поскольку в процедуре Ехтеыою Еисгзп выполняется 0 (18 и) арифметических операций, и при каждой итерации цикла Гог в строках 4-5 производится фиксированное количество арифметических операций.
Сформулированные ниже следствия теоремы 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 ( пюс15) и 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
