Тест на простоту Поклінґтона (англ. Pocklington–Lehmer primality test) — тест на простоту розроблений Генрі Кабурн Поклінґтоном і Деріком Генрі Лемером для визначення чи є число простим. На виході тесту або доведення простоти, або неможливість доведення.
Лема
Нехай Якщо для кожного простого дільника для існує ціле таке, що
тоді — просте.
Позначення: означає, що ділить
Доведення: Для того, щоб показати, що просте нам потрібно лише показати, що або простіше, що Припустимо це не так, тоді існує просте і показник такий, що але не ділить Для цього цілого ми маємо мати ціле, що задовольняє попереднім умовам. Тепер нехай буде порядком за модулем тоді (перша умова), але не ділить (друга умова). Отже ділить яке ділить — протиріччя, яке доводить лему.
Теорема Поклінґтона
Теорема Поклінґтона (англ. Pocklington's Theorem) (1914): Нехай де — просте, яке не ділить Якщо існує ціле таке, що і тоді кожен простий дільник для має вигляд
Доведення: Нехай — довільний простий дільник і нехай буде порядком за модулем Як і в лемі, (перша умова для але не ділить (друга умова); отже Звісно, і звідси висновок.
Вислід
Вислідом застосування теореми Поклінґтона до кожного простого степеневого дільника (плюс трошки роботи) є:
Теорема: Припустимо, що (тобто ), де і відома факторизація . Якщо існує ціле що задовольняє:
- для кожного
тоді кожен простий дільник для конгруентний за модулем З цього випливає, що якщо тоді є простим.
Кількість перевірок
Нехай буде непарним простим з і І нехай різними простими дільниками для будуть Тоді ймовірність, що випадково обрана база задовольняє обом умовам: і для кожного становить
Отже, якщо відома факторизація дільника тоді для перевірки на простоту, можна просто обирати випадкові цілі в інтервалі доки на знайдеться таке, що задовольняє умовам 1 і 2, тобто просте. Якщо таке не знайшли після розумної кількості ітерацій, тоді імовірно складене і це можна перевірити через застосування ймовірнісного тесту на простоту.
Примітки
- За кількість ітерацій можна взяти де і де
Джерела
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Test na prostotu Poklingtona angl Pocklington Lehmer primality test test na prostotu rozroblenij Genri Kaburn Poklingtonom i Derikom Genri Lemerom dlya viznachennya chi ye chislo n displaystyle n prostim Na vihodi testu abo dovedennya prostoti abo nemozhlivist dovedennya LemaNehaj n gt 1 displaystyle n gt 1 Yaksho dlya kozhnogo prostogo dilnika q displaystyle q dlya n 1 displaystyle n 1 isnuye cile take sho a n 1 1 mod n displaystyle a n 1 equiv 1 pmod n a n 1 q 1 mod n displaystyle a n 1 q not equiv 1 pmod n todi n displaystyle n proste Poznachennya a b displaystyle a b oznachaye sho a displaystyle a dilit b displaystyle b Dovedennya Dlya togo shob pokazati sho n displaystyle n proste nam potribno lishe pokazati sho ϕ n n 1 displaystyle phi n n 1 abo prostishe sho n 1 ϕ n displaystyle n 1 phi n Pripustimo ce ne tak todi isnuye proste q displaystyle q i pokaznik r gt 0 displaystyle r gt 0 takij sho q r n 1 displaystyle q r n 1 ale ne dilit ϕ n displaystyle phi n Dlya cogo cilogo q displaystyle q mi mayemo mati cile sho zadovolnyaye poperednim umovam Teper nehaj m displaystyle m bude poryadkom a displaystyle a za modulem n displaystyle n todi m n 1 displaystyle m n 1 persha umova ale ne dilit n 1 q displaystyle n 1 q druga umova Otzhe q r displaystyle q r dilit m displaystyle m yake dilit ϕ n displaystyle phi n protirichchya yake dovodit lemu Teorema PoklingtonaTeorema Poklingtona angl Pocklington s Theorem 1914 Nehaj n 1 q k R displaystyle n 1 q k R de q displaystyle q proste yake ne dilit R displaystyle R Yaksho isnuye cile take sho a n 1 1 mod n displaystyle a n 1 equiv 1 pmod n i gcd a n 1 q 1 n 1 displaystyle gcd a n 1 q 1 n 1 todi kozhen prostij dilnik p displaystyle p dlya n displaystyle n maye viglyad q k r 1 displaystyle q k r 1 Dovedennya Nehaj p displaystyle p dovilnij prostij dilnik n displaystyle n i nehaj m displaystyle m bude poryadkom a displaystyle a za modulem p displaystyle p Yak i v lemi m n 1 q k R displaystyle m n 1 q k R persha umova dlya a displaystyle a ale ne dilit n 1 q q k 1 R displaystyle n 1 q q k 1 R druga umova otzhe q k m displaystyle q k m Zvisno m p 1 displaystyle m p 1 i zvidsi visnovok Vislid Vislidom zastosuvannya teoremi Poklingtona do kozhnogo prostogo stepenevogo dilnika n displaystyle n plyus troshki roboti ye Teorema Pripustimo sho n 1 F R displaystyle n 1 F times R tobto F n 1 displaystyle F n 1 de F gt R displaystyle F gt R gcd F R 1 displaystyle gcd F R 1 i vidoma faktorizaciya F j 1 t q j e j displaystyle F prod j 1 t q j e j Yaksho isnuye cile a displaystyle a sho zadovolnyaye a n 1 1 mod n displaystyle a n 1 equiv 1 pmod n gcd a n 1 q j 1 n 1 displaystyle gcd a n 1 q j 1 n 1 dlya kozhnogo j 1 j t displaystyle j 1 leq j leq t todi kozhen prostij dilnik p displaystyle p dlya n displaystyle n kongruentnij 1 displaystyle 1 za modulem F displaystyle F Z cogo viplivaye sho yaksho F gt n 1 displaystyle F gt sqrt n 1 todi n displaystyle n ye prostim Kilkist perevirokNehaj n R F 1 displaystyle n RF 1 bude neparnim prostim z F gt n 1 displaystyle F gt sqrt n 1 i gcd R F 1 displaystyle gcd R F 1 I nehaj riznimi prostimi dilnikami dlya F displaystyle F budut q 1 q 2 q t displaystyle q 1 q 2 dots q t Todi jmovirnist sho vipadkovo obrana baza a displaystyle a 1 a n 1 displaystyle 1 leq a leq n 1 zadovolnyaye obom umovam a n 1 mod n displaystyle a n 1 equiv pmod n i gcd a n 1 q j 1 n 1 displaystyle gcd a n 1 q j 1 n 1 dlya kozhnogo j displaystyle j 1 j t displaystyle 1 leq j leq t stanovit j 1 t 1 1 q j 1 j 1 t 1 q j displaystyle prod j 1 t 1 1 q j geq 1 sum j 1 t 1 q j Otzhe yaksho vidoma faktorizaciya dilnika F gt n 1 displaystyle F gt sqrt n 1 todi dlya perevirki na prostotu mozhna prosto obirati vipadkovi cili v intervali 2 n 2 displaystyle 2 n 2 doki na znajdetsya take sho zadovolnyaye umovam 1 i 2 tobto n displaystyle n proste Yaksho take a displaystyle a ne znajshli pislya rozumnoyi kilkosti iteracij todi n displaystyle n imovirno skladene i ce mozhna pereviriti cherez zastosuvannya jmovirnisnogo testu na prostotu PrimitkiZa kilkist iteracij mozhna vzyati T displaystyle T de P T 1 2 100 displaystyle P T leq left frac 1 2 right 100 i de P 1 j 1 t 1 1 q j displaystyle P 1 prod j 1 t 1 1 q j DzherelaFinding primes amp proving primality angl 1997 Prime Number Issues PDF Handbook of Applied Cryptography CRC Press s 143 144 ISBN 0 8493 8523 7