Доброго времени суток, товарищи! Сегодня мы коснемся такой темы, как факторизация числа - разложение числа на простые множители. Существование и единственность такого разложения следует из основной теоремы арифметики. Сегодня мы поверхностно пройдемся по теме, разберем простейшим алгоритм, достаточный для олимпиад, а в следующих статьях углубимся в тему и посмотрим алгоритмы Полларда, Бента, Монте-Карло и Ферма. Как мы знаем из предыдущих статей - делители числа будут только лишь до корня из этого числа (делители ходят парами)...

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