Тот факт, что репертуар универсального квантового компьюте­ра содержит среды, передача которых является труднообрабатываемой для классического вычисления, говорит о том, что новые классы чис­то математических вычислений тоже должны стать легкообрабатыва­емыми на этом компьютере. Как сказал Галилео, законы физики выра­жаются на языке математики, а передача среды эквивалентна оценке определенных математических функций. Действительно, в настоящее время обнаружено множество математических задач, которые можно было бы эффективно решить с помощью квантового вычисления, так как для всех известных классических методов они являются трудно­обрабатываемыми. Наиболее эффектной из этих задач является задача разложения на множители больших чисел. В 1994 году Питер Шор, ра­ботающий в Bell Laboratories, открыл метод, известный как алгоритм Шора. (Пока эта книга корректировалась, были открыты другие эф­фектные квантовые алгоритмы, включая алгоритм Гровера для очень быстрого поиска длинных списков).

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