информационная безопасность
без паники и всерьез
 подробно о проекте
Rambler's Top100Атака на InternetSpanning Tree Protocol: недокументированное применение
BugTraq.Ru
Русский BugTraq
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Модель надежности отказоустойчивой... 
 Неприятные уязвимости в роутерах... 
 Chrome отмечает десятилетие редизайном 
 Foreshadow продолжает дело Meltdown... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / RSN / архив / 2002 / август
2002
главная
январь
февраль
март
апрель
май
июнь
июль
август
сентябрь
октябрь
ноябрь
декабрь
предложить новость




Paragon Partition Manager 7.0

Проблема простых чисел не сдается
cybervlad // 13.08.02 10:32
Многие аспекты современной криптографии зависят от простых чисел.
[Не забывайте при копировании материала указывать полный адрес источника: http://www.bugtraq.ru/rsn/archive/2002/08/11.html]
При этом всегда встает проблема проверки выбранного числа на простоту. Если для небольших чисел проблема решается путем полной проверки или использованием алгоритма, известного под названием "решето Эратосфена", то с большими числами это вычислительно трудно осуществимо. Поэтому на практике применяется ряд оценочных методов, позволяющих с достаточной долей уверенности сказать, является число простым или нет. При этом существует вероятность, что прошедшее тест число все-таки окажется составным (так называемые числа Кармайкла (Кармихаэля) ведут себя при тестах как простые, на самом деле являясь составными). Открытие индийских математиков, профессора Manindra Agarwal и двух студентов Nitin Saxena и Neeraj Kayal позволит разрешить данную проблему. Предложенный ими алгоритм работает медленее, чем применяемые сегодня, зато позволяет точно выяснить, является число простым или нет.

Источник: Indian Institute of Technology Kanpur      
предложить новость  |  обсудить  |  все отзывы (3) [3408]
назад «  » вперед

последние новости
Неприятные уязвимости в роутерах MicroTik // 05.09.18 15:16
Chrome отмечает десятилетие редизайном // 05.09.18 14:29
Foreshadow продолжает дело Meltdown и Spectre // 15.08.18 16:59
Попасть под лошадь // 27.07.18 14:39
Последний спокойный день для сайтов без https // 23.07.18 18:08
Google по-тихому включила изоляцию сайтов в последних версиях Chrome // 12.07.18 16:13
25 лет FreeBSD // 19.06.18 12:33

Комментарии:

Скорее наоборот: найден полиномиальный алгоритм для проблемы простоты числа. 14.08.02 01:42  
Автор: Biasha <Бяша> Статус: Member
<"чистая" ссылка>
полиномиальный он только формально ;) 14.08.02 07:19  
Автор: cybervlad <cybervlad> Статус: Elderman
<"чистая" ссылка>
ибо шибко тормозной все-таки.
индусы ведь ничего принципиально нового не выдумали, использовали древнюю китайскую математику ;) т.е. способ был известен и раньше, видимо, они просто первые, кто догнал, что скорость компьютеров выросла настолько, что можно всерьез задумываться о практическом применении метода...
полиномиальный он только формально ;) 14.08.02 07:38  
Автор: Biasha <Бяша> Статус: Member
<"чистая" ссылка>
> ибо шибко тормозной все-таки.
> индусы ведь ничего принципиально нового не выдумали,
> использовали древнюю китайскую математику ;) т.е. способ
> был известен и раньше, видимо, они просто первые, кто
> догнал, что скорость компьютеров выросла настолько, что
> можно всерьез задумываться о практическом применении
> метода...

Причём здесь скорость кмп'ютера? Раньше не было известно к какому классу относится проблема простоты числа. Теперь известно - к P. А тормозной он только формально :) главное полиномиальный.
А что значит способ был известен и раньше? Раньше то не было полиномиального алгоритма.
<добавить комментарий>


анонимность клоуны конференции спам уязвимости .net acrobat activex adobe android apple beta bgp bitcoin blaster borland botnet chrome cisco crypto ctf ddos dmca dnet dns dos dropbox eclipse ecurrency eeye elcomsoft excel facebook firefox flash freebsd gnome google gpl hp https ibm icq ie intel ios iphone java javascript l0pht leak linux livejournal mac mcafee meltdown microsoft mozilla mysql netware nginx novell ny open source opera oracle os/2 outlook password patch php powerpoint pwn2own quicktime rc5 redhat retro rip router rsa safari sco secunia server service pack shopping skype smb solaris sony spyware sql injection ssl stuff sun symantec torrents unix virus vista vmware vpn wikipedia windows word xp xss yahoo yandex youtube



Rambler's Top100
Рейтинг@Mail.ru



  Copyright © 2001-2018 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach