Проект "GIMPS"
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ТОП-20 участников:
----------------------------------------------------------------------------------------------------------
Дата основания команды - 29.10.2008 Капитан - bigmirok
----------------------------------------------------------------------------------------------------------
Для присоединения к команде Украины:
1. Регистрируемся на сервере проекта
2. На странице "My Team" выбираем в списке UKRAINE, жмем кнопку "Join THIS team"
3. Качаем программу для своей ОС и следуем инструкциям.
----------------------------------------------------------------------------------------------------------
О проекте:
Определение того, является ли данное число простым, в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, предложенный (и строго обоснованный теоретически) детерминированный алгоритм практически непригоден, в виду его большой, хотя и полиномиальной, сложности. Поэтому в криптографии с открытым ключом, где используются простые числа порядка 10300, простоту по-прежнему определяют с помощью эффективных вероятностных тестов, таких как тест Миллера-Рабина. Важно отметить, что если практика довольствуется числами, являющимися простыми с вероятностью близкой к 1, то теория такие числа не приемлет: если про число утверждается, что оно простое, это должно быть строго доказано. Эта разница подчёркивается в разделение алгоритмов на вероятностные и детерминированные.
Дальше на википедии
Ссылки по теме:
