Бастапқы тест - Primality test

A бастапқы тест болып табылады алгоритм кіріс нөмірінің бар-жоғын анықтау үшін қарапайым. Басқа өрістерінің арасында математика, ол үшін қолданылады криптография. Айырмашылығы жоқ бүтін факторлау, бірінші кезектегі тесттер бермейді қарапайым факторлар, тек кіріс санының жай немесе жоқ екендігін көрсететін. Факторизация есептеу қиын мәселе деп саналады, ал бастапқы тестілеу салыстырмалы түрде оңай (оның жүгіру уақыты болып табылады көпмүшелік кіріс өлшемінде). Кейбір бастапқы тесттер дәлелдеу бұл сан жай, ал басқалары ұнатады Миллер – Рабин сан екенін дәлелдеңіз құрама. Сондықтан соңғысын дәлірек атауға болады композиттілік сынақтары бастапқы тестілердің орнына.

Қарапайым әдістер

Қарапайым қарапайым тест сынақ бөлімі: кіріс нөмірі берілген, n, оның біркелкі екенін тексеріңіз бөлінетін кез келген жай сан 2 мен √n (яғни бөлу жоқ деп қалдырады қалдық ). Егер солай болса, онда n болып табылады құрама. Әйтпесе, солай қарапайым.[1]

Мысалы, мына сандарға біркелкі бөлінетін 100 санын қарастырайық:

2, 4, 5, 10, 20, 25, 50

Ең үлкен коэффициент - 50 100-дің жартысына тең екенін ескеріңіз n: барлық бөлгіштерден кіші немесе тең n / 2.

Шындығында, біз барлық мүмкін бөлгіштерді тексергенде n / 2, біз кейбір факторларды табамыз екі рет. Мұны сақтау үшін бөлгіштердің тізімін өнімнің тізімі ретінде қайта жазыңыз, әрқайсысы 100-ге тең:

2 × 50,   4 × 25,   5 × 20,   10 × 10,   20 × 5,   25 × 4,   50 × 2

Өнімдердің өткеніне назар аударыңыз 10 x 10 тек алдыңғы өнімдерде пайда болған сандарды қайталау. Мысалға, 5 x 20 және 20 x 5 бірдей сандардан тұрады. Бұл бәріне қатысты nбарлық бөлгіштері n кем немесе тең сандар болып табылады √n, сондықтан бізге өткенді іздеудің қажеті жоқ.[1] (Бұл мысалда, √n = √100 = 10.)

2-ден үлкен барлық жұп сандарды да жоюға болады, өйткені егер жұп санды бөлуге болады n2. солай бола алады.

17-дің басымдылығын тексеру үшін сынақтық бөлуді қолданайық. Бізге тек бөлгіштерге арналған тест қажет √n, яғни бүтін сандар аз немесе оған тең , атап айтқанда, 2, 3 және 4. Біз 4-тен өткізіп жібере аламыз, себебі бұл жұп сан: егер 4-ті 17-ге тең бөлуге болатын болса, 2-ге тең, ал 2 тізімде бұрыннан бар. Бұл 2 мен 3-ті қалдырады. Біз 17-ді осы сандардың әрқайсысына бөлеміз және 17-ді біркелкі бөлмейтіндігімізді анықтаймыз - екі бөлім де қалдық қалдырады. Сонымен, 17 - ең жақсы.

Біз бұл әдісті одан әрі жетілдіре аламыз. 3-тен үлкен барлық жай бөлшектер формада болатынына назар аударыңыз 6к ± 1, қайда к - бұл 0-ден үлкен кез келген бүтін сан. Бұл барлық бүтін сандарды келесі түрінде көрсетуге болатындығына байланысты (6к + мен), қайда мен = -1, 0, 1, 2, 3 немесе 4. 2-ге бөлінетінін ескеріңіз (6к + 0), (6к + 2) және (6к + 4) және 3 бөлу (6к + 3). Сонымен, неғұрлым тиімді әдіс - бұл тексеру n 2 немесе 3-ке бөлінеді, содан кейін форманың барлық сандарын тексеру керек . Бұл барлық сандарды тексеруден 3 есе жылдам √n.

