Побудова великих простих чисел.
Розглянемо методи перевіркі чисел на простоту, при застосуванні якіх можна стверджуваті, что перевіряючі числа Дійсно є простими. p> На відміну від попередніх тестів, Які вікорістовувалі необхідні умови простота й давали ВІДПОВІДІ типом ВІ - не просте ВІ, або ВІ не знаю ВІ або ВІ імовірність того, что - не просте, не Вище заданого як завгодно малого значення ВІ, дані тести засновані на застосуванні достатніх умів простота. Тому смороду могут давати як ВІДПОВІДІ типом ВІ - Не просте ВІ, ВІ не знаю ВІ, так ї ВІ - просте ВІ. p> Ця властівість застосовується для Побудова простих чисел. Загальна схема в цьом випадка така: обірається Деяка послідовність чисел СПЕЦІАЛЬНОГО увазі, среди якіх нужно найти просте число, потім до чисел Із цієї послідовності застосовується тест Доті, доки ВІН НЕ дасть позитивний відповідь. p> Если ця відповідь ВІ - не просте ВІ, то обірається Наступний число. Если ОТРИМАНО відповідь ВІ - Просте ВІ, то Шуканов просте число побудоване. p> Розглянемо достатні умови простота чисел, Які, звичайна, застосовуються в алгоритмах побудова доказово простих чисел.
Крітерій Люка.
Теорема, упершись доведена Люка в 1876 р., перетворює малу теорему Ферма в крітерій простота числа, достатності Умова Якого может буті Ефективно Використана для доказу простота цього числа.
Теорема 1. (Люка)
Натуральне число є пробачимо у того и Тільки в того випадка, коли віконується Умова
(1)
В
Доведення.
Если просте, то в полі є прімітівній елемент, что и буде Шуканов. Навпаки, нехай для елемента віконується Умова (1). Если, ті, причому Умова (1) гарантує, що. Отже, и
- Просте. Теорема доведена. p> Зауваження (Селфрідж).
Умова (1) у даній теоремі можна замініті на шкірні з таких розумів:
(2)
(3)
Дійсно, ті, что (1) => (2) ї (1) => (3), очевидно. p> Доведемо, что (3) => (2). Нехай. За умів для шкірного знайдеться таке, что, но НЕ діліть число. p> Отже,. Отже, знайдуться елєменти, Такі, що. Тепер елемент буде Шуканов, ТОМУ ЩО порядки ЕЛЕМЕНТІВ взаємно Прості й
В В В
Теорема Люка дозволяє довести простоту числа у випадка, коли відоме розкладання на Прості співмножнікі числа
Для цього можна вікорістаті детермінованій алгоритм, Заснований на переборі всех можливіть значень, або скористати таким імовірніснім методом:
1) Обираємо віпадкові числа ї перевіряємо для них умову (1);
2) ЯКЩО Умова (1) виконан хочай б для одного Із ціх чисел, то просте, ЯКЩО ні, то відповідь невідома.
Аналогічній метод можна побудуваті, вікорістовуючі умову (3).
Проілюструємо цею метод Стосовно до чисел Ферма.
Числами Ферма назівають числа виду (Покажіть, что число увазі может буті пробачимо у того и Тільки в того випадка, коли.)
Ферма вісловлював припущені, что ВСІ числа такого виду - Прості. При Це дійсно так. Альо при, як показавши Ейлер в 1732 р., Справедливе розкладання
.
У 1878р. Іван Міхейовіч Первушин показавши, что числа ї такоже НЕ є простими. (Зазаначімо, что число має 2525223 цифри. При відтворенні такого числа знадобівся б рядок Довжина в 5 км або книга об'ємом 1000 сторінок).
Теорема 2 . ( Пепін, 1877 ). p> Числа при є простим у того и Тільки в того випадка, коли віконується Умова
Доведення. Оскількі Єдиним пробачимо дільніком число є 2, то Достатньо перевіріті умову теореми Люка прі. Покажемо, что як число можна взяти число 3, тоб Достатньо перевіріті умову Вікорістовуючі формулу Ейлера для обчислення значень квадратичного лішків и квадратичним законом взаємності Гаусса отрімуємо, что при простому має буті
В
Тепер зазаначімо, что, и того Умова рівносільна рівності Теорема доведена.
Теорема Люка послужила відправнім пунктом для побудова цілої групи тестів, что дозволяють перевіряті простоту числа. Багатая хто з них отримай Назва - методів, ТОМУ ЩО пріпускають знання повної або часткової факторізації числа. p> Ще Одне узагальнення теореми Люка засновано на розгляді других груп вместо мультіплікатівної групи. Фактично, доказ простота числа в теоремі Люка засновано на вівченні властівостей групи: ЯКЩО будь-яким чином вдається Встановити, что ее порядок дорівнює, то число - просте. p> Дана ідея лежить в Основі таких методів, як метод еліптічніх кривих и метод числового поля.
Теорема Поклінгтона.
У 1914 р., Х. Поклінгтоном булу доведена наступна теорема.
Теорема 3. (Поклінгтон). Нехай, де - просте, что НЕ є дільніком. Если існує ціле таке, что й, то КОЖЕН Простий дільнік числа має вигляд при якомусь. p> Доведення. Нехай - Простий дільнік числа. Тоді з умови теореми
віпліває...
