Методи перевірки чисел на простоту: критерій Люка та його теореми, їх доведення. Теорема Поклінгтона та її леми. Метод Маурера - швидкий алгоритм генерації доведених простих чисел, близьких до випадкового та доведення Д. Коувером і Дж. Куіскуотером.
Аннотация к работе
Побудова великих простих чисел. Розглянемо методи перевірки чисел на простоту, при застосуванні яких можна стверджувати, що перевіряючі числа дійсно є простими. На відміну від попередніх тестів, які використовували необхідні умови простоти й давали відповіді типу ? - не просте?, або ?не знаю? або ?імовірність того, що - не просте, не вище заданого як завгодно малого значення?, дані тести засновані на застосуванні достатніх умов простоти. Теорема, уперше доведена Люка в 1876 р., перетворює малу теорему Ферма в критерій простоти числа , достатня умова якого може бути ефективно використана для доказу простоти цього числа. В 1878р. Іван Михейович Первушин показав, що числа й також не є простими.