Ясно, что числа из огромного диапазона — безусловно содержащего любые числа, которые когда-либо были измерены как численные значе­ния физических переменных — можно перемножить за крошечную долю секунды. Таким образом, умножение действительно легко поддается обработке для любых целей в пределах физики (или, по крайней мере, в пределах существующей физики). Вероятно, за пределами физики мо­гут появиться практические причины умножения гораздо больших чи­сел. Например, для шифровальщиков огромный интерес представляют произведения простых чисел, состоящих примерно из 125 цифр. Наша гипотетическая машина могла бы умножить два таких простых числа, получив произведение, состоящее из 250 цифр, примерно за одну сотую секунды. За одну секунду она могла бы перемножить два тысячезначных числа, а современные компьютеры легко могут осуществить более точный расчет этого времени. Только некоторые исследователи эзоте­рических областей чистой математики заинтересованы в выполнении таких непостижимо огромных умножений, однако, мы видим, что даже у них нет причины считать умножение трудно обрабатываемым.

Напротив, разложение на множители, по сути процесс, обрат­ный умножению, кажется гораздо сложнее. В начале вводится одно число, скажем, 10949769651859, задача заключается в том, чтобы найти два множителя, меньших числа, произведение которых равно 10949769651859. Поскольку мы только что умножили эти числа, мы знаем, что в этом случае ответ будет 4220851 и 2594209 (и поскольку оба эти числа простые, это единственно правильный ответ). Но не об­ладая таким внутренним знанием, как мы нашли бы эти множители? В поисках простого метода вы обратитесь к детским воспоминаниям, но впустую, поскольку такого метода не существует.

Самый очевидный метод разложения на множители — делить вво­димое число на все возможные множители, начиная с 2 и продолжая каждым нечетным числом, до тех пор, пока введенное число не разде­лится без остатка. По крайней мере, один из множителей (принимая, что введенное число не является простым) не может быть больше квад­ратного корня введенного числа, что позволяет оценить, сколько вре­мени может занять этот метод. В рассматриваемом нами случае наш компьютер найдет меньший из двух множителей, 2 594 209, примерно за одну секунду. Однако, если вводимое число будет в десять раз больше, а его квадратный корень примерно в три раза больше, то разложение его на множители по этому методу займет в три раза больше времени. Другими словами, увеличение вводимого числа на один разряд уже ут­роит время обработки. Увеличение его еще на один разряд снова утроит это время и т. д. Таким образом, время обработки будет увеличивать­ся в геометрической прогрессии, т.е. экспоненциально, с увеличением количества разрядов в раскладываемом на множители числе. Разложе­ние на множители числа с 25-значными множителями по этому методу заняло бы все компьютеры на Земле на несколько веков.