www.wikidata.uk-ua.nina.az

Тест простоти Міллера Рабіна або тест Міллера Рабіна це тест простоти алгоритм який визначає чи є надане число простим Й

Тест простоти Міллера — Рабіна

Тест простоти Міллера — Рабіна або тест Міллера – Рабіна — це тест простоти: алгоритм, який визначає чи є надане число простим. Його початкова версія, яку розробив професор Міллер, є детерміністичною, але детермінізм покладається на недоведену узагальнену гіпотезу Рімана; Міхаель Рабін змінив її, щоб отримати безумовний імовірнісний алгоритм.

Вступ Редагувати

Для багатьох застосувань, як-от криптографія, ми потребуємо великих випадкових простих чисел. На щастя, великі прості не такі вже й рідкісні, тому можливо перевіряти цілі потрібного розміру, щоб знайти серед них просте. Функція розподілу простих чисел визначає кількість простих чисел, які менші ніж . Наприклад, Відомо, що

Це досить якісне наближена оцінка для З цього ми маємо, що ймовірність того, що є простим дорівнює . Геометричний розподіл підказує нам, що очікувана кількість спроб для знаходження простого числа становить . Також ми, звісно, можемо опустити парні числа, що зменшує кількість спроб удвічі.

Наївним способом перевірки чи число просте був би повний перебір можливих дільників. Тобто для числа потрібно було б перебрати . Знов-таки, ми можемо пропускати парні числа більші ніж двійка. Якщо вважати, що кожне пробне ділення потребує однаково часу, то складність буде , така складність є експоненційною для . Алгоритми з такою складністю, зазвичай вважають повільними. Хоча у такого алгоритму є й перевага, він знаходить дільники , тобто розкладає число.

Ймовірнісні тести простоти Редагувати

Найвідомішими ймовірнісними тестами простоти є тест Соловея — Штрассена і тест Міллера — Рабіна. В обох випадках базова процедура та сама: ми визначаємо множину свідків того, що є складеним. Якщо ми можемо знайти тоді і є складеним числом. У випадку тесту Міллера — Рабіна

Оцінка кількості свідків Редагувати

Нехай буде непарним числом і нехай з непарним Припустимо, що просте. Тоді квадратними коренями з будуть лише тобто єдиними розв'язками за модулем 2. Більше того, для кожного яке просте з Отже,

Ми бачимо: якщо є простим, тоді для кожного за умови, що або або існує з Зворотнє твердження також істинне, тобто, якщо є складеним, тоді існує з таке що і для І точніше:

Теорема: Нехай буде складеним непарним числом. Нехай з непарним Нехай

Тоді

Порівняння з тестом Соловея—Штрассена Редагувати

Тест Міллера — Рабіна буде кращим вибором:

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

Псевдокод Редагувати

МІЛЛЕР-РАБІН

  1. якщо парне тоді
  2.  повернути ХИБА
  4. поки парне
  5.  
  6. для до
  7.  
  8.  
  9.  якщо тоді
  10.   
  11.    поки і
  12.     
  13.    якщо тоді
  14.     повернути ХИБА
  15. повернути ІСТИНА

Імовірність помилки

