Форум: "Потрепаться";
Текущий архив: 2002.12.30;
Скачать: [xml.tar.bz2];
ВнизПростые числа Найти похожие ветки
← →
~ (2002-12-09 12:59) [0]В журнале "Ломоносов" (New Scientist) в декабрьском номере статья дюже интересная о том, как индийские математики предложили простой алгоритм определения со 100% точностью, простое число или нет. Алгоритм расписан очень точно и занимает 13 строк. Отдав журнал на прочтение сыну, забыл переписать код алгоритма, и теперь доберусь до него не скоро. :(
Нет ли доброго человека, перенесшего этот код на Delphi (или Pascal) и готового выложить его прямо здесь?
← →
McSimm (2002-12-09 13:18) [1]Что-то тут не так...
← →
McSimm (2002-12-09 13:22) [2]Скорее всего речь идет об алгоритме генерации простого числа, а не проверки числа на простое.
← →
zavdim (2002-12-09 13:26) [3]Точно - генерации.
Только по-моему алгоритм секретный - они с ним пока только выпендриваются. Это для шифрования им нужно.
← →
McSimm (2002-12-09 13:26) [4]Похоже я не прав. Это что же, грядет революция в криптографии?
Или это очередная дутая сенсация?
http://mignews.com.ua/science/world/mathe_0812.html
← →
McSimm (2002-12-09 13:33) [5]А вот и сам алгоритм.
http://www.cse.iitk.ac.in/primality.pdf
Пока не разбирался
← →
DAC (2002-12-09 14:08) [6]
> McSimm ©
В августе про эту работу Маниндры было давольно много шума. Правда пошумели-пошумели и притихли.
Да, если алгоритм верный (я пока с ним тоже полностью не разобрался), теоретическую ценность этой работы переоценить тяжело. Получается, что классы N и NPC совпадают.
Однако на практике выжать из этого алгоритма что-нибудь серьезное не получиться. Хотя алгоритм и полиномиальный, но оценка сложности очень бальшая - O(log^12 n), если n - число. Т.е. O(n^12), если n - длина числа.
Так что революция в криптографии отодвигается. :-(((
← →
McSimm (2002-12-09 14:19) [7]То, что революция откладывается - меня только радует.
Кстати, поправьте меня, если я ошибаюсь: Если появится алгоритм быстрой проверки простого числа, то расшифровка PGP становится простой задачей ?
← →
DAC (2002-12-09 15:21) [8]
> McSimm © (09.12.02 14:19)
На 100% сказать не могу. Но похоже на правду. В PGP используются алгоритмы кодирования с открытым ключом. Но какие точно - я не разбирался. Если это алгоритмы типа RSA, то это действительно будет очень простым делом. Скажу даже больше, любой грамотный человек после поверхностного ознакомления с RSA взламает такой шифр с полпинка.
Однако, если появится алгоритм быстрой проверки простого числа, это будет революцией во всех областях программирования, а не только в криптографии. Одни только задачи линейного программирования да теория игр чего стоят!
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2002.12.30;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.009 c