§ 3.3. Эффективность алгоритма деления методом проб

Описанный в предыдущем параграфе алгоритм легко понять и запрограммировать, однако он оказывается чрезвычайно неэффективным. Поскольку для поиска разложения мы многократно используем алгоритм деления методом проб, следует оценить эффективность последнего. Проиллюстрируем это на простом, но очень выразительном примере.

При применении алгоритма деления методом проб к натуральному числу худшим случаем оказывается тот, когда простое. В этом случае алгоритм выполняет до остановки циклов. Для упрощения вычислений предположим, что простое и в нем не меньше ста цифр. Сколько времени потребуется для подтверждения простоты числа с помощью алгоритма деления методом проб?

Мы предполагаем, что т.е. Значит мы должны повторить цикл по меньшей мере раз. Чтобы прикинуть, сколько это займет времени, допустим, что наш компьютер выполняет делений в секунду. Здесь мы предполагаем, что никаких других операций, кроме операции деления, в цикле нет. Безусловно, это далеко не так, однако сделаем такое допущение. Разделив первое число на второе, мы заключаем, что компьютеру потребуется секунд на проверку простоты числа Простой подсчет показывает, что на это уйдет приблизительно лет. По современным

стандартам это чересчур большой срок. Чтобы представить его себе, вспомним, что согласно наиболее распространенной точке зрения, Большой Взрыв произошел около лет назад. Дополнительных комментариев не требуется: числа говорят сами за себя.

Означает ли это, что алгоритм деления методом проб бесполезен? Разумеется, нет. Допустим, что у раскладываемого числа есть маленький простой множитель, скажем, меньший, чем 106. Тогда алгоритм деления методом проб быстро его отыщет. С другой стороны, если у нас есть основания полагать, что тестируемое число простое, то алгоритм деления методом проб не выглядит наилучшим решением.

Есть много других алгоритмов разложения целых чисел, эффективность которых зависит от типа введенного числа. Так, алгоритм из § 3.2 очень хорош для чисел с маленькими простыми делителями. В следующем параграфе мы изучим алгоритм Ферма, который наиболее эффективен для таких чисел у которых есть делитель (не обязательно простой), не сильно превышающий

Следует помнить, что эффективный алгоритм разложения на множители случайно выбранного натурального числа неизвестен. Неясно только, действительно ли он не существует или у человечества пока не хватило ума до него додуматься.