Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Проблема простых чисел не сдается 13.08.02 10:32
Publisher: cybervlad <cybervlad> Статус: Elderman
|
Проблема простых чисел не сдается
Indian Institute of Technology Kanpur http://www.cse.iitk.ac.in/news/primality.html
Многие аспекты современной криптографии зависят от простых чисел. При этом всегда встает проблема проверки выбранного числа на простоту. Если для небольших чисел проблема решается путем полной проверки или использованием алгоритма, известного под названием "решето Эратосфена", то с большими числами это вычислительно трудно осуществимо. Поэтому на практике применяется ряд оценочных методов, позволяющих с достаточной долей уверенности сказать, является число простым или нет. При этом существует вероятность, что прошедшее тест число все-таки окажется составным (так называемые числа Кармайкла (Кармихаэля) ведут себя при тестах как простые, на самом деле являясь составными). Открытие индийских математиков, профессора Manindra Agarwal и двух студентов Nitin Saxena и Neeraj Kayal позволит разрешить данную проблему. Предложенный ими алгоритм работает медленее, чем применяемые сегодня, зато позволяет...
Полный текст
|
|
Скорее наоборот: найден полиномиальный алгоритм для проблемы простоты числа. 14.08.02 01:42
Автор: Biasha <Бяша> Статус: Member
|
|
|
| |
полиномиальный он только формально ;) 14.08.02 07:19
Автор: cybervlad <cybervlad> Статус: Elderman
|
ибо шибко тормозной все-таки.
индусы ведь ничего принципиально нового не выдумали, использовали древнюю китайскую математику ;) т.е. способ был известен и раньше, видимо, они просто первые, кто догнал, что скорость компьютеров выросла настолько, что можно всерьез задумываться о практическом применении метода...
|
| | |
полиномиальный он только формально ;) 14.08.02 07:38
Автор: Biasha <Бяша> Статус: Member
|
> ибо шибко тормозной все-таки.
> индусы ведь ничего принципиально нового не выдумали,
> использовали древнюю китайскую математику ;) т.е. способ
> был известен и раньше, видимо, они просто первые, кто
> догнал, что скорость компьютеров выросла настолько, что
> можно всерьез задумываться о практическом применении
> метода...
Причём здесь скорость кмп'ютера? Раньше не было известно к какому классу относится проблема простоты числа. Теперь известно - к P. А тормозной он только формально :) главное полиномиальный.
А что значит способ был известен и раньше? Раньше то не было полиномиального алгоритма.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
