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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Лема[ред.ред. код]

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

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

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

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

Теорема Поклінґтона[ред.ред. код]

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

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

Вислід[ред.ред. код]

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

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

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

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

Кількість перевірок[ред.ред. код]

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

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

Примітки[ред.ред. код]

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

Джерела[ред.ред. код]