Перегляд вихідного коду сторінки Тест простоти Міллера — Рабіна

У Вас нема дозволу на редагування цієї сторінки з такої причини:

Ваша IP-адреса знаходиться в діапазоні, який заблоковано у всіх вікі Фонду Вікімедіа.

Блокування зроблено ‪EPIC‬. Причиною вказано Open proxy/Webhost: See the help page if you are affected.

Початок блокування: 08:48, 2 липня 2024
Закінчення блокування: 08:48, 2 липня 2025

Ваша поточна IP-адреса: 206.189.44.186. Заблокований діапазон — 206.189.32.0/20.

Будь ласка, додайте всі вказані подробиці до будь-яких запитів, які Ви будете робити. Якщо ви вважаєте, що вас заблокували помилково, ви можете знайти додаткову інформацію та інструкції в глобальній політиці Без відкритих проксі.

В іншому випадку, щоб обговорити блокування, будь ласка, опублікуйте запит на розгляд на Мета-вікі. Ви також можете надіслати електронний лист до VRT-черги стюардів за адресою stewards@wikimedia.org, вказавши усю вищезазначену інформацію.

Ви можете переглянути та скопіювати вихідний текст цієї сторінки:

'''Тест простоти Міллера — Рабіна''' або '''тест Міллера – Рабіна'''&nbsp;— це [[тест простоти]]: алгоритм, який визначає чи є надане число [[просте число|простим]]. Його початкова версія, яку розробив професор Міллер, є детерміністичною, але детермінізм покладається на недоведену [[узагальнена гіпотеза Рімана|узагальнену гіпотезу Рімана]];<ref name="miller">{{Citation |last=Гарі Міллер |year=1976 |title=Ріманова гіпотеза і тест на простоту |journal=Journal of Computer and System Sciences |volume=13 |issue=3 |pages=300–317 |doi=10.1145/800116.803773 }}</ref> [[Міхаель Рабін]] змінив її, щоб отримати безумовний [[увипадковлений алгоритм|імовірнісний алгоритм]].<ref name="rabin">{{Citation |last=Міхаель Рабін |first= |year=1980 |title=Ймовірнісний алгоритм для перевірки простоти |journal=Journal of Number Theory |volume=12 |issue=1 |pages=128–138 |doi=10.1016/0022-314X(80)90084-0 }}</ref>

== Вступ ==
Для багатьох застосувань, як-от криптографія, ми потребуємо великих [[Випадкове просте число|''випадкових'' простих чисел]]. На щастя, великі прості не такі вже й рідкісні, тому можливо перевіряти цілі потрібного розміру, щоб знайти серед них просте. Функція розподілу простих чисел <math>\pi(n)</math> визначає кількість простих чисел, які менші ніж <math>n</math>. Наприклад, <math>\pi(10)=4.</math> Відомо, що
: <math>\lim_{n \to \infty}\frac{\pi(n)}{n/\lg n}=1.</math>
Це досить якісне наближена оцінка для <math>\pi(n).</math> З цього ми маємо, що ймовірність того, що <math>n</math> є простим дорівнює <math>1/\lg n</math>. [[Геометричний розподіл]] підказує нам, що очікувана кількість спроб для знаходження простого числа становить <math>\lg n</math>. Також ми, звісно, можемо опустити парні числа, що зменшує кількість спроб удвічі.

Наївним способом перевірки чи число просте був би повний перебір можливих дільників. Тобто для числа <math>n</math> потрібно було б перебрати <math>2, 3, \dots, \lfloor \sqrt n \rfloor</math>. Знов-таки, ми можемо пропускати парні числа більші ніж двійка. Якщо вважати, що кожне пробне ділення потребує однаково часу, то складність буде <math>O(\sqrt n)</math>, така складність є експоненційною для <math>n</math>. Алгоритми з такою складністю, зазвичай вважають повільними. Хоча у такого алгоритму є й перевага, він знаходить дільники <math>n</math>, тобто [[Факторизація цілих чисел|розкладає]] число.

==Ймовірнісні тести простоти==
Найвідомішими ймовірнісними тестами простоти є [[тест Соловея — Штрассена]] і тест Міллера — Рабіна. В обох випадках базова процедура та сама: ми визначаємо множину <math>W</math> свідків того, що <math>n</math> є складеним. Якщо ми можемо знайти <math>w \in W,</math> тоді <math>W \ne \empty,</math> і <math>n</math> є складеним числом. У випадку тесту Міллера — Рабіна <math>W:=\overline{W_n}.</math>

===Оцінка кількості свідків===
Нехай <math>n\in \mathbb{N}</MATH> буде непарним числом і нехай <math>n-1=2^tm,</math> з непарним <math>m.</math> Припустимо, що <math>n</math> просте. Тоді квадратними коренями з <math>1</math> будуть лише <math>\pm 1,</math> тобто єдиними розв'язками <math>x^2-1</math> за модулем 2. Більше того, <math>a^{n-1}\equiv 1\mod n</math> для кожного <math>a\in\mathbb{N},</math> яке просте з <math>n.</math> Отже, 
:<math>a^{n-1}\equiv 1\mod n</math> і <math>a^{(n-1)/2}\equiv \pm 1\mod n,</math> і 
:якщо <math>a^{(n-1)/2}\equiv 1\mod n,</math> тоді <math>a^{(n-1)/4}\equiv \pm 1\mod n,</math> і
:якщо <math>a^{(n-1)/4}\equiv 1\mod n,</math> тоді <math>\dots</math>
Ми бачимо: якщо <math>n</math> є простим, тоді для кожного <math>a\in\mathbb{N}</math> за умови, що <math>\gcd(a,n)=1,</math> або <math>a^m\equiv 1\mod n,</math> або існує <math>j\in \{0,\dots,t-1\}</math> з <math>a^{2^jm}\equiv -1\mod n.</math> Зворотнє твердження також істинне, тобто, якщо <math>n</math> є складеним, тоді існує <math>a\in \mathbb{N}</math> з <math>\gcd(a,n)=1,</math> таке що <math>a^m\not\equiv 1\mod n</math> і <math>a^{2^jm}\not\equiv-1\mod n</math> для <math>0\le j\le t-1.</math> І точніше:

