Предлагаю сегодня поговорить о факторизации — не самом интуитивно понятном, но очень важном инструменте "большой" математики. Эта статья не из простых, хотя ничего сложного в ней нет. Дело в том, что в ней мы рассмотрим, как математика формализует один из основных инструментов мышления — абстракцию. А абстракции могут стать чем-то внятным только после знакомства с большим числом конкретных примеров. И вот, в качестве первого примера, мы возьмём листок бумаги и посадим на него кляксу. Пятно может быть какой угодно формы и даже состоять из нескольких частей...

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