BugTraq.Ru
Русский BugTraq
http://www.bugtraq.ru/rsn/archive/2002/08/11.html

Проблема простых чисел не сдается
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) [3665]
назад «  » вперед

последние новости
Phrack #70/0x46 // 07.10.21 02:46
Возможно, Facebook наступил на те же грабли с BGP, что и Яндекс десять лет назад // 04.10.21 23:36
50 лет электронной почте // 02.10.21 00:00
Заканчивается действие одного из корневых сертификатов Let’s Encrypt // 30.09.21 17:01
Очередной юбилей Linux // 25.08.21 14:56
HP закрыла 16-летнюю уязвимость в драйверах принтеров // 20.07.21 15:14
Microsoft советует пользователям отключить службу печати // 17.07.21 03:22

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

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

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



  Copyright © 2001-2021 Dmitry Leonov Design: Vadim Derkach