?

Log in

вести с алгоритмического фронта (primality testing in P) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

вести с алгоритмического фронта (primality testing in P) [авг. 7, 2002|03:53 pm]
Anatoly Vorobey
Кажется, горячие индийские парни придумали полиномиальный алгоритм проверки числа на простоту. (ссылка на дискуссию в Слешдоте).


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

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

Примечание: "полиномиальный" алгоритм здесь означает "полиномиальный от размера данных". Т.е. полиномиальная проверка того, является ли простым число N, должна занимать время, ограниченное полиномиалом от log(N) -- размера двоичного представления N. Предлагаемый в этой статье алгоритм работает за время O(log(N)12).

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

Comments:
[User Picture]From: stas
2002-08-07 06:50 am
Насколько я понимаю, практическая ценность этого алгоритма вызывает сомнения - из-за полиномиального коэеффициента - 12 степень. Это значит, что если я могу проверять 16-битовые числа за 1 микросекунду, то для одного 256-битового числа мне понадобится 3 дня работы. Что несколько непрактично, учитывая, что тот же тест Рабина-Миллера, насколько я знаю, делает на много порядков быстрее.
(Ответить) (Thread)
From: ex_ilyavinar899
2002-08-07 06:54 am
Там говорится, что для большинства простых чисел этот тест занимает Ō(n6).

Я послал ссылку Амиту Сахаю в Принстон, но думаю, что он об этом уже слышал.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-08-07 06:57 am
Ну, как я и написал, практическая ценность невелика. То, что O(log(n)^12), как раз не так важно, поскольку это worst case.

В любом случае не удивлюсь, если все будут продолжать использовать тест Рабина-Миллера, как и раньше. Нечто похожее случилось с линейным программированием и симплексным алгоритмом (к-м все пользуются, хотя он не полиномиальный в worst-case и хотя уже довольно давно нашли полиномиальный алгоритм с большой степенью).
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-08-07 07:02 am
>давно нашли полиномиальный алгоритм с большой степенью

какой именно?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-08-07 07:24 am
Пятой, плюс всякие неприятные коэффициэнты, если я правильно помню. Короче говоря, он был непрактичным. Потом в 80-х нашли алгоритм получше... тут я уже подробностей не знаю, но по-моему до сих пор пользуются в основном симплексным.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-08-07 07:37 am
в общих случаях изпользуют interior point method

http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/continuous/constrained/linearprog/section2_1_2.html
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2002-08-07 08:50 am
Насколько я знаю, interior-point алгоритмы типа Кармакара тоже повсеместно используются. Кроме того, доказано, что рандомизированный симплекс полиномиален.

mkay422 больше знает о применении различных алгоритмов математического программирования на Уолл Стрит.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-08-07 09:11 am

Re:

Рандомизированный симплекс, наверное, полиномиален радндомизированно всё-таки, а не детерминированно?
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2002-08-07 09:27 am

Re:

Конечно.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-08-07 09:39 am

Re:

Ну так это not one and that same, как говорится.
(Ответить) (Parent) (Thread)
[User Picture]From: lr33
2002-08-08 12:57 am

Ой, простите!

А можно я эту фразу в memories занесу?
:-)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-08-08 01:00 am

Re: Ой, простите!

Запросто ;)
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2002-08-07 08:52 am
IIT - очень крутое место!!! В Microsoft Research есть несколько выпускников оттуда.
(Ответить) (Thread)
From: (Anonymous)
2002-08-15 01:58 pm

математика

В Москве говорили что индусы нашли способ определения простых чисел.Эх - не люблю неточных формулировок. Хотя - может быть я не понимаю?вот и спрашиваю..мне кажется они нашли способ проверить уже известное число на то простое оно или сложное.А вот алгоритма определени е простого числа они не сделали.Хотя он тоже достаточно прост.
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2002-08-15 02:42 pm

Re: математика

Индусы нашли новый способ определения, простое число или составное. Этот способ по некоторым характеристикам лучше, чем существующие (хотя на практике существующие способы будут продолжаться использоваться).
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-08-15 03:15 pm

Re: математика

Если число составное то находят множители числа? А в способе индусов насколько точно они опреджеляют они что это простое число?У меня жутко наивная просьба.....объясните мне "на пальцах" в чем их способ заключается????Индусы могут дать быстро сколько угодно простых чисел?
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2002-08-15 03:33 pm

Re: математика

Нет, они не находят множители числа - они определяют, что число составное по косвенным признаком.

Если алгоритм индусов говорит, что число простое - оно действительно простое. В этом состоит отличие этого алгоритма от популярного алгоритма Рабина-Миллера, который утверждал это лишь с определенной вероятностью. Вероятность можно было довести как угодно близно до единицы, но время работы алгоритма при этом увеличивалось. В алгоритме индусов нет никаких вероятностей.

На пальцах объяснять я не берусь. Может, кто-то еще попробует.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-08-15 03:38 pm

Re: математика

Значит индусы могут найти в любом диапазоне все простые числа? (Это ничего что я терзаю вас своими делитанскими вопросами?)
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2002-08-15 03:39 pm

Re: математика

Да.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-08-15 03:46 pm

Re: математика

А Вы не можете мне сказать на какой проблеме возникла гипотеза Римана? Интересно просто что же такое решалось что бы привело к ней.
И еще...вот эти индусы..они что - просто написали всем письма с решением и параллельно выложили свое решение на сайте и тем самым защитили себя?А вдруг кто0-то скажет что раньше сделал?НЕужели так просто они пошли на риск?Вот какой поток вопросов.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-08-15 04:10 pm
Скажите пожалуйста, а индусы каждое число в отдельности проверяют или могут выдать блоком N-ое количество простых чисел в любом интервале числового ряда?
(Ответить) (Thread)
[User Picture]From: avva
2002-08-15 11:56 pm

Re:

Каждое в отдельности.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-08-16 12:05 pm
Спасибо. Помогите - нигде не могу выяснить на решении какой задачи возникла гипотеза Римана?
(Ответить) (Parent) (Thread)