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

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