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

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

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

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

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

  1. a^{n-1} \equiv 1 \pmod n,
  2. a^{(n-1)/q} \not\equiv 1 \pmod n;

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

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

Доведення: Для того, щоб показати, що n просте нам потрібно лише показати, що \phi(n) = n - 1, або простіше, що (n - 1) | \phi(n). Припустимо це не так, тоді існує просте q і показник r > 0 такий, що q^r | (n-1), але не ділить \phi(n). Для цього цілого q ми маємо мати ціле, що задовольняє попереднім умовам. Тепер нехай m буде порядком a за модулем n, тоді m | (n-1) (перша умова), але не ділить (n-1)/q (друга умова). Отже q^r ділить m, яке ділить \phi(n) — протиріччя, яке доводить лему.

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

Теорема Поклінґтона (англ. Pocklington's Theorem) (1914): Нехай n-1 = q^kR, де q — просте, яке не ділить R. Якщо існує ціле таке, що a^{n-1} \equiv 1 \pmod n і \gcd(a^{(n-1)/q}-1, n) = 1, тоді кожен простий дільник p для n має вигляд q^kr+1.

Доведення: Нехай p — довільний простий дільник n, і нехай m буде порядком a за модулем p. Як і в лемі, m|(n-1)=q^kR (перша умова для a), але не ділить (n-1)/q=q^{k-1}R (друга умова); отже q^k|m. Звісно, m|(p-1) і звідси висновок.

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

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

Теорема: Припустимо, що n-1 = F\times R (тобто F|(n-1) ), де  F>R, \gcd(F,R)=1 і відома факторизація F=\prod_{j=1}^t q_j^{e_j}. Якщо існує ціле a, що задовольняє:

  1. a^{n-1} \equiv 1 \pmod n;
  2. \gcd(a^{(n-1)/q_j} - 1, n) = 1 для кожного j, 1 \le j \le t,

тоді кожен простий дільник p для n конгруентний 1 за модулем F. З цього випливає, що якщо F > \sqrt n-1, тоді n є простим.

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

Нехай n = RF + 1 буде непарним простим з F > \sqrt n - 1 і \gcd(R, F) = 1. І нехай різними простими дільниками для F будуть q_1, q_2, \dots, q_t. Тоді ймовірність, що випадково обрана база a, 1\le a \le n-1, задовольняє обом умовам: a^{n-1} \equiv \pmod n; і \gcd(a^{(n-1)/q_j} - 1, n)=1 для кожного j, 1\le j\le t, становить \prod_{j=1}^t (1-1/q_j)\ge 1 - \sum_{j=1}^t 1/q_j.

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

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

  1. За кількість ітерацій можна взяти T, де P^T \le \left(\frac{1}{2}\right)^{100}, і де P = 1 - \prod_{j=1}^t(1-1/q_j).

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