Исследование стойкости квантово-криптографических протоколов распространения ключей

Объект исследования и актуальность темы.

Квантовая криптография [1, 2], или распространение секретных ключей, в принципе позволяет реализовать абсолютно стойкие (не дешифруемые подслушивателем даже теоретически) системы шифрования с одноразовыми ключами [3, 4]. Секретность ключей в квантовой криптографии основана на фундаментальных запретах квантовой механики [5], а именно, на том обстоятельстве, что пара наблюдаемых, которым отвечают некоммутирую-щие операторы, не может быть достоверно одновременно различима, что является следствием соотношений неопределенности Гейзенберга. В квантовой криптографии в качестве таких наблюдаемых выступают матрицы плотности информационных состояний, соответствующих классическим битам 0 и 1. Для чистых состояний одновременная ненаблюдаемость (достоверная неразличимость) матриц плотности эквивалентна неортогональности информационных квантовых состояний [6]. Сказанное означает, что не существует измерений, которые с вероятностью единица позволяют различать одно из пары неортогональных состояний и так, чтобы после измерения система оказалась в исходном состоянии, в котором она была до измерения. Таким образом, любое измерение, если оно дает информацию о передаваемых состояниях, неизбежно приводит к их возмущению, что позволяет детектировать любые попытки подслушивания в канале связи. Другими словами, подслушивание (соответственно возмущение состояний) передаваемых состояний должно неизбежно приводить к изменению статистики результатов измерений на приемном конце по сравнению со статистикой результатов измерений на невозмущенных состояниях. Искажение квантовых состояний возникает в неидеальном квантовом канале, что также приводит к изменению статистики результатов измерений. В квантовой криптографии принципиально невозможно отличить изменение статистики результатов по сравнению с идеальным случаем, возникающих за счет шума в канале или от действий подслушивателя, поэтому любые изменения статистики приходится относить на действия подслушивателя.

Если бы законы квантовой механики позволяли обнаруживать только сам факт возмущения передаваемых состояний, то это было бы бесполезно для целей криптографии, точнее передачи ключей. Квантовая механика позволяет не только обнаруживать возмущение состояний, но и связать изменение статистики результатов измерений с количеством информации, 6 которое может быть получено подслушивателем при наблюдаемом изменении статистики отсчетов по сравнению с идеальным случаем.

В квантовой криптографии кроме квантового канала связи (в реальных условиях это либо оптоволокно, либо открытое пространство), по которому передаются квантовые состояния, необходим также открытый классический канал связи. Классический открытый канал связи необходим для выяснения легитимными пользователями изменений статистики отсчетов и коррекции ошибок в первичном ключе, переданном по квантовому каналу связи. Единственное требование, которое предъявляется к классическому каналу связи состоит в том, что передаваемая открыто и доступная всем, включая подслушивателя, классическая информация не могла быть изменена подслушивателем — сохраняла целостность (так называемый unjammable channel). Такой открытый классический канал является математической идеализацией, поскольку подобных каналов в природе не существует. Для сохранения целостности открыто передаваемых классических данных в реальных условиях необходимо использовать процедуры аутентификации и контроля целостности данных. Для подобных процедур в свою очередь требуется секретный ключ.

Если в качестве открытого классического канала используется, например, интернет, то для целей аутентификации возможна генерация ключей по схеме Хеллмана-Диффи [7]. Если же для открытого классического канала используется та же самая оптоволоконная линия, что и для квантового канала связи, то генерация ключей для аутентификации по схеме Хеллмана-Диффи оказывается принципиально неприемлемой из-за очевидной, так называемой атаки «man in the middle». В такой ситуации требуется небольшой стартовый ключ один раз при первом сеансе. При последующих сеансах этот ключ выбрасывается, и для аутентификации и сохранения целостности данных, передаваемых по классическому каналу, используется часть ключа, сгенерированного по квантовому каналу в предыдущем сеансе обмена. Оставшаяся большая часть ключа, используется собственно для шифрования данных. Если для аутентификации и сохранения целостности данных используются процедуры на основе ГОСТа, то длина стартового ключа составляет 256 бит. При этом в результате работы протокола передачи ключа обмена может быть получен новый секретный ключ по квантовому каналу гораздо более длинный, чем исходный.

