Зная
r
, можно эффективно найти делители числа
N
. Учитывая, что
порядок
r
фактически является периодом функции
a
x
mod
N
,
r
мож-
но определить с помощью алгоритма нахождения периода функции.
Число
a
можно взять случайным — если период функции окажется не-
четным, то надо просто выбрать другое
a
и снова прогнать алгоритм.
Квантоваякриптография.
Обычные протоколы открытого рас-
пространения ключей, например протокол Диффи–Хеллмана, основа-
ны на предположении о том, что используемая в них функция (напри-
мер, возведение в степень по простому модулю) является однонапра-
вленной. Однако на настоящий момент неизвестно действительно ли
это так. Более того, многие из них не являются однонаправленными
для квантового компьютера.
С помощью квантово-механических методов можно реализовать
такое устройство для распределения ключей, что злоумышленник фи-
зически не сможет перехватить информацию. Более того, уже есть
реальные устройства, обеспечивающие квантовую передачу ключей.
Итак, пусть у нас есть канал связи, по которому можно передавать
квантовые биты. Два пользователя,
A
и
B
, хотят договориться об об-
щем ключе для шифрования информации, передаваемой по открытому
каналу.
Пользователь
A
может кодировать информацию в различных ба-
зисах. Определим два базиса: в первом 0 кодируется в
|
0
, а 1 коди-
руется в
|
1
, во втором базисе 0 кодируется в
1
√
2
(
|
0
− |
1 )
, а 1 — в
1
√
2
(
|
0 +
|
1 )
.
Протокол квантового распространения ключей заключается в сле-
дующем.
1.
A
случайно выбирает битовую строку.
2.
A
случайно выбирает последовательность базисов длиной, рав-
ной длине битовой строки.
3.
A
кодирует битовую строку, используя соответствующие базисы,
и передает закодированную битовую строку
B
.
4.
B
принимает квантовые биты от
A
и измеряет их, случайно
выбирая базисы для измерения.
5.
B
сообщает
A
по открытому каналу свои базисы измерений.
6.
A
определяет, какие базисы, использованные
B
, совпадают с его
собственными, и сообщает
B
по открытому каналу, какие биты он
принял правильно.
7.
B
посылает пользователю
A
некоторые, выбранные наугад, биты
по открытому каналу.
44 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2006. № 2
