> Интересно, кто-нибудь подходил к решению этой проблемы > достаточно близко. Существуют несколько известных
Довольно близко - Шор (алгоритм Шора). Алгоритм, как предполагают, позволит факторизовать числа оч быстро, но только на квантовом компе. А таких пока нет, по крайней мере, способных выполнить соотв. прогу.
> решить. Или нельзя. Ни где не видел доказательств, только > фраза: "задача NP-полноты".
Если это задача NP-полноты (точно не знаю), то:
Доказательств не существует - ни доказательств, ни опровержений, если эта задача NP-полная. Т.е. неизвестно, можно ли решить NP-полную задачу за полиномиальное время. Однако, поскольку есть оч много таких задач (задача о коммивояжере, о максимальном полном подграфе, и т.д.), и если хотя бы одна из них решается за полиномиальное время, то решаются все, а решений не найдено ни для одной, то сейчас NP-полная задача - практически то же, что не разрешимая за полином. время задача.
А за большее - экспоненциальное - пожалуйста, прямым перебором.
Это все относится к задачам NP-полноты, но я, в свою очередь, хочу задать совсем ламерский вопрос: в чем состоит крякинг RC5? Что считают, например, клиеты distributed.net? Это конкретный зашифрованный пароль, или что-то вроде словаря, или что?
|