Разумеется, что стартовый ключ мог бы быть использован для шифрования этим ключом нового ключа и передачи его второму легитимному пользователю. Однако при этом абсолютная секретность нового ключа гарантируется лишь, если его длина не более длины ключа, на котором он шифруется. Т. е. более длинного ключа получить нельзя. В квантовой криптографии стартовый ключ не используется напрямую для передачи нового ключа, 7 который генерируется по квантовому каналу связи. Как будет видно ниже, число бит открытой информации, переданной по открытому классическому каналу на один бит нового секретного ключа меньше единицы, поэтому возможно расширение ключа.

Подход с небольшим стартовым ключом является более предпочтительным, поскольку при этом возможно свести к минимуму число раундов обмена по открытому каналу связи в процессе «чистки» и усиления секретности ключа (privacy amplification).

Основная задача теории сводится к выяснению длины секретного ключа, который может быть получен при наблюдаемых изменениях статистики результатов измерений на приемном конце по сравнению со статистикой на невозмущенных состояниях. Как правило величиной, которая характеризует отклонение статистики измерений от идеальной, является величина вероятности ошибки. Точнее, вероятности того, что переданный бит был 0, а зарегистрирован как 1, и наоборот. Хотя возможны и другие критерии для обнаружения изменения статистики.

Первым этапом любого квантового протокола распределения ключей является передача и детектирование квантовых состояний. После передачи квантовых состояний легитимные пользователи оценивают вероятность ошибки (отклонение статистики отсчетов от идеальной).

Оценка вероятности ошибки получается путем сравнения через открытый канал части переданной последовательности по квантовому каналу, в дальнейшем раскрытая часть отбрасывается.

Следующий этап состоит в коррекции ошибок в нераскрытой части последовательности у легитимных пользователей посредством обмена информацией через открытый канал связи. Обычно легитимных пользователей называют Алиса и Боб, а подслушивателя — Ева (от английского Eavesdropper). В результате коррекции ошибок остается последовательность бит меньшей длины и одинаковая у Алисы и Боба. «Одинаковая» в данном контексте означает, что их последовательности совпадают с вероятностью, сколь угодно близкой к единице (например, 1 — 2~т ~ 1 — Ю-70 при т = 200, величина параметра т выбирается легитимными пользователями). Напомним, что число атомов в видимой части Вселенной оценивается как 1077).

После «чистки» первичного ключа у подслушивателя имеется строка бит или регистр квантовой памяти с состояниями, или и то и другое вместе. Последний шаг при получении финального секретного ключа состоит в сжатии (фактически в применении случайной функции хэшировании) уже к одинаковой последовательности у Алисы и Боба. Сжатая последовательность бит является общим секретным ключом для легитимных пользователей, 8 про который гарантируется, что подслушиватель имеет о ключе экспоненциально малую информацию по некоторому, заданному Алисой и Бобом, параметру секретности.

Естественным требованием к процедурам коррекции ошибок и усиления секретности ключа является сохранение как можно большего числа бит в финальном ключе. Еще одно требование состоит в минимизации числа обменов по открытому каналу связи в пересчете на один бит в финальном секретном ключе.

При коррекции ошибок в первичном ключе задача легитимных пользователей состоит не только в исправлении ошибок, но также в оценке верхней границы информации, которую может получить об оставшемся ключе подслушиватель из обменов по открытому каналу связи. Для коррекции ошибок возможно использование различных процедур, включая хорошо разработанные классические коды, исправляющие ошибки, либо специальные итерационные процедуры, используюшие двусторонние обмены вспомогательной информацией между Алисой и Бобом через открытый канал связи. Причем заранее отнюдь не очевидно, какой из методов окажется более эффективным по упомянутым выше критериям. Целью диссертационной работы является :

1. Исследование криптографической стойкости двух основных протоколов квантового распределения ключей В92 и ВВ84 с учетом коллективной атаки подслушивателя на передаваемые квантовые состояния;

2. Определение величины критической ошибки Qc в первичных ключах на приемной стороне, до которой возможно получение общего секретного ключа легитимными пользователями;

3. Оценка длины финального секретного ключа, который можно получить при наблюдаемой вероятности ошибки Q < Qc в первичных ключах;

4. Исследование различных процедур распределенной коррекции ошибок в первичных ключах, включая процедуры с двухсторонним обменом вспомогательной информацией через открытый канал связи, а также сравнение их эффективности;

