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

Факторизация, то есть разложение числа на простые факторы, произведение которых дает данное число, является основой для взлома криптографических систем. Криптография использует тот факт, что факторизация является чрезвычайно трудоемким занятием. И чем больше число, с которым мы имеем дело, тем больше времени требуется для его факторизации. Следовательно, мы знаем, что чем длиннее данный пароль, тем сложнее его взломать. Поэтому, например, 128-битный шифр будет сложнее взломать, чем 64-битный. Современные вычислительные технологии не позволяют взламывать очень длинные шифры...