Бұдан әрі жалпылай отырып, барлық жай бөлшектер одан үлкен c# (c бастапқы ) формада болады c# · k + i, үшін мен < c#, қайда c және к бүтін сандар және мен сандарды білдіреді коприм дейін с #. Мысалы, рұқсат етіңіз c = 6. Содан кейін c# = 2 · 3 · 5  = 30. Барлық бүтін сандар формада болады 30к + мен үшін мен = 0, 1, 2,...,29 және к бүтін сан. Алайда, 2 0, 2, 4, ..., 28 бөледі; 3 0, 3, 6, ..., 27 бөледі; және 5 0, 5, 10, ..., 25-ті бөледі. Демек, 30-дан үлкен барлық жай сандар формада болады 30к + мен үшін мен = 1, 7, 11, 13, 17, 19, 23, 29 (яғни. үшін мен < 30 осындай gcd (мен,30) = 1). Егер болса мен және 30-ы көшірме емес болатын 30к + мен 30-ға, яғни 2-ге, 3-ке немесе 5-ке бөлінгішке бөлінеді, сондықтан да жай болмайды. (Ескерту: жоғарыда көрсетілген шарттарға сәйкес келетін барлық сандар жай емес. Мысалы: 437 c # (c) үшін с # k + i түрінде болады (7) = 210, k = 2, i = 17. Алайда, 437 - бұл құрама саны 19 * 23-ке тең).

Қалай c → ∞, бұл мәндер саны c#к + мен қабылдай алады, белгілі бір диапазон азаяды, демек тестілеу уақыты n төмендейді. Бұл әдіс үшін барлық кіші жай бөлшектерге бөлінгіштікті тексеру қажет c. Алдыңғыға ұқсас бақылауларды қолдануға болады рекурсивті, беру Эратосфен елегі.

Осы әдістерді жылдамдатудың жақсы әдісі (және басқаларында төменде айтылған) алдын ала есептеу және белгілі бір шекке дейінгі барлық жай бөлшектердің тізімін сақтау, дейді 200-ге дейінгі барлық жай бөлшектер. (Мұндай тізімді есептеуге болады Эратосфен елегі немесе әрбір өсімді тексеретін алгоритм бойынша м барлық белгілі жай бөлшектерге қарсы < √м). Содан кейін, тестілеуден бұрын n байыпты әдіспен басымдық үшін, n алдымен тізімдегі кез-келген қарапайымға бөлінгіштігін тексеруге болады. Егер ол осы сандардың кез-келгеніне бөлінетін болса, онда ол құрама болып табылады және кез-келген басқа сынақтарды өткізіп жіберуге болады.

Қарапайым, бірақ өте тиімді емес тестілеуді қолданады Уилсон теоремасы, онда көрсетілген б егер ол келесі жағдайда ғана қарапайым:

Бұл әдіс шамамен қажет болғанымен б модульдік көбейту, оны практикалық емес етіп, жай және модульдік қалдықтар туралы теоремалар көптеген практикалық әдістердің негізін құрайды.

Python коды

Келесі қарапайым қарапайым тест болып табылады Python коды қарапайымды қолдану 6к ± 1 бұрын айтылған оңтайландыру. Төменде сипатталған күрделі әдістер үлкендер үшін әлдеқайда жылдам n.

деф is_prime(n: int) -> bool:    «» «6k + -1 оңтайландыруды қолданатын басымдық тесті.» «»    егер n <= 3:        қайту n > 1    егер n % 2 == 0 немесе n % 3 == 0:        қайту Жалған    мен = 5    уақыт мен ** 2 <= n:        егер n % мен == 0 немесе n % (мен + 2) == 0:            қайту Жалған        мен += 6    қайту Рас

Эвристикалық тесттер

Бұл практикада жақсы жұмыс істейтін сияқты, бірақ дәлелденбеген, сондықтан техникалық тұрғыдан алгоритм емес тесттер, Ферма тесті және Фибоначчи тесті қарапайым мысалдар, және олар өте біріктірілген кезде тиімді. Джон Селридж егер болса деп болжайды б тақ сан, және б ≡ ± 2 (мод 5), содан кейін б келесі екі жағдайда да қарапайым болады:

  • 2б−1 ≡ 1 (мод б),
  • fб+1 ≡ 0 (мод б),

қайда fк болып табылады к-шы Фибоначчи нөмірі. Бірінші шарт - 2-негізді қолдана отырып, Ферма примиталдылығын тексеру.

Жалпы, егер б ≡ a (мод х2+4), қайда а квадраттық қалдық емес (мод х2+4) содан кейін б егер келесі шарттар сақталса, жай болуы керек:

  • 2б−1 ≡ 1 (мод б),
  • f(х)б+1 ≡ 0 (мод б),

f(х)к болып табылады к-шы Фибоначчи көпмүшесі кезінде х.

Селидж, Карл Померанс, және Сэмюэль Вагстафф бірге қарсы мысал үшін $ 620 ұсынады. Мәселе 2015 жылдың 11 қыркүйегіне дейін әлі де ашық.[2]

Ықтималдық тестілері

Ықтималдық тестілері Эвристикадан гөрі қатал, өйткені олар құрама санмен алдану ықтималдылығының дәлелденетін шектерін ұсынады.Примиталды тестілердің көпшілігі - ықтималдық тестілері. Бұл сынақтар тестіленген саннан бөлек қолданылады n, басқа сандар а кейбіреулерінен кездейсоқ таңдалады үлгі кеңістігі; әдеттегі кездейсоқ рандомизацияланған бастапқы сынаулар ешқашан қарапайым санды құрама деп есептемейді, бірақ құрама санды жай деп айтуға болады. Қате ықтималдығын тестті бірнеше тәуелсіз таңдалған мәндермен қайталау арқылы азайтуға болады а; үшін жиі қолданылатын екі тест үшін кез келген құрама n кем дегенде жартысы а'лар анықтайды n'композиттілік, сондықтан к қайталанулар қате ықтималдығын ең көбі 2-ге дейін төмендетеді−к, оны ұлғайту арқылы ерікті түрде жасауға болады к.

Рандомизирленген алғашқы тестілердің негізгі құрылымы келесідей:

  1. Кездейсоқ нөмірді таңдаңыз а.
  2. Қандай да бір теңдікті тексеріңіз (таңдалған тестке сәйкес) а және берілген сан n. Егер теңдік орындала алмаса, онда n құрама сан, а а ретінде белгілі куәгер композиттілік үшін, және тест тоқтайды.
  3. 1-қадамнан бастап қажетті дәлдікке жеткенше қайталаңыз.

Бір немесе бірнеше қайталаудан кейін, егер n құрама сан деп табылған жоқ, содан кейін оны жариялауға болады мүмкін премьер.

Фермаға алғашқы тест

Қарапайым ықтималдылық сынағы - бұл Фермаға алғашқы тест (іс жүзінде композиттілік сынағы). Ол келесідей жұмыс істейді:

Бүтін сан берілген n, бүтін санды таңдаңыз а коприм n және есептеңіз аn − 1 модуль n. Егер нәтиже 1-ден өзгеше болса, онда n құрама болып табылады. Егер ол 1 болса, онда n ең жақсы болуы мүмкін.

Егер аn−1 (модуль n) 1 бірақ n ол жай емес n а деп аталадыпсевдоприм негіздеу а. Іс жүзінде біз мұны байқаймыз, егераn−1 (модуль n) 1 болса, онда n әдетте қарапайым. Бірақ мұнда қарсы мысал келтірілген: егер n = 341 және а = 2, онда

341 = 11 · 31 құрама болса да. Шын мәнінде, 341 - бұл ең кіші псевдопримдік негіз 2 (1-суретті қараңыз)[3]).

Тек 2,5-ке жетпейтін 21853 псевдоприм 2 негізі бар×1010 (1005 бетті қараңыз) [3]). Бұл дегеніміз, үшін n 2,5-ке дейін×1010, егер 2n−1 (модуль n) 1-ге тең, сонда n қарапайым, егер болмаса n осы 21853 жалған режимнің бірі болып табылады.

Кейбір құрама сандар (Кармайкл сандары ) меншігіне ие аn − 1 1-ге тең (модуль n) әрқайсысы үшін а бұл коприм n. Ең кішкентай мысал n = 561 = 3 · 11 · 17, ол үшін а560 барлығына 1 (модуль 561) құрайды а Сонымен қатар, Ферма тесті сандарды тез скринингтен өткізу қажет болған жағдайда жиі қолданылады, мысалы, RSA ашық кілтінің криптографиялық алгоритмі.