5. Разработка компьютерных алгоритмов и программ для распределенной коррекции ошибок.

Краткое содержание диссертации.

В первой главе приведено описание квантового криптографического протокола В92 и различных стратегий подслушивания. 9.

Во второй главе для протокола В92 определена критическая ошибка, до которой возможно распределение ключей для индивидуальной и коллективной атаках, получена также оценка длины секретного финального ключа в зависимости от наблюдаемой ошибки, если последняя меньше критической.

В третьей главе исследуется криптографическая стойкость основного квантового протокола распределения ключей — ВВ84. Для данного протокола ранее была найдена точная величина критической ошибки [26],[28]. Однако доказательства [26],[28] являются фактически теоремами существования, констатирующими, что при Q > Qc ~ 11% 1 Алиса и Боб не могут получить общий секретный ключ. При этом явная стратегия Евы, которая приводит к данной ошибке, неизвестна. Точнее говоря, неизвестна оптимальная стратегия подслушивания, которая дает Еве максимум информации о ключе при минимально возможной производимой ей ошибкой у Боба.

Более менее ясно, что при такой стратегии Ева должна использовать квантовую память и коллективные измерения над всей последовательностью квантовых состояний. Это убеждение возникает из того обстоятельства, что для случая индивидуальных измерений над передаваемыми состояниями, оптимальная стратегия известна и построена явно. Но при такой стратегии Евы критическая ошибка оказывается Qc ~ 15%, что выше точной границы.

Кроме того, оставался открытым вопрос о том, что происходит в области ошибок 11% < Qc < 15%. Или иначе говоря, какие стратегии Евы будут приводит к критической ошибке в «диапазоне» стратегий (коллективная атака — индивидуальная атака).

В третьей главе стратегия, на которой достигается теоретический предел критической ошибки Qc т 11%, построена явно. Кроме того, прояснен вопрос, что происходит в области ошибок 11% < Q < 15%. Показано, что существует бесконечный набор стратегий подслушивания Евы, который приводит к ошибкам в интервале 11% < Q < 15%. Установлена связь бесконечного набора стратегий с бесконечным набором классических пропускных способностей квантового канала связи. Данное явление не имеет классического аналога. Причем оказывается, что различные атаки внутри бесконечного набора отличаются только на стадии измерений. Если Ева может проводить коллективные измерения сразу над всей последовательностью квантовых состояний, то реализуется оптимальная стратегия, приводящая к критической ошибке в 11%. Если Ева может производить только индивидуальные измерния, то достигается ошибка в 15%. Если Ева может делать измерения не более, чем над к состояниями сразу (1 < к < оо), то критическая ошибка Qc (ll%) < Q^ < Qc (15%).

Критическая ошибка зависит от способа исправления ошибок. Упомянутые критиче.

3нак та используется для краткости, поскольку значение Qc определяется как корень некоторого трансцендентного уравнения.

10 ские ошибки достигаются, если легитимные пользователи используют случайные шеннонов-ские коды для исправления ошибок. Однако такая процедура является хоть и конструктивной, но практически нереализуема, поскольку требует экспоненциально большой по длине битовой последовательности таблицы кодовых слов. Шенноновские случайные коды обладают минимальной избыточностью. Поэтому количество вспомогательной классической информации, передаваемой через через канал связи, и которая доступна подслушивателю, является минимально возможным по сравнению с другими процедурами исправления ошибок.

Используемые на практике процедуры исправления ошибок имеют большую избыточность, чем процедуры, основанные на случайных кодах. Поэтому Еве оказывается доступно большее количество информации, что приводит к меньшей допустимой критической ошибке, до которой возможно получение общего секретного ключа для Алимы м Боба.

Одной и важных задач является поиск эффективных процедур распределенной коррекции ошибок.

После исправления ошибок Алисой и Бобом у них возникают одинаковые битовые строки («очищенный» ключ). Однако информация Евы об «очищенном» клююче все еще является конечной, и заведомо не экспоненциально малой по параметру секретности. Для получения финального секретного ключа необходимо сжатие (хеширование) очищенного ключа при помощи универсальных функций хеширования второго рода [20] (Wegman, Carter), которые сами являются случайными величинами. Причем степень сжатия определяется как величиной ошибки в первичном ключе, так и используемой процедурой коррекции ошибок. Исследованию этих вопросов посвящена четвертая глава.

