Тест на простоту
Тест на простоту
Чтобы сказать, является ли простым заданное число из 15 или 20 цифр, не хватит всей жизни, даже если использовать все, что уже известно.
Мерсенн, XVII в.
Что задача различать простые и составные числа, а последние разлагать на простые множители, принадлежит к важнейшим и полезнейшим задачам во всей арифметике и что она занимала ум как древних, так и современных математиков, настолько известно, что было бы излишним тратить на это много слов. Тем не менее следует признать, что все до сих пор предложенные методы или ограничиваются частными случаями, или настолько громоздки и трудоемки, что ... в основном едва ли могут быть применимы ... к большим числам ...; достоинство науки требует, чтобы прилежно усовершенствовались все вспомогательные средства, могущие помочь в решении этой знаменитой проблемы.
К. Ф. Гаусс. "Disquisitiones Arithmeticae" ("Арифметические исследования ")
