Простые числа

← →
~ (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 взламает такой шифр с полпинка.
Однако, если появится алгоритм быстрой проверки простого числа, это будет революцией во всех областях программирования, а не только в криптографии. Одни только задачи линейного программирования да теория игр чего стоят!

Простые числа Найти похожие ветки