Побудова простих великих чисел
,
то знайдеться
простий дільник
Доведення.
Нехай
.
Тоді за умовою
теореми в силу
китайської
теореми про
залишки випливає,
що існує таке
,
що
й
.
Звідси отримуємо,
що порядок
елемента
![]()
за
модулем
задовольняє
умови:
і
не ділить
.
Тому
.
У силу
леми Гаусса
про циклічність
мультиплікативної
групи кільця
одержуємо
.
Зазначимо, що
числа
й
взаємно прості
як дільники
сусідніх чисел.
Тому
.
Отже,
.
Хоча цей результат слабкіше, ніж теорема Поклінгтона, даний підхід, як показав Н. Дієметко в 1988 р., також може бути ефективно використаний для доведення простоти чисел.
Теорема
(Дієметко).
Нехай
,
де
– просте,
–
парне й
Якщо існує ціле
таке, що
й
, то
– просте.
Доведення.
Нехай
– не просте й
.
Тоді за лемою
отримуємо, що
існує таке
,
що
.
Позначимо
Тоді
,
де
й
.
Звідси
.
Отже,
,
де
– не може дорівнювати
0, інакше
– просте, або
1, тому що
– непарне.
Аналогічно,
.
Таким чином,
.
Протиріччя. Теорему доведено.
Зазаначимо,
що за умовою
теореми числа
й
можуть бути
не взаємно
прості. Ця теорема
лежить в основі
алгоритму
генерації
простих чисел
у вітчизняному
стандарті на
цифровий підпис
Р 34.10-94.
У ньому
як
обираються
не дуже високі
степені числа
2, а
перебуває
перебором. (З
1 липня 2002 р. цей
стандарт був
замінений на
новий Р 34.10-2001).
Метод Маурера
В 1995 р. У.
Маурер опублікував
швидкий алгоритм
генерації
доведених
простих чисел,
близьких до
випадкового.
У його основі
лежить посилення
теореми Поклінгтона
на випадок,
коли факторизована
частина
числа
задовольняє
нерівності
.
Крім того, йому
вдалося оцінити
ймовірність
успіху при
випадковому
пошуку числа
в умові теореми
Поклінгтона.
Наступна лема є спеціальним випадком теореми Поклінгтона.
Лема
2.
Нехай
Якщо існує ціле
таке, що для
будь-якого
простого дільника
числа
виконані умови
і
,
те кожен простий
дільник
числа
має вигляд
при деякому
цілому
Якщо, крім того,
або
– парне й
,
то
– просте.
Доведення.
Нехай
– складене й
– нетривіальний
простий дільник
числа
.
Тоді за умови
теореми випливає,
що
й
. Міркуючи аналогічно
зауваженню
до теореми
Люка, отримуємо,
що має знайтися
елемент, який
має порядок
рівний
за модулем
.
У силу малої
теореми Ферма
.
Для
доведення
другого твердження,
припустимо,
що
.
Тоді
.
Якщо
,
то
Якщо
- непарне й
,
то
й
![]()
просте число поклінгтон мауер люк
Протиріччя.
Наступна лема доведена Д. Коувером і Дж. Куіскуотером в 1992 р.
Лема
3.
Нехай
і
задовольняють
умову леми 1.
Визначимо числа
й
рівністю
.
Якщо
й число
не дорівнює
нулю й не є повним
квадратом, то
- прості.
Доведення.
Відповідно
до леми 1 для
кожного простого
дільника
числа
виконується
нерівність
За умовою
.
Тому, якщо число
– складене,
то воно не може
мати більше
двох простих
дільників.
Нехай
и.
.
Маємо
інакше
.
Якщо
, то
![]()
Звідси
,
однак у цьому
випадку
Тому
.
Отже,
і
.
За теоремою
Вієта
є коренями
квадратного
рівняння
,
що має розв’язання
в цілих числах
у тому і тільки
в тому випадку,
якщо
є повним квадратом
або нулем. Лему
доведено.
Зазначимо, що переконатися, що задане число не є повним квадратом, можна, обчисливши символ Лежандра для декількох маленьких простих модулів. Якщо при деякому модулі число не буде квадратичним відрахуванням, то воно не буде й повним квадратом.
Нехай
– функція Ейлера.
Лема
4. Нехай
– просте число
й
.
Позначимо через
число елементів
,
порядок яких
ділиться на
.
Тоді справедлива
оцінка
,
причому
рівність виконується
в тому й у тільки
в тому випадку,
коли
![]()
Доведення. Використовуючи властивості функції Ейлера, отримуємо

причому рівність виконана в тому і тільки в тому випадку, коли
![]()
Размещено на