О том, как я «ломал» RSA

Решал я как-то очередную задачу:

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго – шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.

Дано число n (1 ≤ n ≤ 10^5). Найдите такой его делитель (само число n и единица считаются делителями числа n), который лучше любого другого делителя числа n.

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

Я все сделал, и решение прошло.

Далее была вторая задача:

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго — шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.

Дано число n (1 ≤ n ≤ 10^5000). Найдите такой его делитель d (само число n и единица считаются делителями числа n), что любой другой делитель c числа n лучше, чем d.

По сути, такая же задача, что и предыдущая – просто нужно в паре мест поменять «больше» на «меньше» и наоборот. Я поменял, и на небольших тестах решение прошло.

Но тут я замечаю, что в это задаче верхнее ограничение на n какое-то очень большое. Я заменяют тип «int» на класс «длинной» арифметики (5000 тысяч знаков – пустяк, было и более) и пробую: на малых тестах работает, значит, алгоритм верный.

Посылаю решение, и конечно, получаю ответ «Time limit exceeded». После небольшого раздумья становится ясно, что слишком много надо считать, и подход в целом неправильный.

Пишу письмо Leonid’у с просьбой прояснить ситуацию.

Приходит ответ типа, что моя попытка, ища все делители громадного числа, взломать RSA брутборсом конечно похвальная, но исполнена жиденько, да и врядли она вообще под силу современным компьютерам. К тому я же ищу все делители, а не только простые, а их будет еще больше.

В итоге выяснилось, что данная задача решается не только без «длинной» арифметики, но даже и без короткой, одним циклом в пару строк. Просто надо понять, что за тип чисел просят найти.