Миллер – Рабин және Соловай – Страссенге арналған бастапқы тест

The Миллер-Рабинге қатысты тест және Соловай – Страссенге арналған бастапқы тест барлық композиттерді анықтайтын күрделі нұсқалар (бұл тағы бір рет: әрқайсысы құрама нөмір n, кемінде 3/4 (Миллер-Рабин) немесе 1/2 (Соловай-Страссен) сандар а композиттілігінің куәгерлері болып табылады n). Бұл сондай-ақ композиттілік сынағы.

Миллер-Рабинді бағалаудың тесті келесідей жұмыс істейді: бүтін сан берілген n, оң бүтін санды таңдаңыз а < n. 2 болсынсг. = n - 1, қайда г. тақ. Егер

және

барлығына

содан кейін n құрама және а композиттіліктің куәсі болып табылады. Әйтпесе, n Миллер-Рабин сынағы - бұл а күшті псевдоприм тест (PSW қараңыз)[3] 1004 бет).

Соловай-Страссенге арналған басымдылық тесті тағы бір теңдікті қолданады: тақ сан берілген n, бүтін санды таңдаңыз а < n, егер

, қайда болып табылады Якоби символы,

содан кейін n құрама және а композиттіліктің куәсі болып табылады. Әйтпесе, n Соловай-Страссен сынағы Эйлер псевдопримиясы тест (PSW қараңыз)[3] 1003 бет).

Әрбір жеке мәні үшін а, Соловай-Страссен тесті Миллер-Рабинге қарағанда әлсіз. Мысалы, егер n = 1905 ж а = 2, демек, Миллер-Рабин тесті мұны көрсетеді n композиттік болып табылады, бірақ Соловай-Страссен тесті жоқ. Себебі 1905 Эйлерпсевдоприм негізі 2 болып табылады, бірақ күшті псевдоприм негізі 2 емес (бұл PSW 1-суретте көрсетілген)[3]).

Фробениустың бастапқы тесті

Миллер-Рабин және Соловай-Страссен сынақтары қарапайым және басқа жалпы бастапқы тесттерге қарағанда жылдамырақ. Кейбір жағдайларда тиімділікті арттырудың бір әдісі - бұл Фробениустың псевдопрималитетіне тест; бұл тесттің айналымы Миллер-Рабиннің айналымынан шамамен үш есе көп уақытты алады, бірақ Миллер-Рабиннің жеті айналымымен салыстырылатын ықтималдылыққа жетеді.

Фробениус тесті - бұл жалпылау Лукас псевдоприм тест.

Baillie-PSW бастапқы сынағы

The Baillie - PSW-тің алғашқы сынағы - бұл Ферма немесе Миллер-Рабин тестін а-мен біріктіретін ықтималдықтың бастапқы сынағы Лукас ықтимал премьер белгілі қарама-қарсы мысалдары жоқ бірінші дәрежелі тест алу үшін тест. Яғни, белгілі композит жоқ n ол үшін бұл тест хабарлайды n мүмкін ең жақсы.[4] Қарсы мысалдар жоқ екендігі көрсетілген n .

Басқа тесттер

Леонард Адлеман және Мин-Де Хуанг қатесіз (бірақ күткен көпмүшелік уақыт) нұсқасын ұсынды эллиптикалық қисықтың бастапқы сынағы. Басқа ықтимал тестілерден айырмашылығы, бұл алгоритм а негізгі сертификат, осылайша санның жай екенін дәлелдеу үшін қолдануға болады.[5] Алгоритм іс жүзінде өте баяу.

Егер кванттық компьютерлер қол жетімді болды, бірінші кезектілікті тексеруге болатын еді асимптотикалық жылдамырақ классикалық компьютерлерді пайдаланудан гөрі. Комбинациясы Шор алгоритмі, бүтін санды факторизация әдісі Поклингтонның бастапқы сынағы мәселені шешуі мүмкін .[6]

Жылдам детерминирленген тесттер

20-шы ғасырдың басында, деп қорытындыланды Ферманың кішкентай теоремасы примиталдылығын тексеру үшін қолданылуы мүмкін.[7] Нәтижесінде Поклингтонның бастапқы сынағы.[8] Алайда, бұл тест ішінара қажет болғандықтан факторизация туралы n - 1 ең нашар жағдайда жұмыс уақыты баяу болды. Бірінші детерминистік аңғалдық әдістеріне қарағанда тезірек тестілеу циклотомия сынағы; оның жұмыс уақыты дәлелдеуге болады O ((журналn)c журнал журналыn), қайда n - бұл басымдылықты тексеретін және c тұрақты тәуелді болып табылады n. Көптеген жақсартулар жасалды, бірақ олардың ешқайсысында полиномдық жұмыс уақыты бар екендігі дәлелденбеді. (Жұмыс уақыты кірістің өлшемімен өлшенетінін ескеріңіз, бұл жағдайда ~ log боладыn, бұл санды көрсету үшін қажет бит саны n.) эллиптикалық қисықтың бастапқы сынағы O-да жұмыс істейтінін дәлелдеуге болады ((журналn)6), егер кейбір болжамдар болса аналитикалық сандар теориясы шындық[қайсы? ] Сол сияқты, астында жалпыланған Риман гипотезасы, детерминистік Миллердің сынағы Миллер-Рабин ықтималдық тестінің негізін құрайтын дәлелдеуге болады Õ ((журналn)4).[9] Іс жүзінде бұл алгоритм мүлдем қарауға болатын сандардың өлшемдері үшін қалған екеуіне қарағанда баяу. Осы екі әдісті іске асыру өте қиын болғандықтан және бағдарламалау қателіктеріне қауіп төндіретіндіктен, баяу, бірақ қарапайым тестілерге басымдық беріледі.

2002 жылы бірінші дәрежелі сөзсіз детерминирленген детерминирленген көпмүшелік уақыт сынағы ойлап тапты Manindra Agrawal, Неерадж Каял, және Нитин Саксена. The AKS-тің бастапқы сынағы Õ ішінде жұмыс істейді ((журналn)12) (improved дейін жақсартылған ((журнал.)n)7.5)[10] олардың қағазының жарияланған редакциясында), оны одан әрі Õ дейін төмендетуге болады ((лог.)n)6) егер Софи Жерменнің болжамдары шындық[11] Кейіннен Ленстра мен Померанс тесттің in уақытында өтетін нұсқасын ұсынды ((лог.)n)6) сөзсіз.[12]

Agrawal, Kayal және Saxena олардың алгоритмінің Õ ((лог.)n)3) егер Агровалдың болжамдары шындық; дегенмен, Хендрик Ленстра мен Карл Померанстың эвристикалық аргументі оның жалған болуы мүмкін деп болжайды.[10] Agrawal болжамының өзгертілген нұсқасы, Agrawal-Popovych гипотезасы,[13] әлі де дұрыс болуы мүмкін.

Күрделілік

Жылы есептеу күрделілігі теориясы, жай сандарға сәйкес келетін ресми тіл PRIMES ретінде белгіленеді. PRIMES бар екенін көрсету оңай Co-NP: оның құрамы COMPOSITES NP өйткені факторды алдын-ала болжай отырып, композицияны шешуге болады.

1975 жылы, Вон Пратт көпмүшелік уақытта тексерілетін бірінші дәрежелі сертификат бар екенін және осылайша PRIMES болғанын көрсетті NP, сондықтан NP ∩ coNP. Қараңыз негізгі сертификат толық ақпарат алу үшін.

Соловай-Страссен және Миллер-Рабин алгоритмдерінің келесі ашылуы PRIMES-ті енгізді coRP. 1992 жылы Adleman-Huang алгоритмі[5] күрделілігін төмендетті ZPP = RP ∩ coRP, бұл Праттың нәтижесін ауыстырды.

The Adleman – Pomerance – Rumely бастапқы тест 1983 жылдан бастап PRIMES қойылды QP (квази-полиномдық уақыт ), жоғарыда аталған кластармен салыстыруға болатындығы белгісіз.

Практикада оның тартымдылығы, Риман гипотезасын болжайтын полиномдық уақыт алгоритмдері және басқа да осыған ұқсас дәлелдер болғандықтан, ұзақ уақыт күдіктенді, бірақ басымдылықты полиномдық уақытта шешуге болатындығы дәлелденбеді. Бар болуы AKS-тің бастапқы сынағы көптен бері келе жатқан сұрақты түпкілікті шешіп, PRIMES-ті орналастырды P. Алайда, PRIMES белгісіз P-аяқталды және оның ішінде жатқан сыныптарда жататыны белгісіз P сияқты NC немесе L. PRIMES жоқ екені белгілі Айнымалы0.[14]

Сандық-теоретикалық әдістер

Сияқты санның жай екенін тексеру үшін белгілі бір сандық-теоретикалық әдістер бар Лукас сынағы және Проттың сынағы. Бұл сынақтар әдетте факторизацияны талап етеді n + 1, n - 1 немесе ұқсас мөлшер, бұл олардың жалпы мақсаттағы алғашқы тестілеу үшін пайдалы еместігін білдіреді, бірақ олар көбінесе тексерілген сан кезінде өте күшті болады n ерекше формаға ие екендігі белгілі.

Лукас сынағы шындыққа негізделген көбейту реті санның а модуль n болып табылады n - 1 прайм үшін n қашан а Бұл қарабайыр түбір модулі n. Егер біз көрсете алсақ а үшін қарабайыр n, біз көрсете аламыз n қарапайым.

Әдебиеттер тізімі

  1. ^ а б Ризель (1994) 2-3 бет
  2. ^ Джон Селридж # Селфридждің алдын-ала тестілеу туралы болжамы.
  3. ^ а б c г. e Карл Померанс; Джон Л. Селридж; Сэмюэл С. Вагстафф, кіші. (Шілде 1980). «Псевдопремалар 25 · 10 дейін9" (PDF). Есептеу математикасы. 35 (151): 1003–1026. дои:10.1090 / S0025-5718-1980-0572872-7.
  4. ^ Роберт Байлли; Сэмюэл С. Вагстафф, кіші. (Қазан 1980). «Lucas Pseudoprimes» (PDF). Есептеу математикасы. 35 (152): 1391–1417. дои:10.1090 / S0025-5718-1980-0583518-6. МЫРЗА  0583518.
  5. ^ а б Адлеман, Леонард М.; Хуанг, Мин-Дех (1992). Шектеулі өрісте бірінші кезектегі сынау және абелия сорттары. Математикадан дәріс конспектілері. 1512. Шпрингер-Верлаг. ISBN  3-540-55308-8.
  6. ^ Чау, Х. Ф .; Міне, Х. (1995). «Кванттық факторизация арқылы алғашқы тест». arXiv:квант-ph / 9508005.
  7. ^ Поклингтон, H. C. (1914). «Ферма теоремасы бойынша үлкен сандардың жай немесе құрама табиғатын анықтау». Камбр. Фил. Soc. Proc. 18: 29–30. JFM  45.1250.02.
  8. ^ Вайсштейн, Эрик В. «Поклингтон Теоремасы». MathWorld.
  9. ^ Гари Л. Миллер (1976). «Риманның гипотезасы және басымдыққа арналған тесттер». Компьютерлік және жүйелік ғылымдар журналы. 13 (3): 300–317. дои:10.1016 / S0022-0000 (76) 80043-8.
  10. ^ а б Агровал, Маниндра; Каял, Нерадж; Саксена, Нитин. «Primes - P» (PDF). Математика жылнамалары. дои:10.4007 / жылнамалар.2004.160.781.
  11. ^ Агровал, Маниндра; Каял, Нерадж; Саксена, Нитин (2004). «PRIMES - P» (PDF). Математика жылнамалары. 160 (2): 781–793. дои:10.4007 / жылнамалар.2004.160.781.
  12. ^ Карл Померанс және Хендрик В. Ленстр (2005 жылғы 20 шілде). «Гаусс кезеңдерімен алғашқы тестілеу» (PDF).
  13. ^ Попович, Роман (30 желтоқсан 2008). «Агроальды гипотеза туралы ескерту» (PDF).
  14. ^ Э. Аллендер, М. Сакс және И.Е. Шпарлинский, бастапқы деңгейдің төменгі шегі, J. Comp. Сист. Ғылыми. 62 (2001), 356-36 бб.

Дереккөздер

Сыртқы сілтемелер