AOP_Tom2 (1021737), страница 127
Текст из файла (страница 127)
[Указание. Если и ф 4, то одной из таких функций 7(п) является йсг((т(п), и), где т(н) = ппп(гп [ т! шог! и = О).) (Как следствие (Ь), полное разложение на простые множители произвольно большого числа и можно найти, выполнив только 0(!обо) арифметических операций. Для заданного частичного разложения и = им, . п„кансдое из чисел он не являющихся простыми, можно заменить функциями 7(пг) (пг//(и,)) за 2 О(!ойп,)=О(1обп) циклов. Этот процесс можно повторять до тех пор, пока все чигла и, не станут простыми.) ь 41. [Мйй[ (Дагариас (1 айапав), Миллер (М!Пег) и Одлыжко (Ог!!ух!го).) Назначение этого упражнения — показать, что может быть вычислено количество простых чисел, меньших г'г', если принимать во внимание только простые числа, меньшие Аг, и, таким образом, з 3 вычислять величину я (Аг ) за О(йгь") шагов. Положительное целое число, для которого все простые множители превышают число т, назовем т-долгожителем; так что один т-долгожитель останется в решете Эратосфена (упр.
8) после просеивания всех чисел, кратных простым числам, не превышающим гп. Пусть 1(х, т) — количество т-долгожителей, которое не превышает х, и пусть |ь(х, гл)— количество таких долгожителей; для которых имеется ровно )г простых множителей (учитывая кратность). а) Докажите, что я(!г' ) = я(!г') + у(!г~, 1г') — 1 — /з(йг, М). Ь) Поясните, как вычислить уа(Мз, !г') по значениям:г(х) для х < Аг~. Используйте метод вычисления значения уг(1000, 10) вручную. с) Та же задача, что и в (Ь), но вместо уз(йг~, А') вычислите уз(1У~, гг').
[Указание. Используйте тождество 7(х,р,) = /(х,р, г) — 7(х7рмр„г), где рэ есть Оье простое ггра=Ц г() Проанализируйте структуры данных, необходимые для эффективного вычисления величин при решении задач (Ь) и (с). 42. [Муб[ (Х. В. Ленстра (мл.) (Н. 1эг. Ьепвсга, Лг).) Для заданного интервала О < г < а < )т', в котором г Ь в и А' .Ь з, покажите, что можно найти все делители числа Аг, равные щ г (по модулю э), выполнив О([!У/э~]'7~ !ой э) хороню подобранные арифметические операции над (18 М)-битовыми числами. [Указание. Примените результаты упр. 4.5.3-49.] ь 43. [М43] Пусть т = рд — г-битовое целое число Влюма, как в теореме 3.5Р, и пусть Я~ = (у ] у = я~ шоб го для некоторого х).
Тогда 0~ имеет (р+ 1)(д+ 1)/4 элементов и каждый из этих элементов р б Я~ имеет единственный квадратный корень с =,/у, такой, что к б Ям. Предположим, что С(у) — это алгоритм, который правильно предсказывает значение ~/у шоб 2 с вероятностью > -' + е, где у — случайный элемент 0 . Цель этого упражнения — доказать, что задача, решаемая при помощи С, почти так же трудна, как и задача разложения на простые множители числа т. а) Разработайте алгоритм А(С, т,е,р,Ю), который использует случайные числа, и алгоритм С для того, чтобы предсказать без обязательного вычисления ~/у, будет ли данное целое число д принадлежать 0..
Результат выполнении алгоритма должен быть корректным с вероятностью > 1 — 5, а время Т(А) его выполнения не должно превышать величины О(с ~(!обд ')Т(С)) в предположении, что Т(С) > г~. (Если Т(С) < гэ, в этой формуле замените Т(С) величиной (Т(С) + г~),) Ь) Разработайте алгоритм Р(С, тп, с), который находит множители числа пг и ожидаемое время выполнения которого равно Т(г') = 0(г~(с е+ с (1обс )Т(С))). Указание. Для О < е < гл и фиксированного р б 0~ положим ге = ечгушобт и Ле = ге шос(2. Учтем, что Л( — е) + Ле = 1 и Л(е~ + . + е„) = (Ле~ + + Лев + [(гщ + + ге )/т]) шаг!2.
Имеем далее г(-'и) = з(ти + щЛе); здесь величина эе заменяет (шэх1е) шобгп. Если ке б 0, имеем г(ке) = ъ/сэр, поэтому алгоритм С обеспечивает способ предсказания величины Ле для примерно половины всех е. 44. [М35] (И. Хвастал (1. Наэсаб).) Покажите, что нетрудно найти к в случае, когда а а+ а гк+а эх +а~эх~ гэ О (по модулю гп ), О < к < пэ„йсб(а,э, а ма г, а з, гп,) = 1 и нн > 10ы при 1 < 1 < 7, если гп, .1 ш при 1 < ! < 2 < 7, (Все переменные — целые числа, и все они, кроме к, известны.) Указание. Когда Т,— произвольная неособая матрица вещественных элементов, алгоритм Ленстрв (Еепэсга) и Ловача (1.ояйэя) [Масйегпабэс6е Алла!еп 281 (1982), 515-534] эффективно находит ненулевой целочисленный вектор и = (еы...,. ся), такой, что длина (еХ) < ~/п2" ]бег/]Ы".
45. [М41] (Дж. М. Поллард (3. ЬЕ Ройагб) и Клаус-Петер Шнорр (С!апэ-Ресег Ясбпогг).) Покажите, что для целых чисел к и у, заданных целых чисел а, Ь и и> для которых аЫ и и и нечетно, существует эффективный способ решения уравнения к — ау ш Ь (по модулю п) э 2 даже в том случае, когда неизвестно разложение на простые множители числа и. [Указание.
Используйте тождество (х, — ар,)(хэ — ауэ) = к — ар, где к = хааке — ащрэ и 2 3 2 з 2 2 н = гПэ + хэуь] 48. [НМ39] (Л. Эдлеман (1, АО!шпал).) Пусть р — достаточно большое простое число и а --простой корень по модулю р; таким образом, все целые числа 6 в интервале 1 < Ь < р могут быть записаны в виде Ь = а" шос! р для некоторого единственного числа и из интервала 1< и <р.
Используя идеи, аналогичные идеям из алгоритма Диксона разложения на простые множители, разработайте алгоритм, который почти всегда по заданному 6 находит число и за 0(р') шагов для всех с > О. [Указание. Начните с формирования набора чисел п„таких, что число а"' шоб р имеет только малые простые множители.] 47. [Мбб) Некоторая цитата из литературного источника х = х1хг, представленная в АЯСП-ходах, в зашифрованном виде выглядит как (х~1 пю11?Ьг, хг зпюс) Ж) = (14к9гкРьСьз1О92ь91вв9сОв1в46444ЬО4В1гСО11зг9Сг1вР11ОР6вО4РатьСзСЕОзО1ОзВВтС4Озк1З2124166 еьгшткгвбьоосзьвтзгтьгьввьвосввьзв?1498?гскозггввзьввзкьвэвввзвтьввигвзв?98911121?4616, 1ьва2ьк21кРлвь69ь42ь9О184сРвгРггв2евквовгВ4зеРвш1Ргь91е8вс2сввььве4в1Р1РкО4РРгРОвззктзо 92ОЬЬЗ418ОВВ9ВВ8С6ж66ьО1ЗО9ЬЗ17ЗЬРЕ66С741О1261ВЗ4СВ26ВВР634ООСОС286г6124Ь4Е3ОВООЕ4ОЗЬСТ) в шестнадцатеричных обозначениях, где Х равно 17В23ЬЗВ969ЬЕС669РЕР6О94О16ОС4О8428ВО12ЬЗРРЕ49О114Р2Е6ЗЗР82С8ВОЬ224РС4З16Р91О4СЕОЗВС6810 вк6т61ьтРп1ст8Р96ь6зОРл9взРьссьв9воо1вввгьг1Р4квОО9ьвгьРО1Рввееш11евзтьОРОг1ььз8гшвввз.
Что собой представляет х? Проблема распознавания простых чисел из составных и Разложения составных чисел на простые множители является одной иэ самы» важных и полезных среди всех арифметических задач. ... Высокое призвание науки в том, кажется, и состоит; чтобы любой вклад в решение такой злегэнтной и знаменитой пРоблемы усердно культивировался, — К. Ог. ГАУСС (С. г, ВА055), О!Ьби?Ь?Г?ОПЕЗ АПГПтЕГ1СШ, АСт~С!Е 329 (1Н01) й.б. ПОЛИНОМИАЛЬНАЯ АРИФМЕТИКА Изученные НАМИ ткхНОЛОГНН естественным образом применимы не только к числам, но н к различным математическим величинам.
В этом разделе речь пойдет о полиномах, что представляет шаг вперед по сравнению с числами. Формально говоря, полинам над 5 представляет собой выражение вида и(х) = и„х" + +исх+ ив, где коэффициенты и„,..., иы ие — элементы некоторой алгебраической системы 5, а переменная х может рассматриваться как формальный символ без определенного значения. Будем полагать, что алгебраическая система 5 представляет собой каммутатиенае кольцо с единицей. Это означает, что 5 допускает операции сложения, вычитания и умножения, удовлетворяющие обычным свойствам: сложение и умножение являются ассоциативнылси и коммутативными бинарными операциями, определенными на 5, причем умножение дистрибутивно по отношению к сложению.
Существует также единичный элемент по сложению 0 и единичный элемент по умножению 1, такие, что а + 0 = а и а - 1 = а для всех а из 5. Вычитание является обратной по отношению к сложению операцией, но о возможности деления как об операции, обратной по отношению к умножению, ничего не предполагается. Полинам Ох"+ +. +Ох"~'+и„хя+..
+и1х+ие рассматривается как идентичный папиному (1), хотя формально он отличается от него. Мы говорим, что (1) является полиномом степени и со старшим коэ44ициентам и„, если и„ф 0; в этом случае запишем* (г) бей(и) = п, К(и) = и„. Кроме того, по определению е(ея(0) = — со, й(0) = О, где 0 означает нулевой поливом, т. е. полинам, все коэффициенты котороео равны нулю. Мы говорим также, что и(х) — нормированный налимам, если его старший коэффициент й(и) равен 1.
Арифметика полиномов состоит, в первую очередь, из сложения, вычитания и умножения; иногда к этим операциям добавляются другие, например, деление, возведение в степень, разложение на множители и поиск наибольшего общего делителя. Сложение, вычитание и умножение определяются естественным образом, как если бы переменная х была элементом 5: мы складываем или вычитаем полиномы посредством сложения или вычитания коэффициентов при одинаковых степенях х.
Умножение выполняется согласно правилу (и„х" + +ив)(е„х" + +ио) = ш„,,х"+'+ +то, где (4) шй = иеиь. + и1ие 1 + .. + иь-1и1 + иьие. В последней формуле и» и и рассматриваются как равные нулю при е > г и у > з соответственно. Ь Здесь символ Г означает !еад1нд (еедйщна; в русскеязычней математической литературе-- старшна).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
