М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 186
Текст из файла (страница 186)
Эти задачи — нахождение порядка элемента и разложение числа на множители. К сожалению, достоверно неизвестно даже, является ли система ВЯА надежно защищенной, если обе эти проблемы трудноразрешимы. (Может оказаться так, что обе указанные проблемы действительно сложны для решения на классическом компьютере, однако есть какой-то другой способ взлома системы ВЯА.) Несмотря на вышесказанное в течение двух с лишним десятилетий все попытки взлома системы ВЯА не привели к «успеху», и именно поэтому принято считать, что система ВЯА надежно защищена от взлома с использованием классического компьютера.
Приложение 5. Криптография с открытым ключом и система ВЯА 779 Задача П5.1. Напишите программу на любом языке программирования, которая выполняет шифрование и дешифрование с использованием системы ВЯА. Найдите два 20-битовых простых числа и с их помощью закодируйте 40-битовое сообщение.
История и дополнительная литература Криптографические системы с открытым ключом были придуманы Диффи и Хеллманом в 1976 г. [120], а также независимо Мерклом (примерно в то же время, хотя его работа была опубликована только в 1978 г. [280)). Вскоре после этого Ривест, Шамир и Адлеман [342) изобрели систему ВЯА. В 1997 г. было обнаружено, что эти идеи — криптография с открытым ключом, а также системы Диффи-Хеллмана и ВЯА — были на самом деле изобретены в конце 1960-х и начале 1970-х годов исследователями из Британской разведывательной службы ОСН1]. Отчет об этих работах находится в Интернете по адресу: МФр://ипээч.сее8.8ошп1с/аЬоиФ/пеесгес/. Проверки на простые числа (тесты Миллера-Рабина и Соловея — Штрассена) описаны в замечательной книге Коблица [227] по теории чисел и криптографии, содержащей также дополнительный материал по криптографии с открытым ключом.
Эти способы проверки простоты чисел были первыми примерами вероятностных алгоритмов, более эффективных, чем соответствующие детерминированные. Алгоритм Соловея-Штрассена описан в [367), а алгоритм Миллера-Рабина — в работах [281] и [331]. Приложение 6 ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ ЛИБА Одним из самых важных и полезных результатов в теории обработки квантовой информации является нериеенстпео сильной субаддитиености для энтропии фон Неймана: для трех квантовых систем А, В и С выполняется условие (П6.1) Я(А, В,С) + Я(В) < Я(А,В) + Я(В,С).
К сожалению, наглядное доказательство этого факта неизвестно. В гл. 11 приведено достаточно простое доказательство с использованием так называемой теоремы Лий. В данном Приложении приводится ее доказательство. Начнем с обозначений. Пусть у(А, В) — действительнозначная функция матриц А и В. Функция у называется совместно-вогнутой по А и В, если для любого Л, удовлетворяющего условию О < Л < 1, выполняется неравенство ,((ЛА1 + (1 — Л)Аю ЛВ1 + (1 — Л)Вз) > ЛДАы В1) + (1 — ЛЩАю Вэ). (П6.2) Будем говорить, что А < В, если матрица  — А является неотрицательно определенной.
Соответственно А > В означает, что В < А. Пусть А — произвольная матрица. Определим норму матрицы А следующим образом: (П6.3) )(А~( = шах ((и)А)п)!. При доказательстве теоремы Лаба понадобятся следующие легко проверяемые утверждения. Упражнение П6.1 (отношение «<» сохраняется при сопряжении). Покажите, что если А < В, то ХАХ1 < ХВХ1 для любой матрицы Х. Упражнение П6.2. Докажите, что А > О тогда и только тогда, когда А— неотрицательно определенный оператор. Упражнение П6.3 (отношение «<» задает частичный порядок).
Покажите, что отношение < задает частичный порядок на операторах, т. е. транзативно (А < В, В < С =» А < С), антисимметрично (А < В, В < А, =» А = В) и рефлексивно (А < А). Упражнение П6.4. Пусть матрица А обладает собственными значениями Л,. Обозначим максимальный элемент множества ~Л,~ буквой «Л». Докажите, что 1. ()А() > Л; 2. если матрица А эрмигова, то ~(А6 = Л; Приложение 6.
Доказательство теоремы Либа 781 3. если А= [ (П6.4) то [[А[] = 3/2 > 1 = Л. Упражнение П6.7. Пусть А — неотрицательно определенная матрица. Покажите, что ][А[[ < 1 тогда и только тогда, когда А < 1. 'Упражнение П6.8. Пусть А — неотрицательно определенная матрица. Определим супероператор (линейный оператор на множестве матриц) уравнением А(Х) ж АХ.
Покажите, что супероператор А будет неотрицательно определенным относительно скалярного произведения Гильберта-Шмидта. (Это означает, что Фг(ХсА(Х)) > О для любого Х.) Покажите аналогичным образом, что и супероператор, определяемый равенством А(Х) ж ХА, будет неотрицательно определенным относительно скалярного произведения Гильберта-Шмидта. Вооружившись этими фактами, можно приступить к формулировке и доказательству теоремы Либа. Теорема П6.1 (теорема Лнба). Пусть Х вЂ” матрица, О < 1 < 1.
Тогда функ- ция /(А,В) ьэ Фг(ХсАсХВ' ') (П6.5) является совместно вогнутой для неотрицательно определенных матриц А и В. Теорема Либэ легко выводится из следующей леммы. Лемма П6.2. Пусть Вс, Вз, Яс, Яз, Тс, Тз — такие неотрицательно определенные операторы, что О = [Вс, Вз] = [Яс, Яз] = [Тм Тз] и (П6.6) (П6.7) В >Вс+Тс, В2 ~ 1оз + Т2. Тогда для любого 1, удовлетворяющего условию О < с < 1, выполняется следу- ющее матричное неравенство: ВсВс-с > ВсВс-с + ТсТс-с э се се (П6.8) Доназапсельсспвв.
Сначала докажем частный случай утверждения: $ = 1/2, а потом используем этот случай для доказательства при произвольном й Удобно Упражнение П6.5. Докажите, что матрицы АВ и ВА имеют одинаковые собственные значения. (Указание: Докажите для обратимой матрицы А, что с1еФ(х1 — АВ) = бес(х1 — ВА), а следовательно, собственные значения матриц АВ и ВА одинаковые.
По непрерывности это утверждение можно распространить и на случай необратимой матрицы А.) Упражнение П6.6. Пусть матрицы А и В таковы, что А — эрмитова матрица. Используя предыдущие два упражнения, покажите, что []АВ[] < ][ВА][. считать матрицы В1 и Вг обратимыми (доказательство в случае, когда хотя бы одна из матриц необратима, оставим читателю в качестве несложного упражнения — необходимо только немного модифицировать доказательство, приведенное ниже). Пусть |х) и ~ у) — векторы.
После двукратного применения неравенства Коши- Шварца и несложных преобразований получим, что (П6.9) (П6.10) (П6.11) (х)(Я1 + Т1)(х)(уИЯг + Тг) ~у). (П6.12) Пусть ~и) — произвольный вектор единичной длины. Применив формулу (П6.13) с (х) ке В1 1/ (и) и )у) ке Вг 1/ 1и), получим соотношения ( (В-1/2(с1/2 о1/г + Т1/2Т1/г)Вг-1/г~ ) (П6.14) (П6.15) (П6.16) Введем следующие обозначения: (П6.17) (П6.18) Заметим, что А — эрмитова матрица, поэтому из упр. Пб.б и предыдущих неравенств следует, что 782 Приложение 6.
Доказательство теоремы Либа < ((х(Я,/ Яг/ (у)(+ ((х(Т1/ Тг/ )у)! < ао1 1х)!Щ !уЦ + !(Т1 1хЦ//Тг !уЦ Согласно предположению, 31 + Т1 < В1, Яг + Тг ~< Вг, поэтому имеем следовательно, ~~В-1/2(31/231/2 + Т1/гт1/2)В-1/2~! < 1 В-1/4В-1/4 ~В1/2В1/г Т1/2Т1/21 о-1/2 12(12+12)'2 В = В1/4В 1/4 2 1 ((В 1/4В 1/4(51/251/2 + Т1/2Т1/2) В 1/4 В 1/4 = )(АВ(! < )(ВА!) аВ-1/2(о1/гВ1/г Т1/2Т1/2)В.
1/га (1, (П6.19) (П6.20) (П6.21) Приложение 6. Доказательство теоремы Либа 783 где последнее неравенство непосредственно совпадает с (П6.16). Оператор АВ является неотрицательно определенным, поэтому из упр. П6.7 и предыдущего неравенства следует соотношение Наконец, из упр. П6.1 и коммутативности матриц В1 и Л2 получим $1/2$1!2+ Т1|2ТЦг < Л1/2Р1/2 г + 1 г -- 1 "2 (П6.23) что означает справедливость неравенства (П6.8) при Ф = 1/2. Пусть теперь 1 — множество всех чисел 1, для которых выполняется неравенство (П6.8).
Очевидно, что Е содержит 1 = О и Ф = 1; кроме того, мы только что убедились, что Ф 1/2 также принадлежит множеству 1. Докажем теперь неравенство (П6.8) для произвольного Ф, лежащего в диапазоне от О до 1. Пусть числа р и й принадлежат множеству В М'Е~~ "> Б"$1 " Т"Т1 " 1 2 1 2 + 1 2 1 Я"21~ " > Б"$1 "+ Т"Т1 2 -- 12 (П6.24) (П6.25) Легко видеть, что эта пара неравенств — частный случай пары неравенств (Пб.б) и (П6.7). Согласно доказанному для случая 2 = 1/2, получим, что (яв „)Иэ(лэд1 „) > (БРБ1 „)Ц2 ( „$1 „)1/2 + (Т"Т1 ") (Т"Т1 ") .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