В пятой главе рассмотрена эффективность различных методов коррекции ошибок применительно к задачам квантовой криптографии, основанных на процедуре бисектив-ного поиска, комбинированном каскадном методе, а также на классических кодах Боуза-Чоудхури-Хоквингема и Хэмминга.

Наиболее простая итерационная процедура коррекции ошибок — это бисективный поиск ошибок, который сводится к разбиению первичного ключа на случайные непересекающиеся блоки и вычислению четностей этих блоков. Четности множеств сравниваются, как на приемном, так и на передающем конце через открытый канал. После раскрытия четности какого-либо множества, один из случайно выбранных битов, отбрасывается. При несовпадении четностей размер блока уменьшается вдвое, и процесс повторяется. Поскольку блоки не пересекаются, то выбрасывание битов не представляет труда. Такая процедура сохраняет конфиденциальность — подслушиватель не получает дополнительной информации при «чистке» первичного ключа. Однако, такая процедура крайне неэффективна, поскольку остается.

11 достаточно мало битов в «очищенном» ключе (например, при вероятности ошибки в 10% в первичном ключе в «очищенном» ключе остается не более 10% от исходной длины).

Наиболее эффективным, в смысле длины «очищенного» ключа, на сегодняшний день, по-видимому, является каскадный метод коррекции ошибок, впервые предложенный в [22]. В исходном варианте каскадного метода биты четности отдельных, и, в общем случае, пересекающихся подмножеств запоминаются и используются на следующих проходах. В процессе работы метода никакие биты не выбрасываются, поэтому метод не сохраняет конфиденциальность. Оценить информацию, которую получает подслушиватель, когда раскрываются биты четности набора пересекающихся множеств, возникающие на разных проходах, достаточно сложно. До сих пор, насколько нам известно, полный анализ не был выполнен.

Сохранить конфиденциальность и эффективность метода можно, если в конце «чистки» первичного ключа отбрасывать некоторое количество битов. Поскольку, возникающие на каждом проходе множества битов пересекаются, то процедура выбрасывания не является тривиальной.

В данной главе предложен простой регулярный способ сохранения конфиденциальности (отбрасывания раскрытых при «чистке» битов четности пересекающихся множеств).

В шестой главе на основе результатов, полученных в предыдущих главах, приводится описание разработанного программного комплекса и алгоритмов обработки ключей, используемых в экспериментальном образце оптоволоконной системы квантовой криптографии.

Защищаемые положения.

1. Построена явная атака на передаваемый при помощи квантовых состояний ключ для протокола В В 84, достигающая теоретического предела ошибки Qc «11%, до которой возможно распределение ключей;

2. Дана оценка длины секретного ключа, которую можно получить при наблюдаемой вероятности ошибки Q < Qc в первичных ключах, для двух основных квантовых протоколов распределения ключей ВВ84 и В92;

3. Предложен метод сохранения конфиденциальности для каскадного метода коррекции ошибок в первичных ключах;

4. Разработаны алгоритмы и комрьютерные программы для распределенной коррекции ошибок.

Научная новизна и практическая значимость.

В диссертационной работе впервые построена явная атака на ключ в квантовой криптографии (протокол ВВ84), на которой достигается теоретический предел по критической ошибке. Данная атака является наилучшей для подслушивателя в том смысле, что подслу-шиватель получает максимум информации о ключе, производя при этом минимально возможную ошибку на приемной стороне. Впервые также выяснено, что происходит в области ошибок 11% < Qc < 15%. Показано, что существует бесконечный набор атак подслушивателя, которые приводят к ошибкам в данном диапазоне. Атаки отличаются друг от друга только на стадии измерений, которые производит подслушиватель. Выяснена связь получаемой подслушивателем информации о ключе при таких измерениях с набором классических пропускных способностей квантового канала связи. Показано, что для достижения теоретического предела по ошибке подслушивателю необходима квантовая память.

Получены оценки длины ключа для двух основных квантовых протоколов распределения ключей В92 и ВВ84.

Проведено сравнение эффективности различных методов распределенной коррекции ошибок в первичных ключах в квантовой криптографии. Показано, что наиболее эффективным методом является каскадный метод. Предложен метод исключения контрольных битов четности перекрывающихся множеств, которые возникают при коррекции ошибок. Это позволяет устранить информацию выдаваемую подслушивателю легитимными пользователями через открытый канал при коррекции ошибок. Использование данной процедуры позволяет гарантировать, что информация о ключе, которую имел подслушиватель до коррекции ошибок, не увеличится после их исправлении легитимными пользователя.

