> Интересно, кто-нибудь подходил к решению этой проблемы > достаточно близко. Существуют несколько известных
Довольно близко - Шор (алгоритм Шора). Алгоритм, как предполагают, позволит факторизовать числа оч быстро, но только на квантовом компе. А таких пока нет, по крайней мере, способных выполнить соотв. прогу.
> решить. Или нельзя. Ни где не видел доказательств, только > фраза: "задача NP-полноты".
Если это задача NP-полноты (точно не знаю), то:
Доказательств не существует - ни доказательств, ни опровержений, если эта задача NP-полная. Т.е. неизвестно, можно ли решить NP-полную задачу за полиномиальное время. Однако, поскольку есть оч много таких задач (задача о коммивояжере, о максимальном полном подграфе, и т.д.), и если хотя бы одна из них решается за полиномиальное время, то решаются все, а решений не найдено ни для одной, то сейчас NP-полная задача - практически то же, что не разрешимая за полином. время задача.
А за большее - экспоненциальное - пожалуйста, прямым перебором.
Это все относится к задачам NP-полноты, но я, в свою очередь, хочу задать совсем ламерский вопрос: в чем состоит крякинг RC5? Что считают, например, клиеты distributed.net? Это конкретный зашифрованный пароль, или что-то вроде словаря, или что?
Много народу в сети RC5 ломает перебором (на сколько я понимаю хоть и не в лоб, но перебором). Можно конечно и крепостную стену лбом пробить, если 2^N людей будут в нее долбиться в течение 2^M лет.
Насколько я понимаю все методы шифрования с открытым ключем основаны на отсутствии быстрого алгоритма разложения числа на множители. Точнее нужно для числа найти его два сомножителя, поскольку заведомо известно, что для его получения брались два больших простых числа, стало быть других делителей оно не имеет.
Интересно, кто-нибудь подходил к решению этой проблемы достаточно близко. Существуют несколько известных алгоритмов, которые значительно сокращают время поиска сомножителей перебором, но можно же задачу и без перебора решить. Или нельзя. Ни где не видел доказательств, только фраза: "задача NP-полноты".
про NP12.05.02 21:26 Автор: Dude Статус: Незарегистрированный пользователь
> Интересно, кто-нибудь подходил к решению этой проблемы > достаточно близко. Существуют несколько известных
Довольно близко - Шор (алгоритм Шора). Алгоритм, как предполагают, позволит факторизовать числа оч быстро, но только на квантовом компе. А таких пока нет, по крайней мере, способных выполнить соотв. прогу.
> решить. Или нельзя. Ни где не видел доказательств, только > фраза: "задача NP-полноты".
Если это задача NP-полноты (точно не знаю), то:
Доказательств не существует - ни доказательств, ни опровержений, если эта задача NP-полная. Т.е. неизвестно, можно ли решить NP-полную задачу за полиномиальное время. Однако, поскольку есть оч много таких задач (задача о коммивояжере, о максимальном полном подграфе, и т.д.), и если хотя бы одна из них решается за полиномиальное время, то решаются все, а решений не найдено ни для одной, то сейчас NP-полная задача - практически то же, что не разрешимая за полином. время задача.
А за большее - экспоненциальное - пожалуйста, прямым перебором.
Это все относится к задачам NP-полноты, но я, в свою очередь, хочу задать совсем ламерский вопрос: в чем состоит крякинг RC5? Что считают, например, клиеты distributed.net? Это конкретный зашифрованный пароль, или что-то вроде словаря, или что?
про алгоритм Шора13.05.02 21:14 Автор: leo <Леонид Юрьев> Статус: Elderman Отредактировано 13.05.02 21:15 Количество правок: 1
> Довольно близко - Шор (алгоритм Шора). Алгоритм, как > предполагают, позволит факторизовать числа оч быстро, но > только на квантовом компе. А таких пока нет, по крайней > мере, способных выполнить соотв. прогу. IBM в конце прошлого года реализовала выполнение subj на квантовом уровне. Конечно в игрушечном масштабе, но все же...
http://researchweb.watson.ibm.com/resources/news/20011219_quantum.shtml
> Это все относится к задачам NP-полноты, но я, в свою > очередь, хочу задать совсем ламерский вопрос: в чем состоит > крякинг RC5? Что считают, например, клиеты distributed.net? > Это конкретный зашифрованный пароль, или что-то вроде > словаря, или что? полным перебором ищется 64-битный ключ (пароль).
на множители. Точнее нужно для числа найти его два
> сомножителя, поскольку заведомо известно, что для его > получения брались два больших простых числа, стало быть > других делителей оно не имеет. > Интересно, кто-нибудь подходил к решению этой проблемы > достаточно близко. Существуют несколько известных > алгоритмов, которые значительно сокращают время поиска > сомножителей перебором, но можно же задачу и без перебора > решить. Или нельзя. Ни где не видел доказательств, только > фраза: "задача NP-полноты". Брат, стукни в асю - 144221400. я обрыл всю библиотеку, по инет лазил немерянно - ссылки на быструю факторизацию числа, если только 2-а простых сомножителя есть, вот кроме упоминаний - ничего.
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
