Книга: Побудова простих великих чисел

Побудова великих простих чисел.

Розглянемо методи перевірки чисел на простоту, при застосуванні яких можна стверджувати, що перевіряючі числа дійсно є простими.

На відміну від попередніх тестів, які використовували необхідні умови простоти й давали відповіді типу ² - не просте², або ²не знаю² або ²імовірність того, що – не просте, не вище заданого як завгодно малого значення², дані тести засновані на застосуванні достатніх умов простоти. Тому вони можуть давати як відповіді типу ² - не просте², ²не знаю², так й ² - просте².

Ця властивість застосовується для побудови простих чисел. Загальна схема в цьому випадку така: обирається деяка послідовність чисел спеціального виду, серед яких потрібно знайти просте число, потім до чисел із цієї послідовності застосовується тест доти, доки він не дасть позитивну відповідь.

Якщо ця відповідь ²- не просте², то обирається наступне число. Якщо отримано відповідь ² - просте², то шукане просте число побудоване.

Розглянемо достатні умови простоти чисел, які, звичайно, застосовуються в алгоритмах побудови доказово простих чисел.

Критерій Люка.

Теорема, уперше доведена Люка в 1876 р., перетворює малу теорему Ферма в критерій простоти числа , достатня умова якого може бути ефективно використана для доказу простоти цього числа.

Теорема 1. (Люка)

Натуральне число є простим у тому і тільки в тому випадку, коли виконується умова

(1)

Доведення.

Якщо просте, то в полі є примітивний елемент, що і буде шуканим. Навпаки, нехай для елемента виконується умова (1). Якщо , те, причому умова (1) гарантує, що . Отже, і
– просте. Теорема доведена.

Зауваження (Селфридж).

Умова (1) у даній теоремі можна замінити на кожну з таких умов:

(2)

--> ЧИТАТЬ ПОЛНОСТЬЮ <--