Тест на простоту Поклінґтона: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
|||
Рядок 27:
Нехай <math>n = RF + 1</math> буде непарним простим з <math>F > \sqrt n - 1</math> і <math>\gcd(R, F) = 1.</math> І нехай різними простими дільниками для <math>F</math> будуть <math>q_1, q_2, \dots, q_t.</math> Тоді ймовірність, що випадково обрана база <math>a,</math> <math>1\le a \le n-1,</math> задовольняє обом умовам: <math>a^{n-1} \equiv \pmod n;</math> і <math>\gcd(a^{(n-1)/q_j} - 1, n)=1</math> для кожного <math>j,</math> <math>1\le j\le t,</math> становить <math>\prod_{j=1}^t (1-1/q_j)\ge 1 - \sum_{j=1}^t 1/q_j.</math>
Отже, якщо відома факторизація дільника <math>F > \sqrt n-1,</math> тоді для перевірки на простоту, можна просто обирати випадкові цілі в інтервалі <math>[2, n-2]</math> доки на знайдеться таке, що задовольняє умовам 1 і 2, тобто <math>n</math> просте. Якщо таке <math>a</math> не знайшли після ''розумної'' кількості ітерацій,<ref>За кількість ітерацій можна взяти <math>T,</math> де <math>P^T \le \left(\frac{1}{2}\right)^{100},</math> і де <math>P = 1 - \prod_{j=1}^t(1-1/q_j).</math></ref> тоді <math>n</math> імовірно складене і це можна перевірити через застосування ймовірнісного тесту на простоту.
== Примітки ==
| |||