Тест на простоту Поклінґтона

Тест на простоту Поклінґтона (англ. Pocklington–Lehmer primality test) — тест на простоту розроблений Генрі Кабурн Поклінґтоном і Деріком Генрі Лемером для визначення чи є число простим. На виході тесту або доведення простоти, або неможливість доведення.

ЛемаРедагувати

Нехай   Якщо для кожного простого дільника   для   існує ціле таке, що

  1.  
  2.  

тоді   — просте.

Позначення:   означає, що   ділить  

Доведення: Для того, щоб показати, що   просте нам потрібно лише показати, що   або простіше, що   Припустимо це не так, тоді існує просте   і показник   такий, що   але не ділить   Для цього цілого   ми маємо мати ціле, що задовольняє попереднім умовам. Тепер нехай   буде порядком   за модулем   тоді   (перша умова), але не ділить   (друга умова). Отже   ділить   яке ділить   — протиріччя, яке доводить лему.

Теорема ПоклінґтонаРедагувати

Теорема Поклінґтона (англ. Pocklington's Theorem) (1914): Нехай   де   — просте, яке не ділить   Якщо існує ціле таке, що   і   тоді кожен простий дільник   для   має вигляд  

Доведення: Нехай   — довільний простий дільник   і нехай   буде порядком   за модулем   Як і в лемі,   (перша умова для   але не ділить   (друга умова); отже   Звісно,   і звідси висновок.

ВислідРедагувати

Вислідом застосування теореми Поклінґтона до кожного простого степеневого дільника   (плюс трошки роботи) є:

Теорема: Припустимо, що   (тобто   ), де     і відома факторизація  . Якщо існує ціле   що задовольняє:

  1.  
  2.   для кожного  

тоді кожен простий дільник   для   конгруентний   за модулем   З цього випливає, що якщо   тоді   є простим.

Кількість перевірокРедагувати

Нехай   буде непарним простим з   і   І нехай різними простими дільниками для   будуть   Тоді ймовірність, що випадково обрана база     задовольняє обом умовам:   і   для кожного     становить  

Отже, якщо відома факторизація дільника   тоді для перевірки на простоту, можна просто обирати випадкові цілі в інтервалі   доки на знайдеться таке, що задовольняє умовам 1 і 2, тобто   просте. Якщо таке   не знайшли після розумної кількості ітерацій,[1] тоді   імовірно складене і це можна перевірити через застосування ймовірнісного тесту на простоту.

ПриміткиРедагувати

  1. За кількість ітерацій можна взяти   де   і де  

ДжерелаРедагувати