Раз безопасность в интернете зависит от наличия достаточного количества больших простых чисел, как же веб-сайтам удается быстро находить их для эффективного предоставления финансовых услуг? Для этого используются алгоритмы, которые по меньшей мере дают веб-сайту высокую вероятность того, что найденные ими числа простые, хотя и не гарантируют этого.
Вспомним, что если некое число не простое и не псевдопростое, то половина чисел, меньших его, не пройдут тест Ферма. Но что, если нам так сильно не повезет, что мы проверим именно те числа, которые пройдут этот тест? Казалось бы, чтобы найти свидетеля составного характера числа, необходимо проверить половину меньших его чисел. Но какова вероятность не попасть на такого свидетеля? Предположим, мы проверили 100 чисел и не нашли ни одного свидетеля. Это означает одно из двух: либо наше число простое или псевдопростое, либо нам действительно не попалось ни одного свидетеля, но вероятность такого события составляет 1 к 2100. Играть на таких условиях я согласен! – уж слишком мала эта вероятность.
Хотя у нас есть превосходные алгоритмы, как детерминированные, так и вероятностные, позволяющие находить простые числа для создания таких кодов, обычных алгоритмов для взлома этих кодов, по-видимому, не существует. А как насчет чего-нибудь не столь обычного?
Квантовые шорткаты
Квантовые шорткаты
Одна из проблем, с которыми сталкиваются обычные компьютеры, когда пытаются решить задачу, подобную нахождению простых чисел для деления большого кодового числа, состоит в том, что им приходится проводить одну проверку, прежде чем они могут перейти к следующей. (Уточню для ясности, что в последующих рассуждениях я имею в виду только точное деление, без остатка.) Хорошо бы было разделить компьютер на части так, чтобы все они одновременно проводили разные проверки. Параллельная обработка – очень действенный способ ускорения работы. Взять, к примеру, строительство дома. В состязании на скорость строительства дома, проводившемся в Лос-Анджелесе, победила бригада из 200 строителей, работавших параллельно: они закончили свой дом за четыре часа. Разумеется, некоторые задачи необходимо выполнять последовательно. При строительстве многоэтажного дома или подземного гаража следующий этаж можно добавить, только когда будет построен предыдущий. Но перебор меньших чисел с проверкой того, делится ли на них большее, прекрасно можно производить параллельно. Каждая из таких проверок никак не зависит от результатов всех остальных.
Недостаток параллельной обработки данных состоит в том, что и она ограничивается физическими возможностями. Если разбить задачу на две, время, которое занимают проверки, уменьшится в два раза, но зато увеличится вдвое количество необходимой аппаратуры. По сути дела, такой подход не помогает находить простые делители большого числа.