'''Теорема:''' Нехай <math>n \in \mathbb{N}</math> буде складеним непарним числом. Нехай <math>n-1=2^tm,</math> з непарним <math>m.</math> Нехай 
:<math>\overline{W_n}=\{[a]\in\mathbb{Z}_n^*|a^m\not\equiv 1\mod n, a^{2^jm}\not\equiv -1\mod n, 0\le j\le t-1\}.</math>
Тоді <math>|\overline W_n| \ge \varphi{(n)}/2.</math>

===Порівняння з тестом Соловея—Штрассена===
Тест Міллера — Рабіна буде кращим вибором:
# Легше обчислити тестові умови.
# Свідок для тесту Соловея—Штрассена також свідок для тесту Міллера — Рабіна.
# У тесті Міллера — Рабіна ймовірність натрапити на свідка за одну випадкову спробу більша ніж 3/4, а у тесті Соловея—Штрассена 1/2.

==Псевдокод==
{| class="wikitable"
|-
|
'''МІЛЛЕР-РАБІН'''<math>(n, k)</math>
# '''якщо''' <math>n</math> парне '''тоді'''
# &emsp;'''повернути''' ХИБА
# <math>m\gets (n-1)\ \mbox{div}\ 2; t \gets 1</math>
# '''поки''' <math>m</math> парне
# &emsp;<math>m\gets m\ \mbox{div}\ 2; t\gets t+1</math>
# '''для''' <math>i\gets 1</math> '''до''' <math>k</math>
# &emsp;<math>a\gets Random() \mod n</math>
# &emsp;<math>u\gets a^m\mod n</math>
# &emsp;'''якщо''' <math>u\ne 1</math> '''тоді'''
# &emsp;&emsp;<math>j\gets 1</math>
# &emsp;&emsp;&emsp;'''поки''' <math>u\ne n - 1</math> і <math>j<t</math>
# &emsp;&emsp;&emsp;&emsp;<math>u\gets u^2\mod n; j\gets j+1</math>
# &emsp;&emsp;&emsp;'''якщо''' <math>u\ne n-1</math> '''тоді'''
# &emsp;&emsp;&emsp;&emsp;'''повернути''' ХИБА
# '''повернути''' ІСТИНА
|}
Імовірність помилки <math>\le 1/4^k.</math>

== Див. також ==
* [[Тест Соловея — Штрассена]]

== Примітки ==
{{reflist}}

== Джерела ==
* {{CLRS|chapter=31 Теоретико-числові алгоритми}}
* {{cite book
| прізвище1                   = Hans Delfs
| прізвище2                   = Helmut Knebl
| назва                   = Introduction to Cryptography. Principles and Applications.
| видання                 = 2
| рік-оригіналу           = 2007
| видавець                = Springer
| isbn                    =  978-3-540-49243-6
| сторінки                = 319-324
| розділ                  = A.8 Primes and Primality Tests
}}

{{Алгоритми теорії чисел}}
[[Категорія:Тести простоти]]
[[Категорія:Скінченні поля]]

Шаблони, використані на цій сторінці:

Шаблон:CLRS (редагувати)
Шаблон:Citation (переглянути вихідний код) (частково захищено)
Шаблон:Cite book (переглянути вихідний код) (захищено)
Шаблон:Hlist/styles.css (переглянути вихідний код) (захищено)
Шаблон:Iw (переглянути вихідний код) (захищено)
Шаблон:Main other (переглянути вихідний код) (захищено)
Шаблон:Navbox (переглянути вихідний код) (захищено)
Шаблон:Reflist (переглянути вихідний код) (захищено)
Шаблон:Reflist/styles.css (переглянути вихідний код) (захищено)
Шаблон:Алгоритми теорії чисел (редагувати)
Шаблон:Вступ до алгоритмів (редагувати)
Шаблон:Не перекладено (переглянути вихідний код) (захищено)
Модуль:Arguments (переглянути вихідний код) (захищено)
Модуль:Check for unknown parameters (переглянути вихідний код) (захищено)
Модуль:Citation/CS1 (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/COinS (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Configuration (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Identifiers (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Utilities (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Whitelist (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/styles.css (переглянути вихідний код) (захищено)
Модуль:Navbar (переглянути вихідний код) (захищено)
Модуль:Navbar/configuration (переглянути вихідний код) (захищено)
Модуль:Navbar/styles.css (переглянути вихідний код) (захищено)
Модуль:Navbox (переглянути вихідний код) (захищено)
Модуль:Navbox/configuration (переглянути вихідний код) (захищено)
Модуль:Navbox/styles.css (переглянути вихідний код) (захищено)
Модуль:TableTools (переглянути вихідний код) (захищено)
Модуль:Не перекладено (переглянути вихідний код) (захищено)

Повернення до сторінки «Тест простоти Міллера — Рабіна».

Отримано з https://uk.wikipedia.org/wiki/Тест_простоти_Міллера_—_Рабіна