*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

понедельник, 19 июля 2010 г.

О том, как я «ломал» 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 брутборсом конечно похвальная, но исполнена жиденько, да и врядли она вообще под силу современным компьютерам. К тому я же ищу все делители, а не только простые, а их будет еще больше.

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

5 комментариев:

  1. Мде.. Как же жизнь связана. Подписан на твой блог, а даже и не знал что у нас общий знакомый :))

    ОтветитьУдалить
  2. Максимальная степень 10, на которую делится число. Сумма цифр минимальна - 1, но среди делителей с такой суммой оно максимально, а значит, является наихудшим числом.

    ОтветитьУдалить
  3. А разве 100, 1000 и т.д. не могут быть делителями?

    ОтветитьУдалить
  4. Александр, я об этом и говорю. Для входа задачи n ответом будет максимальная степень 10, на которую делится n (если n делится на 10^0, 10^1, ..., 10^k, но на 10^{k+1} уже не делится, то ответ 10^k).
    Таким образом, достаточно посчитать количество нулей в конце десятичной записи n, допустим их будет k, и выдать как ответ единицу с k нулями после неё.

    ОтветитьУдалить