М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 184
Текст из файла (страница 184)
В случае, когда все ау — целые положительные числа, таковыми же являются все числа р и Ч». До««азапгелъспгно. Проведем индукцию по п. Утверждение легко проверяет- ся для и = О, 1, 2. По определению, для п > 3 имеем [ао,..., ап) = [ас,..., ап 2, ап 1 + 1/ап]. (П4.44) Применим предположение индукции. Введем обозначение ру/Чз для последовательности подходящих дробей цепной дроби в правой части равенства (П4.41): Рп-1 [пе ° ° ° оп-2 оп-1 + 1/оп) = = Чп-1 (П4.45) ОЧЕВИДНО, ЧтО Р -З = Р -З, Р -2 = Рп 2 И Ч -З = Ч -З, Ч -2 = Чп-г, ПОЭТОМУ Р вЂ” (а -1 + 1/ ' )Р -2 + Р -з (П4.46) Чп 1 (ап 1+1/ап)Чп-2+Ч -з Р -1+Рп-г/ап Чп 1+Чп 2/ап (П4.47) 49' в знаменатель», поскольку числители (в нашем примере 31, 3, 2, 1) образуют последовательность убывающих целых положительных чисел. Как быстро алгоритм завершит свое выполнение? Этот вопрос будет рассмотрен ниже.
° Доказанная выше теорема относилась к числам з > 1; на практике удобно отказаться от условия ае > О и допустить, чтобы число ае принимало любые целые значения, что сделает ограничение з > 1 излишним. В частности1 если х лежит в диапазоне от О до 1 (что характерно для применений в квантовых алгоритмах), то в разложении в цепную дробь число ас будет равно нулю. Алгоритм разложения в цепную дробь дает однозначный способ нахождения цепной дроби для заданного рационального числа. Неопределенность может возникнуть только на последнем шаге, поскольку целое число можно представить двумя разными способами: ап = ап или ап пп (ап — 1) + 1/1, что дает два разных представления в виде цепной дроби.
Эта неопределенность очень важна, поскольку при этом можно считать, что в разложении рационального числа содержится либо четное, либо нечетное число «этэжей». Тогда в зависимости от требований задачи можно выбирать дробь с четным или нечетным числом «этажей». Упражнение П4.18. Выпишите разложение в виде цепных дробей для чисел х = 19/17 и х = 77/65. Теорема П4.15. Пусть ае,...,ан — последовательность положительных чисел. Тогда 772 Приложение 4. Теория чисел Умножая числитель и знаменатель правой части на а„, обнаруживаем, что р»-1 р» Ч»-~ Ч» (П4.48) Из уравнений (П4.48), (П4.44) и (П4.45) следует равенство (е . »)=— = р» Ч» (П4.49) что и требовалось доказать.
Упражнение П4.19. Покажите, что д„р»-~ — р„д„« = ( — 1)" для н > 1. Докажите (используя этот факт), что НОД(р„, д„) = 1. ( Указание: примените индукцию по и.) Насколько много значений а„необходимо вычислить, чтобы получить разложение в цепную дробь для рационального числа х = р/д > 1, где р и д— взаимно простые числа? Пусть ае,..., ан — положительные целые числа. Из определения чисел р„и д„следует, что р„и Ч„образуют возрастающие последовательности. Поэтому р„= а»р»-~ + р»-в > 2р» э (аналогично д„> 2Ч»-э), а следовательно, р„,д„> 2(»~э~ (где выражение ~х1 обозначает целую часть числа х). Значит, 2(и~э" < д < р, т. е.
57 = О(!обр). А следовательно, если х = р/Ч вЂ” рациональное число и числа р и д записываются с помощью Ь бит каждое, то разложение числа т в цепную дробь может быть вычислено за 0(Ь~) операций: 0(Ь) операций «выделения целой и дробной частей и переноса дробной части в знаменатель», каждая из которых требует 0(Ьз) элементов для простейших арифметических операций.
Теорема П4.16. Пусть я — рациональное число, а р/д — такое рациональное число, что р ~ 1 — — в < —. (П4.50) Р» т= — + — з Ч„ 2дэ (П4. 51) (очевидно, что ф~ < 1). Определим число А соотношением Ч~Р»-ь Р»д»-ъ Я~-~ (П4.52) Из определения числа Л следует, что Лр„+ р„, Ж = Лд„+ д„, ' (П4.53) Тогда р/д — некоторая подходящая дробь для числа х. Доназа«пельсгиво. Пусть [ае,..., а„) — разложение в виде цепной дроби для числа р/д. Определим р и ду, как в теореме П4.15, причем р„/д„= р/д. Зада- дим число Б соотношением П4.4.
Цепные дроби 773 а следовательно, х = [ао,...,а„,Л]. Сделав п четным числом, с учетом упр. П4.19 легко убедиться в справедливости равенства 2 9„-1 Л = — —:. б 9„ (П4.54) Поскольку числа д„образуют возрастающую последовательность, имеем Л = — — — > 2 — 1 > 1. 2 9„1 б 9„ (П4.55) Следовательно, Л вЂ” рациональное число, большее единицы, поэтому его можно представить в виде конечной цепной дроби Л = [6с,..., 6 ], т. е. х = [ас,..., а„, 6с,..., 6т] — конечная цепная дробь, а р/9 — подходящая дробь для этой цепной дроби.
1. Докажите, что и < 1оя (~„") . 2. Покажите, что (П4.56) где суммирование ведется по всем простым р, не превосходящим 2п. 3. Используя два предыдущих пункта, покажите, что я(2п) > 1оя2п (П4.57) История и дополнительная литература По теории чисел написано много превосходных учебников. Мы существенно использовали материал из книги Коблитца [227], которая содержит начальные сведения как по теории чисел, так и по алгоритмам и криптографии. Глава 33 книги Кармена, Лейзерсона и Ривеста [92] (представляющей собой всесторонний труд, посвященный, в основном, алгоритмам) содержит схожую подборку вводных курсов.
Введение в теорию цепных дробей в данном приложении базируется на гл. 10 классического учебника по теории чисел [195]. Задача П4.4 взята вз работы [312]. Задача П4.1 (оценка количества простых чисел). Пусть я(п) — количество простых чисел, меньших и. Утверждение, известное как асимптстический закон распределения простых чисел (доказательство которого весьма нетривиально) гласит, что !пп„, я(п) 1пп/и = 1, а следовательно, я(п)— и] 1пп. Данная задача является более слабым аналогом теоремы о простых числах и дает неплохую нижнюю оценку для количества простых чисел.
Приложение 5 КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМ И СИСТЕМА ВЯА Криптография — это искусство тайного общения двух лиц. Например, если клиент собирается сделать покупку с помощью Интернета, он хотел бы передать номер своей кредитной карты по сети так, чтобы его узнала только та компания, где он делает покупку. Приведем более жестокий пример: во время войны каждая вз воюющих сторон хочет иметь возможность конфиденциального общения. Для обеспечения этого используется криптографический протокол, или криптосистема Эффективная криптосистема позволяет двум сторонам взаимодействовать, делая при этом «подслушивание» со стороны затруднительным. Очень важным классом криптосистем являются криптосистемы с вткрмтил«ключам. Основная идея шифрования с открытым ключом проиллюстрирована на рис. П5.1.
Алиса устанавливает почтовый ящик, обладающий следующими свойствами: любой человек может оставить сообщение для нее, но только она может забрать почту из ящика. Чтобы обеспечить такую возможность, в ящике предусмотрены две дверцы. На крышке ящика имеется закрывающаяся входная дверца, и любой, кто может ее открыть, может бросить письмо в ящик.
Но эта щель «односторонняя», т. е. через нее нельзя вынуть почту из ящика. Алиса предоставляет ключ от верхней щели всем — зто открытый ключ, т. е. она может получать почту от любого человека. На передней стенке ящика имеется вторая дверца, через которую можно достать находящуюся внутри почту. Единственный ключ от этой дверцы находится у Алисы — это ее секретп»Ж ключ. Такая система с двумя ключами — открытым и секретным — позволяет любому желающему передавать Алисе конфиденциальные сообщения.
Криптографические системы с открытым ключом работают по схожи1в правилам. Предположим, Алиса хочет получать сообщения, используя такую систему. Она должна создать два криптографических ключа: откр»«тмй Р и секретный о'. Конкретный вид этих ключей зависит от особенностей используемой криптографической системы. В некоторых криптографических системах в качестве ключей используются простые объекты, например, числа, в других— более сложные математические объекты, такие, как эллиптические кривые. После того как Алиса создала свои ключи, она «публикует» открытый ключ, т.
е. предоставляет доступ к нему всем желающим. Пусть теперь Воб хочет послать Алисе конфиденциальное сообщение. Сначала он получает созданный Алисой открытый ключ Р, потом шифрует сообщение, предназначенное для отправки Алисе, с помощью этого открытого клю- Приложение 5. Криптография с открытым ключом и система ВЯА 775 ча.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