На основе теоретических исследований разработаны алгоритмы и компьтерные программы, которые использованы при разработке экспериментального образца оптоволоконной системы квантовой криптографии.

Апробация работы и публикации.

Результаты работы докладывались и обсуждались на следующих конференциях:

1. Международная конференция «Quantum Informatics — QI-2007», Москва, Россия, 2007 г.;

2. 10 Научно-техническая конференция по криптографии, посвященная 85-летию образования Криптографической Службы России, Москва 2006 г., Академия Криптографии Российской Федерации, Секция 13.

3. Международная конференция «Quantum Informatics — QI-2005», Москва, Россия, 2005 г.;

Основные результаты диссертации опубликованы в работах:

1) С. Н. Молотков, А. В. Тимофеев, Явная атака на ключ в квантовой криптографии (протокол ВВ84), достигающая теоретического предела ошибки Qc рз 11%, Письма в Журнал экспериментальной и теоретичесой физики, т.85, вып.10, 634 (2007).

2) А. В. Тимофеев, С. Н. Молотков, О каскадном методе коррекции ошибок в первичных ключах в квантовой криптографии, сохраняющем конфиденциальность, Письма в Журнал экспериментальной и теоретичесой физики, т.82, вып.12, 868 (2005).

3) А. В. Тимофеев, Д. И. Помозов, А. П. Маккавеев, С. Н. Молотков, О структуре открытого классического канала связи в квантовой криптографии: коррекция ошибок, целостность и аутентичность, Журнал экспериментальной и теоретической физики, т. 131, вып.5, 771 (2007).

4) А. П. Маккавеев, С. Н. Молотков, Д. И. Помозов, А. В. Тимофеев, О практических методах «чистки» ключей в квантовой криптографии, Журнал экспериментальной и теоретической физики, т. 128, вып.2, 263 (2005).

1. S. Wiesner, Conjugate coding, S1. ACT News, 15, 78 (1983).

2. C.H.Bennett, G. Brassard, Quantum Cryptography: Public Key Distribution and Coin Tossing, Proc. of IEEE Int. Conf. on Comput. Sys. and Sign. Proces., Bangalore, India, December 1984, p.175.

3. G.S.Vernam, Cipher printing telegraph systems for secret wire and radio telegraphic communications, J. Amer. Inst. Elect. Eng., 55, 109 (1926).

4. C.E.Shannon, Communication theory of secrecy systems, Bell Syst. Tech. Jour., 28, 658 (1949).

5. W.K.Wootters, W.H.Zurek, A single quantum cannot be cloned Nature, 299, 802 (1982).

6. C.H.Bennett, Quantum Cryptography Using Any Two Nonorthogonal States, Phys. Rev. Lett., 68, 3121 (1992);

7. W. Diffi, M.E.Hellman, New directions in cryptography, IEEE Trans, on Information Theory, IT-22, 644 (1976).

8. A.K.Ekert, B. Huttner, G.M.Palma, A. Peres, Eavesdropping on Quantum-Cryptographical Systems, Phys. Rev., A50, 1047 (1994).

9. H.E.Brandt, J.M.Meyers, S.J.Lomonaco Jr., Aspects of Entangled Translucent Eavesdropping in Quantum Cryptography, Phys. Rev., A56,4456 (1997).

10. C.E.Shannon, Mathematical Theory of Communication, Bell Syst. Tech. Jour., 27, 397- 27, 623 (1948).

11. Р. Галлагер, Теория информации и надежная связь, Москва, Советское радио (1974).

12. C.W.Helstrom, Quantum Detection and Estimation Theory, Academic Press, New York, San Francisco, London, (1976).

13. J. Wolfowitz, The Coding Messages Subjected to Chance Errors, Illinois J. of Math., 1, 591 (1957).124.

14. А. С. Холево, Введение в квантовую теорию информации, серия Современная математическая физика, вып. 5, МЦНМО, Москва, 2002;

15. R. Jozsa, B. Schumacher, A new proof of the quantum noiseless coding theorem, J. Mod. Optics. 41, 2343 (1994).

