Предыдущая Следующая
Тот факт, что репертуар универсального
квантового компьютера содержит среды, передача которых является
труднообрабатываемой для классического вычисления, говорит о том, что новые
классы чисто математических вычислений тоже должны стать легкообрабатываемыми
на этом компьютере. Как сказал Галилео, законы физики выражаются на языке
математики, а передача среды эквивалентна оценке определенных математических
функций. Действительно, в настоящее время обнаружено множество математических
задач, которые можно было бы эффективно решить с помощью квантового вычисления,
так как для всех известных классических методов они являются труднообрабатываемыми.
Наиболее эффектной из этих задач является задача разложения на множители
больших чисел. В
1994 году Питер Шор, работающий в Bell Laboratories, открыл метод, известный как алгоритм Шора. (Пока эта книга
корректировалась, были открыты другие эффектные квантовые алгоритмы, включая алгоритм Гровера для очень быстрого поиска
длинных списков).
Алгоритм Шора чрезвычайно прост и
довольствуется гораздо более скромным аппаратным обеспечением, чем то, которое
понадобилось бы для универсального квантового компьютера. А потому вероятно,
что квантовое устройство для разложения на
множители будет построено задолго до того, как весь диапазон
квантовых вычислений станет технологически осуществимым. Эта перспектива имеет
грандиозное значение для криптографии
(науки, которая занимается секретной передачей информации и установлением ее
подлинности). Реальные сети связи могут быть глобальными и иметь огромные,
постоянно изменяющиеся наборы участников с непредсказуемыми схемами связи.
Непрактично требовать, чтобы каждая пара участников заранее физически обменивалась
секретными шифровальными ключами, которые позволили бы им позднее общаться, не
боясь, что их подслушают. Криптография с
открытым ключом — это любой метод отправки секретной
информации, при котором ни отправитель, ни получатель не делятся секретной
информацией. Самый надежный из известных методов криптографии с открытым ключом
основан на трудности обработки задачи разложения на множители больших чисел.
Этот метод известен как криптосистема RSA, которая получила свое название в честь Рональда Ривеста (Rivest), Ади Шамира (Shamir) и Леонарда Адельмана
(Adelman), которые
впервые предложили ее в 1978 году.
Этот метод обусловлен математической процедурой, посредством которой сообщение
можно закодировать, используя в качестве ключа огромное (скажем, 250-значное)
число. Получатель может свободно обнародовать этот ключ, потому что любое
сообщение, зашифрованное с его помощью, можно расшифровать, только зная
множители этого числа. Таким образом, я могу выбрать два 125-значных простых
числа и хранить их в секрете, но перемножив, сообщить всем их 250-значное
произведение. Кто угодно может послать мне сообщение, использовав это число как
код, но только я смогу прочитать эти сообщения, потому что только мне известны
секретные множители. Предыдущая Следующая
|