Простые числа за полиномиальное время

denissign

Слух прошел, что трое ебучих студентов индусов готовя дипломы придумали полиномиальный алгоритм проверки числа на простоту, америкосы из Bell Labs уже подтвердили правильность решения.
Имхо индусов пора в ось зла включать, мало того что эти суки устраивают демпинг во всей IT индустрии, так они скоро камня на камне в теории чисел не оставят

vovkak

Можешь ссылку дать?

ppp1638602mtu

>Можешь ссылку дать?
на слух?
На самом деле, индусы - как 800 миллионов обезьян с
пишущими машинками...

Xephon

Скоро год этой новости. В сентябре 2002 был доклад на мехмате по опубликованной статье.
Алгоритм хоть и полиномиален (кажется, 6-ая или 12-ая степень но с большими константами.
Насколько мне известно, это не студенты, а трое из самой сильной группы теоретиков числовиков в Индии (так по крайней мере говорил знакомый профессор-алгебраист из той самой страны)
P.S. на newsru писали, что гипотезу Пуанкаре доказали - вот это дело!

denissign

Я не искал в инете инфу по этому поводу, потому и спросил - может кто-то уже знает все про эту байку.

Xephon

Про это дело больше изестно 'у (его шеф - Нестеренко). Серега вроде бы как раз собирался заниматься реализацией этого алгоритма. Но при этом, говорит, нужно все существенно улучшить в описании и в константах.

denissign

То есть это все же правда ?
Ведь полиномиальное решение искали уже очень давно, и некоторые считали что его вообще нет.
Если продолжив тему эти ребята разложат число на множители за полиномиальное время - это будет самая большая подстава за время существования криптографии. Что банки будут делать вместе с интернет-торговлей ?

denissign

Реализация алгоритма занимает 13 строк кода, серьезное занятие конечно - не вопрос

vladlen62

хуйня это все... В журнале Ломоносов писали в начале семестра... И алгоритм давали... Мы с пропом даже реализовать его попробовали... Базара нет, 13 строк, только вот некоторые из этих строк требуют гораздо более серьезных алгоритмов для возвращения необходимых данных... Так что индусы сосут хуй )

denissign

> серьезных алгоритмов
ну НОД посчитать легко
> индусы сосут хуй
ну не совсем сосут - все же полиномиальный алгоритм

Xephon

А в газете "Правда" не писали?
Может быть лучше оригинал статьи почитать?
Так, к слову. Из случайных листочков с кафедры ТЧ - часть рецензии на доказательство Большой Теоремы Ферма: "прежде чем доказывать эту гипотезу советуем Вам немного изучить теорию чисел по серьезным книгам"

syv7

блин, не надо кидать пальцы... вот сначала реализуйте кто-нить, тогда я скажу, что этот человек - действительно отец. Индусы алгоритм придумали, но про прогу они так ничего не сказали. Кому нахуй нужен этот ебаный алгоритм без реализации.

denissign

Да нет - сказали,
насколько я понял в Bell Laboratory они и отправили прогу.

Afonya

Насчет ебучего ТЧ я читал, что недавно доказали что минимальное расстояние между соседними простыми числами ассимптотически имеет порядок меньше , чем среднее такое расстояние, т.е. является о(log n). Т.е. это продвижение по вопросу, беконечно ли число пар "близнецов" - например 11 и 13 , 29 и 31, 41 и 43 и тд.
Согласен, что фигня, но все равно - прорыв.

syv7

ааа, круто. Както сели мы реализовывать его, только запоролись на последней строчке алгоритма и потом забили

margo11

