М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 183
Текст из файла (страница 183)
Порядком числа х по модулю 11' называют наименьшее положительное целое число, для которого х" = 1 (пюд М). Задача нахождения порядка заключается в определении г по заданным х и И. 'Упражнение П4.16. Докажите, используя теорему П4.9, что порядок числа х по модулю Ф делит число у(Р7). Процедура сведения разложения на простые множители к нахождению порядка элемента включает два основных шага: 1) необходимо показать, что можно найти множитель числа и, если мы умеем находить нетривиальное решение х ~ х1 (пюб М) уравнения хз = 1 (пюс1 г7); 2) необходимо доказать, что произвольно выбранное взаимно простое с Ф число 9 с большой вероятностью имеет порядок т, который является четным числом и у"1з ф х1 (пюд Ж), т. е.
х ьз у'~з (пюб Ж) — решение уравнения хз = 1 (пюб М). Теорема П4.11. Пусть М вЂ” составное число длиной Е бит, х — нетривиальное решение уравнения хз = 1 (шод И) в диапазоне 1 < х < М, т. е. х ф 1 (шод Ф), х ф Ф вЂ” 1 = — 1 (шоб Ж). Тогда по крайней мере одно из чисел НОД(х — 1, Ф) и НОД(х+ 1, Ф) является нетривиальным делителем числа Ф, и его можно вычислить за 0(Ь~) операций. Доказатпеяъстао. Поскольку х = 1 (пюд М), число И делит х~ — 1 = (х + 1)(х — 1), следовательно, М должно иметь общий делитель либо с (х+ 1), либо с (х — 1). Но по предположению 1 < х < (М вЂ” 1), поэтому (х — 1) < (х+ 1) < Ф, т.
е. общий множитель не может равняться Ф. Используя алгоритм Евклида, найдем НОД(х — 1, М) и НОД(х + 1, 11'), а следовательно, и нетривиальный делитель числа И (на это потребуется 0(Ьз) операций). Лемма П4.12. Пусть р — нечетное простое число; 2а — максимальная степень числа 2, делящая у(р~). Тогда с вероятностью ровно 1/2 число 24 делит порядок по модулю р элемента из Ер, выбранного случайно и равновероятно. Даказагпеяъспзво. Заметим, что число ~р(р'") = р" ~(р — 1) — четное, поскольку р — нечетное, следовательно, 4 > 1. Согласно теореме П4.10 существует образующая д группы Ер, поэтому произвольный элемент этой группы может 768 Приложение 4.
Теория чисел быть записан в виде д" (шос( р~) для некоторого л в диапазоне от 1 до сс»(р"). Пусть т — порядок элемента д" по модулю р . Рассмотрим два случая. Первый случай: й — нечетное число. Поскольку д«" = 1 (шос( р ), можно сделать заключение, что р(р )~йт, поэтому Ят, так как число с« — нечетное. Второй случай: й — четное число. Тогда имеем , ь/г д ~~» ~/ = (д"~" ~/ =1 / =1 (пюс1 р ): (П4.31) Поэтому т/(ср(р )/2), отсюда следует, что 2" не делит т.
Итак, группу Е' можно разбить на две части равной мощности: элементы, которые могут быть представлены в виде д" с нечетным с«(для них 2л~т, где т— порядок дь) и в виде дь с четным к (для них 2",~ т). Поэтому с вероятностью 1/2 число 2" делит порядок т произвольно выбранного элемента группы Е„' . Теорема П4.13. Пусть Ю = р, ' х... хр'"" — разложение нечетного составного числа на простые множители. Пусть х — элемент из Е~„выбранный случайно и равновероятно, т — порядок элемента х (по модулю Ф). Тогда р(т четное и х"с ф — 1 (шобс«')) > 1 — —.
3 1 2'" (П4.32) Доказательство. Покажем, что 1 р(т нечетное или х'/~ = — 1 (шобЖ)) ( —. 2»ъ (П4.33) Согласно китайской теореме об остатках, выбор случайного числа х с равномерно распределенной по множеству Е~~ вероятностью равносилен выбору чисел х с равномерно распределенными по множествам Е", вероятностями тз' (при условии х = хс (шос( р-') для всех у). Пусть т — порядок элементах по модулю р '. Пусть 2«с — максимальная степень числа 2, которая делит ту, а 2" — максимальная степень числа 2, которая делит т.
Рассмотрим следующее условие: т нечегно или х"/~ = — 1 (шос( Ж). Покажем, что для его выполнения необходимо, чтобы дт принимало одно и то же значение для всех у'. Отсюда будет следовать утверждение теоремы, поскольку, согласно лемме П4.12, вероятность выполнения вышеуказанного условия не меньше 1/2«с. Сначала рассмотрим случай нечетного т. Легко заметить, что тДт для всех у, поэтому т нечетно, т. е. с( = 0 для всех г = 1,...,к. Второй и последний случай — т четно и х'/э = — 1 (шос1 Ю). Тогда х'/з = -1 (шоб р '), т. е.
ту,~ (т/2). Поскольку т ~т, то Н1 = сС для всех 11 На основе теорем П4.11 и П4.13 можно построить алгоритм, который с большой вероятностью находит нетривиальный делитель составного числа Ф. С помощью классического компьютера могут быть эффективно выполнены все шаги этого алгоритма, кроме (по крайней мере, так считается на данный момент) «подпрограммы» нахождения порядка. Повторяя алгоритм достаточное П4.4.
Цепные дроби 769 число раз, мы разложим число Ф на простые множители. Полное описание алгоритма приводится ниже. 1. Если И четное, выдать делитель 2. 2. Определить (с использованием упр. 5.17), имеет ли число М вид а» дня целых чисел а > 1 и Ь > 2; если имеет, то выдать делитель'а. 3. Выбрать случайное число х в диапазоне от 1 до (17 — 1). Если НОД(х, 1»') > 1, выдать делитель НОД(х, Ж).
4. Найви порядок г элемента х по модулю Ф (используя процедуру нахождения порядка) . 5. Если г четное и х"~з ф — 1 (шоб Ж), то вычислить НОД(х'7з — 1,М) и НОД(х'~з + 1, Ф). Проверить, какое из этих двух чисел является нетривиальным делителем, и выдать это число. В противном случае алгоритм не дает результата.
Шаги 1 и 2 данного алгоритма либо выдают делитель, либо сообщают, что Ж является нечетным числом с более чем одним простым делителем. Для выполнения этих шагов требуется 0(1) и 0(ХР) операций соответственно. Шаг 3 либо выдает делитель, либо выбирает случайный элемент х из Е;~. Шаг 4 вызывает процедуру нахождения порядка элемента, вычисляя порядок т элемента х по модулю М. Шаг 5 завершает алгоритм, поскольку в соответствии с теоремой П4.13, с вероятностью не менее 1/2 число т четно и при этом х"~з ф — 1 (шод Ф), а теорема П4.11 утверждает, что либо НОД(х"~з — 1, Ф), либо НОД(х'~з + 1, Ф) является нетривиальным делителем числа Ж.
Упрвжыеыие П4.17 (сведение нахождения порядка к разложению ыа простые множители). Выше было доказано, что, умея быстро находить порядок элемента, можно быстро разложить числа на простые множители. Покажите, что эффективный алгоритм разложения на простые мыожители позволяет эффективно находить порядок по модулю М любого взаимно простого с 1У числа х. П4.4 Цепные дроби Здесь будет дано небольшое введение в теорию цепных дробей. Эта тема имеет существенное значение для применения быстрых квантовых алгоритмов нахождения порядка и разложения на простые множители, описанных в гл.
5. В качестве примера цепной дроби рассмотрим число з, определяемое выражением 3 †1 (П4.34) г+ —,ф-' При неформальном подходе можно написать уравнение з = 1/(2+ з), откуда следует, что з = ~/2 — 1. Иден метода цепных дробей заключается в описании действительных чисел только с помощью целых, используя выражения, 49 к»»»»в»» 770 Приложение 4. Теория чисел . аналогичные (П4.34).
Конечная цепная дробь определяется конечным набором целых положительных чисел ас,..., ан, 1 [оо,...,ан] пи аэ+ а1+ - — - «-— "э (П4.35) 31 5 — = 2+ —. 13 13' (П4.36) Далее мы переносим дробную часть в знаменатель: 31 1 2+ 1г. 13 (П4.37) Эти операции — выделение целой и дробной частей и перенос дробной части в знаменатель — теперь применим к дроби 13/5: 31 1 1 2+ з 2+ 13 2+з 2+~ (П4.38) Далее выполним эти операции применительно к дроби 5/3: 31 1 1 — =2+ =2+ 13 2+ 1+1~ 2+ -ф (П4.39) На этом шаге разложение в цепную дробь заканчивается, поскольку 3/2 = 1 + 1/2, в слагаемом 1/2 в числителе стоит единица, и перенос этой дробной части в знаменатель не требуется.
Окончательное представление числа 31/13 в виде цепной дроби выглядит следующим образом: 31 1 — =2+ 13 2+ «1 ь|4 (П4.40) Ясно, что алгоритм нахождения цепной дроби завершится после конечного числа шагов «разбиения на целую и дробную части и переноса дробной части Будем называть и й подходящей' дробью (О < и < г7) к этой цепной дроби набор [ас, а„]. Теорема П4.14. Пусть х — рациональное число, не меньшее единицы. Тогда существует представление числа х в виде цепной дроби: х = [ае,..., аи], кото- рое может быть найдено с помощью алгоритма нахождения цепных дробей, построенного на основе алгоритма Евклида. До«газатиельспмго.
Идею цепных дробей легче всего понять на конкретном примере. Найдем представление числа 31/13 в виде цепной дроби. Первый шаг алгоритма заключается в выделении в числе 31/13 целой и дробной частей: П4.4. Цепные дроби 771 [ао,, ап] = —, (П4.41) Чп гДе Рп и Чп — действительные числа, опРеДелЯемые по инДУкЦии слеДУюЩим образом: Рс ы ао Че ьз 1, Р, = 1+ аеа1, Ч1 ее а1, (П4.42) (П4.43) Рпьзапрп 1+р. 23 Ч ьз впЧп-1 + Чп-2 где 2 < п < 1У.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
