Алгоритмы поиска простых чисел

«Самое большое простое число 2^32582657-1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс

Натуральное число называется простым, если оно имеет только два различных делителя: единицу и само себя. Задача поиска простых чисел не дает покоя математикам уже очень давно. Долгое время прямого практического применения эта проблема не имела, но все изменилось с появлением криптографии с открытым ключом. В этой заметке рассматривается несколько способов поиска простых чисел, как представляющих исключительно академический интерес, так и применяемых сегодня в криптографии.