Побудова простих великих чисел (стр. 3 из 4)

Хоча цей результат слабкіше, ніж теорема Поклінгтона, даний підхід, як показав Н. Дієметко в 1988 р., також може бути ефективно використаний для доведення простоти чисел.

Теорема (Дієметко). Нехай

, де – просте, – парне й Якщо існує ціле таке, що й , то – просте.

Доведення. Нехай

– не просте й . Тоді за лемою отримуємо, що існує таке , що .

Позначимо

Тоді , де й . Звідси . Отже, , де – не може дорівнювати 0, інакше – просте, або 1, тому що – непарне. Аналогічно, . Таким чином,

.

Протиріччя. Теорему доведено.

Зазаначимо, що за умовою теореми числа

й можуть бути не взаємно прості. Ця теорема лежить в основі алгоритму генерації простих чисел у вітчизняному стандарті на цифровий підпис Р 34.10-94.

У ньому як

обираються не дуже високі степені числа 2, а перебуває перебором. (З 1 липня 2002 р. цей стандарт був замінений на новий Р 34.10-2001).

Метод Маурера

В 1995 р. У. Маурер опублікував швидкий алгоритм генерації доведених простих чисел, близьких до випадкового. У його основі лежить посилення теореми Поклінгтона на випадок, коли факторизована частина

числа задовольняє нерівності . Крім того, йому вдалося оцінити ймовірність успіху при випадковому пошуку числа в умові теореми Поклінгтона.

Наступна лема є спеціальним випадком теореми Поклінгтона.

Лема 2. Нехай

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

Доведення. Нехай

– складене й – нетривіальний простий дільник числа . Тоді за умови теореми випливає, що й . Міркуючи аналогічно зауваженню до теореми Люка, отримуємо, що має знайтися елемент, який має порядок рівний за модулем . У силу малої теореми Ферма .

Для доведення другого твердження, припустимо, що

. Тоді .
Якщо , то Якщо - непарне й , то й

просте число поклінгтон мауер люк

Протиріччя.

Наступна лема доведена Д. Коувером і Дж. Куіскуотером в 1992 р.

Лема 3. Нехай

і задовольняють умову леми 1. Визначимо числа й рівністю . Якщо й число не дорівнює нулю й не є повним квадратом, то - прості.

Доведення. Відповідно до леми 1 для кожного простого дільника

числа виконується нерівність За умовою . Тому, якщо число

– складене, то воно не може мати більше двох простих дільників. Нехай

и. .

Маємо

інакше .

Якщо

, то

Звідси

, однак у цьому випадку Тому .

Отже,

і . За теоремою Вієта є коренями квадратного рівняння , що має розв’язання в цілих числах у тому і тільки в тому випадку, якщо є повним квадратом або нулем. Лему доведено.