16. P. Hausladen, R. Jozsa, B. Schumacher, M. Westmoreland, W.K.Wootters, Classical information capacity of a quantum channel, Phys. Rev. A54, 1869 (1996).

17. B. Schumacher, M.D.Westmoreland, Sending classical information via noisy quantum channels, Phys. Rev. A 56, 131 (1997).

18. D. Maurer, Practical error-correction procedures in quantum cryptography, IEEE Trans. Inf. Theory, 39, 733 (1993).

19. C.H.Bennett, G. Brassard, C. Crepeau, U. Maurer, Generalized privacy amplification, IEEE Transaction on Information Theory, 41, 1915 (1995).

20. J.L.Carter, M.N.Wegman, Universal classes of hash functions, Journal of Computer and System Sciences, 18, 143 (1979).

21. C.H.Bennett, F. Bessette, G. Brassard, L. Salvail, J. Smolin, Experimental quantum, cryptography, Journal of Cryptology, 5, 3 (1992).

22. G. Brassard, L. Salvail, Secret Key Reconcilation by Public Discussion, Lecture Notes in Computer Science, 765, 410 (1994).

23. E.J.Mac Williams, N.J.A.Sloane, The Theory of Error-Correcting Codes, North-Holland Publ. Company, (Amsterdam, New York, Oxord), 1977.

24. W.W.Peterson, E.J.Weldon, Error-Correcting Codes, The MIT Press, Cambridge, Massachusetts, London, England, (1972).

25. B. Julsgaard, J. Sherson, J.I.Cirac, J. Flurasek, E.S.Polzik, Experimental demonstration of quantum memory for light, Nature, 432, 482 (2004).

26. D. Mayers, Unconditional security in Quantum Cryptography, arXiv: quant-ph/9 802 025.

27. E. Biham, M. Boyer, P.O.Boykin, T. Mor, V. Roychowdhury, A Proof of the Security of Quantum Key Distribution, arXiv: quant-ph/9 912 053.125.

28. P.W.Shor, J. Preskill, Simple Proof of Security of the BB84 Quantum Key Distribution Protocol, arXiv: quant-ph/3 004.

29. I.Csiszar. J. Korner, Broadcast channels with confidential messages, IEEE Trns. Inf. Theory, 24, 339 (1978).

30. C.A.Fuchs, N. Gisin, R. Griffiths, Chi-Sheng Niu, A. Peres, Optimal Eavesdropping in Quantum Cryptography, Phys. Rev., A56 1163 (1997).

31. C.E.Shannon, Mathematical Theory of Communication, Bell Syst. Tech. Jour., 27, 397- 27, 623 (1948).

32. А. С. Холево, Проблемы передачи информации. 8, 63 (1972) — 15, 3 (1979) — Успехи математических наук. 53, 193 (1998);

33. А. В. Тимофеев, С. Н. Молотков, О каскадном методе коррекции ошибок в первичных ключах в квантовой криптографии, сохраняющем конфиденциальность, Письма в ЖЭТФ, 82 868 (2005).

34. R. Griffiths, Chi-Sheng Niu, Optimal eavesdropping in quantum cryptography. II. A quantum circuit, Phys. Rev., A56 1173 (1997).

35. P. Shor, Capacities of Quantum Channels and How to Find Them, arXiv: quant-ph/304 102.

36. Gilles Brassard, Louis Salvail, Secret-Key Reconciliation by Public Discussion, EUROCRYPT 1993: 410−423.

37. W. T. Buttler, S. K. Lamoreaux, J. R. Torgerson, G. H. Nickel, Fast, Efficient Error Reconciliation for Quantum Cryptography, arXiv: quant-ph/203 096.

38. Chip Elliott, Alexander Colvin, David Pearson, Oleksiy Pikalo, John Schlafer, Henry Yeh, Current status of the DARPA Quantum Network, arXiv: quant-ph/503 058.

39. Дональд Кнут. Искусство программирования, т. 1, «Вильяме», Москва, 2000.

40. C. Cachin, Dissertation of Swiss Federal Institute of Technology of Ziirich, Entropy Measures and Unconditional Security in Cryptography, Diss. ETH No.12 187 (1997).

41. Т. Кормен, Ч. Лейзерсон, Р. Ривест, Алгоритмы: построение и анализ, МЦНМО, Москва, 2004.