Див. також Редагувати

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

  1. Гарі Міллер (1976). Ріманова гіпотеза і тест на простоту. Journal of Computer and System Sciences 13 (3): 300–317. doi:10.1145/800116.803773. 
  2. Міхаель Рабін (1980). Ймовірнісний алгоритм для перевірки простоти. Journal of Number Theory 12 (1): 128–138. doi:10.1016/0022-314X(80)90084-0. 

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

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Test prostoti Millera Rabina abo test Millera Rabina ce test prostoti algoritm yakij viznachaye chi ye nadane chislo prostim Jogo pochatkova versiya yaku rozrobiv profesor Miller ye deterministichnoyu ale determinizm pokladayetsya na nedovedenu uzagalnenu gipotezu Rimana 1 Mihael Rabin zminiv yiyi shob otrimati bezumovnij imovirnisnij algoritm 2 Zmist 1 Vstup 2 Jmovirnisni testi prostoti 2 1 Ocinka kilkosti svidkiv 2 2 Porivnyannya z testom Soloveya Shtrassena 3 Psevdokod 4 Div takozh 5 Primitki 6 DzherelaVstup RedaguvatiDlya bagatoh zastosuvan yak ot kriptografiya mi potrebuyemo velikih vipadkovih prostih chisel Na shastya veliki prosti ne taki vzhe j ridkisni tomu mozhlivo pereviryati cili potribnogo rozmiru shob znajti sered nih proste Funkciya rozpodilu prostih chisel p n displaystyle pi n nbsp viznachaye kilkist prostih chisel yaki menshi nizh n displaystyle n nbsp Napriklad p 10 4 displaystyle pi 10 4 nbsp Vidomo sho lim n p n n lg n 1 displaystyle lim n to infty frac pi n n lg n 1 nbsp Ce dosit yakisne nablizhena ocinka dlya p n displaystyle pi n nbsp Z cogo mi mayemo sho jmovirnist togo sho n displaystyle n nbsp ye prostim dorivnyuye 1 lg n displaystyle 1 lg n nbsp Geometrichnij rozpodil pidkazuye nam sho ochikuvana kilkist sprob dlya znahodzhennya prostogo chisla stanovit lg n displaystyle lg n nbsp Takozh mi zvisno mozhemo opustiti parni chisla sho zmenshuye kilkist sprob udvichi Nayivnim sposobom perevirki chi chislo proste buv bi povnij perebir mozhlivih dilnikiv Tobto dlya chisla n displaystyle n nbsp potribno bulo b perebrati 2 3 n displaystyle 2 3 dots lfloor sqrt n rfloor nbsp Znov taki mi mozhemo propuskati parni chisla bilshi nizh dvijka Yaksho vvazhati sho kozhne probne dilennya potrebuye odnakovo chasu to skladnist bude O n displaystyle O sqrt n nbsp taka skladnist ye eksponencijnoyu dlya n displaystyle n nbsp Algoritmi z takoyu skladnistyu zazvichaj vvazhayut povilnimi Hocha u takogo algoritmu ye j perevaga vin znahodit dilniki n displaystyle n nbsp tobto rozkladaye chislo Jmovirnisni testi prostoti RedaguvatiNajvidomishimi jmovirnisnimi testami prostoti ye test Soloveya Shtrassena i test Millera Rabina V oboh vipadkah bazova procedura ta sama mi viznachayemo mnozhinu W displaystyle W nbsp svidkiv togo sho n displaystyle n nbsp ye skladenim Yaksho mi mozhemo znajti w W displaystyle w in W nbsp todi W displaystyle W neq emptyset nbsp i n displaystyle n nbsp ye skladenim chislom U vipadku testu Millera Rabina W W n displaystyle W overline W n nbsp Ocinka kilkosti svidkiv Redaguvati Nehaj n N displaystyle n in mathbb N nbsp bude neparnim chislom i nehaj n 1 2 t m displaystyle n 1 2 t m nbsp z neparnim m displaystyle m nbsp Pripustimo sho n displaystyle n nbsp proste Todi kvadratnimi korenyami z 1 displaystyle 1 nbsp budut lishe 1 displaystyle pm 1 nbsp tobto yedinimi rozv yazkami x 2 1 displaystyle x 2 1 nbsp za modulem 2 Bilshe togo a n 1 1 mod n displaystyle a n 1 equiv 1 mod n nbsp dlya kozhnogo a N displaystyle a in mathbb N nbsp yake proste z n displaystyle n nbsp Otzhe a n 1 1 mod n displaystyle a n 1 equiv 1 mod n nbsp i a n 1 2 1 mod n displaystyle a n 1 2 equiv pm 1 mod n nbsp i yaksho a n 1 2 1 mod n displaystyle a n 1 2 equiv 1 mod n nbsp todi a n 1 4 1 mod n displaystyle a n 1 4 equiv pm 1 mod n nbsp i yaksho a n 1 4 1 mod n displaystyle a n 1 4 equiv 1 mod n nbsp todi displaystyle dots nbsp Mi bachimo yaksho n displaystyle n nbsp ye prostim todi dlya kozhnogo a N displaystyle a in mathbb N nbsp za umovi sho gcd a n 1 displaystyle gcd a n 1 nbsp abo a m 1 mod n displaystyle a m equiv 1 mod n nbsp abo isnuye j 0 t 1 displaystyle j in 0 dots t 1 nbsp z a 2 j m 1 mod n displaystyle a 2 j m equiv 1 mod n nbsp Zvorotnye tverdzhennya takozh istinne tobto yaksho n displaystyle n nbsp ye skladenim todi isnuye a N displaystyle a in mathbb N nbsp z gcd a n 1 displaystyle gcd a n 1 nbsp take sho a m 1 mod n displaystyle a m not equiv 1 mod n nbsp i a 2 j m 1 mod n displaystyle a 2 j m not equiv 1 mod n nbsp dlya 0 j t 1 displaystyle 0 leq j leq t 1 nbsp I tochnishe Teorema Nehaj n N displaystyle n in mathbb N nbsp bude skladenim neparnim chislom Nehaj n 1 2 t m displaystyle n 1 2 t m nbsp z neparnim m displaystyle m nbsp Nehaj W n a Z n a m 1 mod n a 2 j m 1 mod n 0 j t 1 displaystyle overline W n a in mathbb Z n a m not equiv 1 mod n a 2 j m not equiv 1 mod n 0 leq j leq t 1 nbsp Todi W n f n 2 displaystyle overline W n geq varphi n 2 nbsp Porivnyannya z testom Soloveya Shtrassena Redaguvati Test Millera Rabina bude krashim viborom Legshe obchisliti testovi umovi Svidok dlya testu Soloveya Shtrassena takozh svidok dlya testu Millera Rabina U testi Millera Rabina jmovirnist natrapiti na svidka za odnu vipadkovu sprobu bilsha nizh 3 4 a u testi Soloveya Shtrassena 1 2 Psevdokod RedaguvatiMILLER RABIN n k displaystyle n k nbsp yaksho n displaystyle n nbsp parne todi povernuti HIBA m n 1 div 2 t 1 displaystyle m gets n 1 mbox div 2 t gets 1 nbsp poki m displaystyle m nbsp parne m m div 2 t t 1 displaystyle m gets m mbox div 2 t gets t 1 nbsp dlya i 1 displaystyle i gets 1 nbsp do k displaystyle k nbsp a R a n d o m mod n displaystyle a gets Random mod n nbsp u a m mod n displaystyle u gets a m mod n nbsp yaksho u 1 displaystyle u neq 1 nbsp todi j 1 displaystyle j gets 1 nbsp poki u 1 displaystyle u neq 1 nbsp i j lt t displaystyle j lt t nbsp u u 2 mod n j j 1 displaystyle u gets u 2 mod n j gets j 1 nbsp yaksho u 1 displaystyle u neq 1 nbsp todi povernuti HIBA povernuti ISTINAImovirnist pomilki 1 4 k displaystyle leq 1 4 k nbsp Div takozh RedaguvatiTest Soloveya ShtrassenaPrimitki Redaguvati Gari Miller 1976 Rimanova gipoteza i test na prostotu Journal of Computer and System Sciences 13 3 300 317 doi 10 1145 800116 803773 Mihael Rabin 1980 Jmovirnisnij algoritm dlya perevirki prostoti Journal of Number Theory 12 1 128 138 doi 10 1016 0022 314X 80 90084 0 Dzherela RedaguvatiTomas Kormen Charlz Lejzerson Ronald Rivest Kliford Stajn 2009 1990 31 Primarily Testing Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill s 965 975 ISBN 0 262 03384 4 Hans Delfs Helmut Knebl A 8 Primes and Primality Tests Introduction to Cryptography Principles and Applications vid 2 Springer s 319 324 ISBN 978 3 540 49243 6 Otrimano z https uk wikipedia org w index php title Test prostoti Millera Rabina amp oldid 36610998