Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 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.57 MB
Время: 0.036 c
1-99131
mikl2002
2002-12-18 12:24
2002.12.30
Как осуществить XLS преобразование в XMLDocument e


1-99186
Pat
2002-12-19 00:19
2002.12.30
InstallShield Express for Delphi5


3-98965
Goobit
2002-12-09 13:19
2002.12.30
Лог изменений в TClientDataSet


1-99142
Berg
2002-12-18 14:30
2002.12.30
Глупый вопрос, наверно......


3-99019
Emfi
2002-12-09 19:10
2002.12.30
Блокировка таблиц в MS SQL.





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский