М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 182
Текст из файла (страница 182)
ЯснО, что гц.з < гд.ы поэтому ц~.з < т;/2. ° г;~.~ ) г,'/2. Тогда г; = 1.т;.ь~+г;.ьз, следовательно, тн~.з = тс-г;~~ < г;/2. Поскольку гь!.з < г;/2, операция деления с остатком в алгоритме Евклида должна быть выполнена не более чем 2 !!о8 а~! = 0(Е) рэз (где ! х'! — минимальное целое, не меньшее х). Каждое деление с остатком требует 0(1Р) операций, так что для всего алгоритма Евклида потребуется 0(Ьз) операций. Нахождение таких чисел х и у, что ах+ бр = НОД(а, 5), требует еще и 0(Ь) подстановок, для каждой из которых необходимо выполнить 0(ЕР) операций, поэтому всего понадобится 0(1.~) операций.
Алгоритм Евклида также может быть использован для эффективного поиска мультипликативных обратных в арифметике остатков. Это неявно вытекало Найдем НОД(6825, 1430) с помощью алгоритма Евклида: 6825 = 4 1430+ 1105, 1430 = 1 ° 1105+ 325, 1105 = 3. 325+ 130, 325 = 2 130+ 65, 130 = 2 65. 65 = 325 — 2 130 = = 325 — 2 (1105 — 3 325) = -2 1105 + 7 325 = = — 2 1105 + 7 ° (1430 — 1 ° 1105) = 7 1430 — 9 ° 1105 = = 7 1430 — 9 (6825 — 4 ° 1430) = †9 ° 68 + 37 1430.
(П4.4) (П4.5) (П4.6) (П4.7) (П4.8) (П4.9) (П4.10) (П4.П) (П4.12) П4.2. Арифметика остатков и алгоритм Евклида 763 вз доказательства следствия П4.4; теперь можно доказать это в явном виде. Пусть числа а и и — взаимно простые, и мы хотим найти а 1 по модулю и. Поскольку ИОД(а, и) = 1, с помощью алгоритма Евклида можно найти такие целые числа х и у, что (П4.13) ах + ир = 1.
Заметим, что ох = 1 — иу = 1 (пюй и), т. е. число х является мультипликативным обратным числу а (по модулю и). Более того, этот алгоритм эффективен с точки зрения затраченных ресурсов — требуется только 0(Ь~) операций, где Ь вЂ” количество битов в записи числа и.
Теперь нам известен эффективный способ поиска мультипликативных обратных в арифметике остатков. С его помощью легко решать простые линейные уравнения вида ах+6=с (пюйи). (П4.14) Пусть а и и — взаимно простые целые числа. С помощью алгоритма Евклида можно быстро найти число а 1 — обратное а (по модулю и), а следовательно, и решение предыдущего уравнения: х = а (с — э) (пюй и).
(П4.15) Следующим важным результатом является китайская теорема об остатках, расширяющая круг уравнений, которые мы можем решить. Из этой теоремы вытекает метод решения систем уравнений в арифметике остатков. Теорема П4.6 (китайская теорема об остатках). Пусть тм..., т„— та- кие положительные целые числа, что любые два из них т; и т (1 ф 1)— взаимно простые. Тогда система уравнений х = а1 (пюй т1), х = аз (шой тз), (П4.16) (П4.17) х = а„(пюй т„) (П4.18) имеет решение.
Более того, любые два решения этой системы дают одинаковый остаток по модулю М = т1тз х ... х т„. доказательство. Доказательство будет заключаться в явном построении решения системы уравнений. Введем обозначение М; ге М/т; и заметим, что т; и М; — взаимно простые числа.
Поэтому для числа М; существует мультипликативное обратное (обозначим его Ф;) по модулю т;. Обозначим х ги ~ „. а;М;Мь Заметим, что М;1У; = 1 (пюй т;) и М;1У; = О (пюй тз) при 1 ф,1, поэтому х = а; (пюй т;), отсюда следует существование решения исходной системы уравнений. Предположим, существуют два решения исходной системы уравнений: х и х'. Тогда х — х' = О (гпой т;) для всех 1, поэтому т; делит х — х' для любого г.
Поскольку все числа т; попарно взаимно простые, произведение М = т1 х ... х т„также делит х — х', т. е. х = х' (шой М), что и требовалось доказать. 764 Приложение 4. Теория чисел Алгоритм Евклида и китайская теорема об остатках — наиболее яркие достижения алгоритмической теории чисел. Тем более забавно, что именно они играют важную роль в последовательности идей, ведущих к ВЯА-криптосистемам, защищенность которых базируется на с«ожиости выполнения некоторых алгоритмических задач в теории чисел.
Перейдем к основам теории чисел, необходимым для понимания ВЯА-криптосистем. Основная идея заключена в знаменитом факте классической теории чисел — малой шеореме Ферма, которую следует отличать от последней («Великойь) теоремы Ферма, а также в выполненном Эйлером обобщении малой теоремы Ферма. Доказательство малой теоремы Ферма опирается на следующую красивую лемму. Лемма П4.7. Пусть р — простое число, Й вЂ” целое число, лежащее в диапазоне. от 1 до (р — 1). Тогда р делит Я) . Дояазательстпво. Запишем тождество р(р — 1) х ... х (р — Й+ 1) = ( ) Й(Й вЂ” 1) х... х 1.
(П4.19) Й Поскольку Й > 1, левая часть (а следовательно и правая) делится на р. Учитывая, что Й < р — 1, заключаем, что множитель Й(Й вЂ” 1) х ... х 1 не делится на р. Следовательно, множитель („") должен делиться на р. Теорема П4.8 (малая теорема Ферма). Пусть р — простое число, а — любое целое. Тогда аг = а (шод р). Если а не делится нар, то а" « = 1 (шоб р), Дояпзатааьс«пво. Второе утверждение теоремы следует из первого, поскольку если число а не делится на р, то для него существует мультипликативное обратное по модулю р, поэтому а" ~ = а ~ах = а ~а = 1 (шод р). Докажем первое утверждение теоремы для положительного а (случай неположительного а является простым следствием) индукцией по а.
При а = 1 получим а" = 1 = а (шод р). Предположим, первое утверждение теоремы выполнено для а, т. е. а" = а (шод р) и докажем его для (а+ 1). Запишем биноминальное разложение (П4.20) Согласно лемме П4.7, р делит (гь) при 1 < Й < р — 1, поэтому все члены, кроме первого и последнего, дают остаток О по модулю р: (1+ а)г = (1+ а") (шой р).
Поскольку а" = а (шест р), получим (1+ а)г = (1+ а) (шо«1 р), что и требовалось доказать. Существует замечательное обобщение малой теоремы Ферма, принадлежащее Эйлеру. Оно использует понятие функции Эйлера «х у(п) определяется как число положительных целых чисел, меньших п и взаимно простых с и. Например, нетрудно заметить, что все положительные целые числа, меньшие простого р, взаимно просты с р, следовательно, у(р) = р-1. С числом р будут взаимно простыми только числа, кратные р: р, 2р, Зр,..., (р'" ~ — 1)р. Отсюда следует, что (П4.21) П4.2. Арифметика остатков и алгоритм Евклида 765 Далее, если а и Ь взаимно простые, то в соответствии с китайской теоремой об остатках имеем ~р(аЬ) = ~р(а)~р(Ь).
(П4.22) Чтобы доказать этот факт, рассмотрим систему уравнений х = х„(пюд а), х = хь (шос1 Ь). Применяя китайскую теорему об остатках к этой системе уравнений, легко установить взаимно однозначное соответствие между такнми парами (х„хь), что 1 < х, < а, 1 < хь < Ь, НОД(х„а) = 1, НОД(хь, Ь) = 1, и такими целыми числами х, что 1 < х < аЬ, НОД(х, аЬ) = 1. Всего существует у(а)у(Ь) таких пар (х„хь) и у(аЬ) чисел х; таким образом, равенство (П4.22) доказано. Уравнения (П4.21) и (П4.22) приводят к формуле для у(п), использующей разложение числа п на простые множители (и = р~)' х ...
х р~,"): (П4.23) Упражнение П4.10. Найдите <р(187). Упражнение П4.11. Докажите, что и = ~~~ у(ы), (П4.24) Доназагпельстпво. Сначала покажем индукцией по а, что ат~г ) = 1 (пюб р ). Для а = 1 это утверждение сводится к малой теореме Ферма. Предположим, что утверждение верно для о > 1, т. е. ат(г ) 1+Ьра (П4.25) для некоторого целого й.
Тогда согласно уравнению (П4.21) имеем а~~э ) = а" ~" ') = (П4.26) (П4.27) (П4.28) = аг"'~" ) = =(1+Ьр )г= (П4.29) где суммирование ведется по всем целым положительным делителям а числа и, включал 1 и и. (Уяиакпе: сначала докажите это утверждение для п = р'", а для завершения доказательства воспользуйтесь свойством (П4.22).) Существует следующее (докэзанное Эйлером) красивое обобщение малой теоремы Ферма. Теорема П49.
Пусть числа а и и — взаимно-простые. Тогда а')э) = 1 (пюд п). 766 Приложение 4. Теория чисел Используя лемму П4.2, легко показать, что р +~ делит все члены, стоящие под знаком суммы, так что а"'(" ~ = 1 (шоб р~+~), (П4.30) т. е. индуктивный переход доказан. Для завершения доказательства теоремы следует заметить, что для произвольного п = р~' х ... х р'" при каждом у выполняется равенство аэ~"> = 1 (шоб р '), поскольку у(п) делится на ~р(р ~ ). Применяя конструкцию, построенную при доказательстве китайской теоремы об остатках, можно заметить, что любое решение системы уравнений х = 1 (пюй р ')) должно удовлетворять условию я = 1 (шоб п), поэтому а"<"~ = 1 (шо4 и).
Введем обозначение Е'„для множества всех элементов Е„, для которых существуют мультипликативные обратные элементы по мовулю и, т. е. для множества тех элементов Е„, которые взаимно простые с п. Легко видеть, что множество Е,", является группой по умножению (это означает, что Е„' содержит единичный элемент, мультипликативные обратные для всех своих элементов, а также произведение любых двух элементов; обзор элементарной теории групп дан в Приложении 2), а ее мощность равна ~о(п).
Оказывается, группа Е'„обладает весьма интересной структурой, если и является степенью нечетного простого числа р (и = р ). Такая группа Ер является циклической, т. е. существует элемент д из Е', порождвющий группу Е„': любой элемент х группы Е" может быть представлен в виде з = д" (шод и) с некоторым неотрицательным Й. Теорема П4.10. Пусть р — нечетное простое число, а — положительное целое число. Тогда группа Ер является циклической. Домазатпельсгпво.
Доказательство этой теоремы выходит за рамки нашей книги. Его можно найти в разных учебниках по теории чисел, см., например, разд. 3.2 книги Кнута [225]. Упражнение П4.12. Докажите, что Е„" — группа относительно операнди умно- жения по модулю и, а ее мощность равна у(п). упражнение П4.13.
Пусть а — произвольный элемент группы Е;,. Докажите, что множество Я ьч (1, а, аэ,...) образует подгруппу в Е;, и что мощность Я равна наименьшему целому числу т, удовлетворяющему уравнению а" = 1 (пюй и). Упражнение П4.14. Пусть д — образующая группы Е„'. Покажите, что по- рядок элемента д равен у(п). 'Упражнение П4.15. Теорема Лагранжа (теорема П2.1) утверждает, что мощность подгруппы делит мощность группы. Докажите теорему П4.9 (а~<"> = 1 (шоб п) для любого а б Е'„) другим способом — с использованием теоремы Лагранжа. П4.3. Сведение разложения на простые множители 767 П4.3 Сведение разложения на простые множители к нахождению порядка элемента Задача разложения на простые множители с помощью классического компьютера оказывается эквивалентна другой задаче — нахождению порядка.
Этот факт очень важен, поскольку с помощью квантового компьютера можно быстро решать задачу нахождения порядка, а значит, можно осуществить и быстрое разложение на простые множители. В этом разделе мы покажем эквивалентность этих двух задач, фокусируя внимание читателя именно на сведении разложения на простые множители к нахождению порядка. Пусть М вЂ” положительное целое число, х — число, взаимно простое с И и 1 < х < Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