Есть запрограммированный вариант этого алгоритма. Прогал его один из студентов МГУ (не я). Тормозит уже для 5-ти значных чисел. Насколько я понимаю, проблема вовсе не в криворукости того, кто прогал, а в том, что оценка сложности алгоритма O(ln^12(n а 12-я степень - это серьезно.
Еще я слышал (от одного из сотрудников кафедры ТЧ что недавно алгоритм был улучшен и теперь он полиномиальный 2-й степени.
Новой версии алгоритма не видел.

Xephon

Просто o(log n) или какая-то более точная оценка?

beerukoffa

Алгоритм из статьи индийцев ftp://vvx.hackers/Media/primality.pdf

Xephon

Ничего себе!
Что ж ты молчал!

margo11

Я слушал доклад, где рассказывалось доказательство алгоритма. Сам алгоритм и доказательство простые и коротенькие, кроме одного места:
используется очень серьезный результат из аналитической теории чисел про распределение простых чисел с некоторыми свойствами.

syv7

воо, 12-ю строчку мы где-то час реализовывали, так ничего и не сделали... точнее я смысла ее не могу понять: буковки вроде знакомые, но...

margo11

только что вернулся с работы

Afonya

А хз. Видел на сайте Cnews( они сами небось не поняли, что написали.

stm7543347

Объясните мне, тупому, какой наибольший простой делитель у числа 1?

syv7

нет походу

stm7543347

Тогда, ИМХО, алгоритм упадёт на первой же итерации цикла...

syv7

не упадет

gateway-2002

зайди к своему соседу Жене - он спец по простым числам. а так - ну вроде сделали они и чего дальше ?

denissign

да ничего блин !
серьезный научный результат,
или тебе этого мало ?

gateway-2002

ну во первых ты к женьке сходил ? а во вторых мы его обсуждали прошлым летом. хз чего ты проснулся только щяс.

sergo60

Этот алгоритм был опубликован еще в августе того года, почему волна пошла только щас? Кому надо, смотри доказательство (на английском) \\liza\videotv\primality.pdf. Есть еще и на русском, но в бумажном варианте.

denissign

> мы его обсуждали прошлым летом
в форуме обсуждали ?

gateway-2002

в том числе. а женька все таки бухой должен быть.

sergo60

Не уважаете бл....

stm7543347

не упадет

r=2
........
if (r is prime)
let q be the largest prime factor of (r-1)...

syv7

ну значит 1 туда вписать надо.

sergo60

Число 1 не является простым, и не является составным, можете назвать его исключением.
Еденица, это еденица.

Zhannauk

Слышала, что да, индусы доказали полиномиальность. Вроде бы оценка n^12. Теоритически эта оценка хорошая, но практически она ничего не дает. 1 000 000^12 уже очень много, ни один компьютер, наверное, не справится. Вроде бы есть оценки вида c^log(log n хотя она и экспоненциальная, но она практически пременима для более больших чисел, чем первая.

Runa

И в заключение, разумеется, несколько слов о значении данного результата для криптографии.
С одной стороны, всякое продвижение в области разработки эффективных тестов простоты является хорошей новостью для криптографии. На данный момент трудно себе представить, чтобы алгоритмы проверки чисел на простоту можно было использовать в криптоанализе. В то же время, генерация ключей для криптосистем с открытым ключом, схем электронной подписи и т. п. включает в себя генерацию больших псевдослучайных простых чисел. Поэтому всякий новый эффективный тест простоты может сказаться лишь положительно на надежности и эффективности алгоритмов генерации ключей.
С другой стороны, данный алгоритм большого практического значения не имеет. Известные ранее рандомизированные алгоритмы проверки простоты весьма эффективны, а вероятность ошибки при их применении может считаться пренебрежимо малой для любых приложений.

sergo60

Абсолютно не согласен с утверждением.

margo11

Оценка не n^12, а (ln(n^12, но это все равно много

Runa

Обоснуй, пожалуйста, если у тебя есть противоположная информация...

sergo60

А кто автор этих строк?

margo11

Напиши какое-нибудь конкретное утверждение, с которым не согласен, если не влом

sergo60

И при условии выполнии гипотезы о числе простых Софи Жермен, сложность уменьшается до 6-ой степени.

Runa

Это статья с Cryptography.Ru
http://www.nature.ru/db/msg.html?mid=1188738

Xephon

Филипп Филиппович локти положил на стол, вгляделся в Шарикова и спросил:
- Позвольте узнать, что вы можете сказать по поводу прочитанного.
Шариков пожал плечами.
- Да не согласен я.
- С кем? С Энгельсом или с Каутским?
- С обоими, - ответил Шариков.
- Это замечательно, клянусь богом. "Всех, кто скажет, что другая..." А что бы вы со своей стороны могли предложить?
- Да что тут предлагать?.. А то пишут, пишут... Конгресс, немцы какие-то... Голова пухнет. Взять все, да и поделить...
- Так я и думал, - воскликнул Филипп Филиппович, шлепнув ладонью по скатерти, - именно так и полагал.
Михаил Булгаков "Собачье сердце"

Lonabigdi

Бля, чуваки, напишите еще что-нибудь такое умное, так читать интересно. Даже слова знакомые - if, ... Ой а больше нет знакомых.
Кстати, я слышал, что большая теорема Ферма доказана как один из частных случаев гипотезы Таниямы (которая доказана каким-то пиндосом кажется из Японии). Можете пинаться. Кстати, я не знаю, кто такой Ферма и что такое Танияма.

geva

Всё. это последняя капля.
Лови 5 !

stm5853057

Anonimous это я - можете пинаться.

merinus

этот результат очень значителен. хотя может быть ему нет
сейчас применения на практике, но он хорошо подстегнет
исследования в этой области. важен сам факт
полиномиальности такой проверки. дальше, как и многие
другие алгоритмы, он будет улучшаться и повлечет за
собой другие результаты.

Runa

Никто с этим и не спорит.
Результат очень интересный и важный!
Просто говорилось о конкретном практическом применении этого алгоритма в криптографии...

sol77

Так ведь ответ на вопрос простое число или нет не предполагает нахождения делителей. Я слышал, что были и до этого какие-то алгоритмы, которые позволяли очень быстро определить составное число или неизвестно какое. Так что, прорыв хотя и значительный, банки могут спать спокойно.

denissign

Я написал "продолжив тему", читай внимательней.
Понятно что именно этот алгоритм ничего не даст для ломания DF или RSA.
Оставить комментарий
Имя или ник:
Комментарий: