Enkelthedstest

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 21. maj 2020; verifikation kræver 1 redigering .

Spørgsmålet om at bestemme, om et naturligt tal er primtal , er kendt som primaalitetsproblemet. $N$

En primalitetstest (eller primalitetstest) er en algoritme , der, efter at have taget et tal som input , tillader enten ikke at bekræfte antagelsen om tallets sammensætning eller præcist at hævde dets enkelhed. I det andet tilfælde kaldes det den sande primalitetstest. Primalitetstesten er således kun en hypotese om, at hvis algoritmen ikke bekræfter antagelsen om, at tallet er sammensat , så kan dette tal være primtal med en vis sandsynlighed . Denne definition indebærer mindre tillid til testresultatets overensstemmelse med den sande tilstand end en ægte primalitetstest, som giver et matematisk verificeret resultat. $N$ $N$

Introduktion

Problemer i diskret matematik er blandt de mest matematisk komplekse . En af dem er faktoriseringsproblemet , som består i at finde en faktorisering af et tal til primfaktorer. For at løse det skal du finde primtal, hvilket fører til problemet med enkelhed. Primalitetstestproblemet tilhører kompleksitetsklassen P , det vil sige, at køretiden for algoritmerne til at løse det afhænger polynomielt af størrelsen af inputdataene, hvilket blev bevist i 2002 . Der er en lignende, men ubevist, erklæring om faktoriseringsproblemet .

Nogle anvendelser af matematik ved hjælp af faktorisering kræver en række meget store primtal valgt tilfældigt. Algoritmen til at opnå dem, baseret på Bertrands postulat :

Algoritme:

Input : naturligt tal $N$
Løsning (søg efter et tilfældigt primtal P)
1. $P\får$ Funktionen til at generere et vilkårligt naturligt tal på et segment $[N,2N]$
2. Hvis sammensat, så $P$
  1. $P\venstrepil \,P+1$
  2. Hvis da $P=2N$
    1. $P\venstrepil \,N$
3. Returner " - tilfældig primtal" $P$

Tidspunktet for at løse problemet med denne algoritme er ikke defineret, men der er stor sandsynlighed for, at det altid er polynomium, så længe der er nok primtal, og de er mere eller mindre jævnt fordelt . For simple tilfældige tal er disse betingelser opfyldt.

Det er kendt ( Euklids sætning ), at sættet af primtal er uendeligt. Dirichlets sætning ( 1837 ) siger, at hvis gcd , så er der uendeligt mange primtal kongruente med modulo . Med andre ord er primtal fordelt ensartet i restklasser i henhold til Euler- funktionen [1] for enhver værdi af . Men hvis primtallene er jævnt fordelt, men der er meget få af dem, er søgningen muligvis ikke mulig i praksis. For at løse dette andet problem bruger vi primtalssætningen ( 1896 ), ifølge hvilken antallet af primtal i et interval stiger med . Dette tal har en tendens til uendelig ret hurtigt, hvorfra vi kan konkludere, at selv for store værdier er der en ret stor sandsynlighed ( ) for at finde et primtal tilfældigt. Ud fra dette kan vi konkludere, at den ovenfor beskrevne algoritme kan give svaret i polynomiel tid, hvis der er en polynomiel algoritme, der giver os mulighed for at verificere enkelheden af et vilkårligt stort tal , hvilket fører til problemet med primalitet. $(a,n)=1$ $-en$ $n$ $modn$ $\varphi (n)$ $n$ $[2,n]$ $n$ $n/log(n)$ $n$ $1/ln(n)$ $n$

Historisk information

Den allerførste omtale af primtal kendes fra Euklid ( 3. århundrede f.Kr. ). Samtidig blev den første algoritme til at finde primtal opfundet af Eratosthenes ( II århundrede f.Kr. ) og er nu kendt som Eratosthenes si . Dens essens ligger i den sekventielle udelukkelse fra listen over heltal fra til multipla af andre primtal allerede fundet af "sigten" [2] . Langt senere foreslog den arabiske matematiker Ibn al-Banna at opregne heltal ikke op til , men op til , hvilket gjorde det muligt at reducere antallet af operationer. Ulempen ved denne metode er, at i stedet for at kontrollere et givet tal for enkelhed, tilbyder den en sekventiel opregning [3] af alle heltal op til , og er derfor ineffektiv og kræver betydelig computerkraft . $en$ $n$ $2,3,5$ $n$ ${\sqrt {n}}$ $n$ ${\sqrt {n}}$

I begyndelsen af det 13. århundrede foreslog Leonardo af Pisa , kendt som Fibonacci, en talfølge (opkaldt efter ham), hvor en af egenskaberne er, at det -. Fibonacci - tal kun kan være primtal for primtal , bortset fra . Denne egenskab kan bruges, når man tester Fibonacci-tal for primalitet. Han foreslog også, uafhængigt af ibn al-Banna, en metode til at kontrollere tal for enkelhed ved opregning. Denne algoritme er sand (eller usandsynlig), fordi svaret altid opnås, men ekstremt ineffektivt. $n$ $F_{n}$ $n$ $n=4$

Den første til at bruge relationer mellem tal til at definere primalitet var Pietro Antonio Cataldi i sit arbejde med perfekte tal. Perfekte tal er dem, der er lig med summen af deres egne divisorer. De første syv perfekte tal er 6, 28, 496, 8128, 33550336, 8589869056 og 137438691328. Cataldi fastslog, at hvis et tal er primtal, og tallet også er primtal, så er tallet perfekt. $n$ $2^{n}-1$ $2^{{n-1}}(2^{n}-1)$

I det 17. århundrede var den franske matematiker Marin Mersenne engageret i undersøgelsen af tal af formen [4] , senere navngivet Mersenne-tal til hans ære . Mersenne opdagede, at af de første 257 Mersenne-tal er kun 11 primtal (for n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 og 257). Ved at gøre det lavede han flere fejl ( er ikke primtal ved p = 67 eller 257, og er ved p = 61, 89 og 107). Søgningen efter primtal blandt Mersenne-tal er ret enkel takket være Luc-Lehmer-testen , som giver dig mulighed for at finde en løsning relativt hurtigt. Derfor er Mersenne-tallene de største blandt de i øjeblikket kendte primtal. I korrespondancen mellem Mersenne og Fermat blev flere flere ideer vedrørende primtal udtrykt [4] . $2^{n}-1$ $2^{n}-1$

Så Fermat opdagede, at hvis et heltal ikke er deleligt med et primtal , så er tallet altid deleligt med ( Fermats lille sætning ). Sætningen blev senere generaliseret af Euler . Adskillige primalitetstest er baseret på Fermats lille sætning. Fermat foreslog også, at tallene i formen for alle naturlige tal er primtal . Dette er faktisk tilfældet for . Et modeksempel på denne påstand fandt Euler- . For at teste Fermat-tal for primalitet er der en effektiv Pepin-test . Til dato er der ikke fundet nye Fermat-primtal. $-en$ $s$ $a^{{p-1}}-1$ $s$ $2^{2^{k}}+1$ $k$ $k=0,1,2,3,4$ $2^{2^{5}}+1=4294967297=641\cdot 6700417$

Blandt andre videnskabsmænd, Euler, Legendre , Gauss beskæftiget sig med enkelheden af tal . Betydelige resultater med at løse problemet med primalitet blev opnået af den franske matematiker Édouard Lucas i hans arbejde med Fermat- og Mersenne-tallene. Det er kriteriet for enkelheden af Mersenne-tallene givet af ham, der nu er kendt som Lucas-Lehmer-testen.

I 2002 blev en deterministisk polynomiel primalitetstest, Agrawal-Kayal-Saxena-testen , udviklet . Dets fremkomst blev forudsagt af eksistensen af polynomielle primalitetscertifikater og som en konsekvens af det faktum, at problemet med at kontrollere et tal for primalitet tilhørte NP- og co-NP- klasserne på samme tid.

Ægte primalitetstests

Eksisterende algoritmer til at teste et tal for primalitet kan opdeles i to kategorier: ægte primalitetstest og sandsynlighedsprimalitetstest. Sande tests som et resultat af beregninger giver altid kendsgerningen til enkelthed eller sammensætning af et tal, en probabilistisk test giver et svar om sammensætningen af et tal eller dets ikke-sammensætning med en vis sandsynlighed [2] [4] . For at sige det enkelt siger den probabilistiske algoritme, at tallet højst sandsynligt ikke er sammensat, men i sidste ende kan det vise sig at være enten primtal eller sammensat. Tal, der opfylder den probabilistiske primalitetstest, men er sammensatte, kaldes pseudoprimer [1] . Et eksempel på sådanne tal er Carmichael-tallene [3] . Du kan også navngive Euler-Jacobi-numrene for Solovay-Strassen-testen og Lucas pseudoprimer. $\epsilon$

Et eksempel på ægte primalitetstest er Luc-Lehmer-testen for Mersenne-tal . Den åbenlyse ulempe ved denne test er, at den kun gælder for en række bestemte slags tal. Andre eksempler inkluderer dem, der er baseret på Fermats lille sætning :

Pepins test for Fermat-tal .
Proths sætning for Proths tal .
Agrawal-Kayala-Saxene-test , den første polynomielle primalitetstest.
Luc-Lehmer-Riesel test .

Såvel som:

divisor iteration metode .
Wilsons sætning .
Pocklington-kriteriet .
Miller test .
Adleman-Pomerans-Rumeli test , forbedret [5] af Cohen og Lenstroy
Primalitetstest ved hjælp af elliptiske kurver .

Probabilistiske primalitetstests

Denne kategori omfatter:

Enkelthedstest i kryptografi

I øjeblikket er primtal meget brugt inden for informationssikkerhed. Først og fremmest skyldes dette opfindelsen af den offentlige nøglekrypteringsmetode, som bruges i informationskryptering og i elektroniske digitale signaturalgoritmer . I øjeblikket er størrelsen af primtal, der bruges til dannelsen af en digital signatur ved hjælp af elliptiske kurver, i henhold til standarderne, i overensstemmelse med GOST R 34.10-2012 mindst 254 bit. For så store tal er spørgsmålet om at bestemme et tals primehed ekstremt vanskeligt. Simple metoder, såsom opregningsmetoden, er uegnede til brug på grund af, at de kræver en ekstremt stor mængde beregningsressourcer og meget tid [6] .

Bestemmelsen af et tals primeness er også nødvendig, når man krakker information krypteret eller signeret ved hjælp af RSA-algoritmen . For at åbne sådan en besked er det nødvendigt at kunne opdele et tal i to primfaktorer, hvilket er en ikke-triviel opgave for store tal.

På den anden side, når der genereres nøgler til offentlige nøglekryptosystemer , elektroniske signatursystemer osv., bruges store pseudo-tilfældige primtal. For eksempel, når du bruger Diffie-Hellman-protokollen, er det nødvendigt at have et primtal, der angiver det endelige felt . Derfor gør brugen af en effektiv primatitetstest det muligt at øge pålideligheden af algoritmer til generering af sådanne nøgler.

Se også

Noter

↑ 1 2 Kormen T., Leiser Ch . Algoritmer. Konstruktion og analyse. - M. : MTSNMO, 2002. - S. 765-772.
↑ 1 2 Vasilenko O. N. Talteoretiske algoritmer i kryptografi. - M. : MTSNMO, 2003. - 328 s.
↑ 1 2 Crandall R., Pomerance C. Prime Numbers: A Computational Perspective. - Springer, 2005.
↑ 1 2 3 Donald Knuth . Kunsten at programmere, bind 2. Afledte algoritmer. - M . : "Williams" , 2007.
↑ Nesterenko Yu. V. Introduktion til kryptografi. - Peter, 2001. - 288 s.
↑ B. Schneier. Anvendt kryptografi. - S. 296-300.

Litteratur

Vasilenko O. N. Kapitel 1. Test af tal for primalitet og konstruktion af store primtal // Talteoretiske algoritmer i kryptografi . - M. : MTSNMO, 2003. - S. 12-56. — 328 s. — ISBN 5-94057-103-4 . Arkiveret 27. januar 2007 på Wayback Machine
Nesterenko Yu. V. Kapitel 4.6. Sådan kontrolleres et stort tal for enkelhed // Introduktion til kryptografi / Red. V. V. Yashchenko. - Peter, 2001. - 288 s. - ISBN 5-318-00443-1 . Arkiveret 25. februar 2008 på Wayback Machine
Schneier B. Del 3. Kryptografiske algoritmer. Kapitel 11 11.5. Prime Number Generation // Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protokoller, algoritmer og kildekode i C. - M. : Triumph, 2002. - S. 296-300. — 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .
Kormen T., Leiser C. Kapitel 33.8. Kontrol af tal for enkelhed // Algoritmer. Konstruktion og Analyse . - M. : MTSNMO, 2002. - S. 765-772. - ISBN 5-900916-37-5 .
Crandall R., Pomerance C. Kapitel 3. Genkendelse af primtal og kompositter. Kapitel 4. "Primality Proving" // Prime Numbers: A Computational Perspective . - Springer, 2005. - S. 117-224. — ISBN 0-387-25282-7 .
Donald Knuth . Kapitel 4.5.4. Prime Factorization // The Art of Programming, bind 2. De resulterende algoritmer = The Art of Computer Programming, vol. 2. Seminumeriske algoritmer. - 3. udg. - M .: "Williams" , 2007. - S. 832. - ISBN 0-201-89684-2 .

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme

Talteoretiske algoritmer
Enkelthedstest	AKC test ÅOP test Bailey-PSU Elliptisk kurve Pocklington-kriterium Farm test Luke test Luc-Lehmer test Luc-Lehmer-Riesel test Prots sætning Pepin test Kvadratisk Frobenius test Nightingale-Strassen test Miller-Rabin test
Generering af primtal	Atkins si Sigte af Eratosthenes Sigte Sundarama Decay Wheel
Faktorisering af heltal	Fortsat fraktionsmetode Dixons algoritme Elliptisk kurve metode Euler metode Pollards ρ-algoritme p −1 Pollard metode p +1-Williams metode Firkantet sigte Generel talfeltsigtemetode Speciel talfeltsigtemetode Rationel sigte Fermat metode Quadratic Shanks former Iteration over divisorer Shors algoritme
Multiplikation	oldægyptisk Multiplikation med en kolonne Karatsuba Toom-Cook algoritme Schönhage - Strassen Fuhrer
Diskret logaritme	Gelfond-Shanks algoritme ρ-algoritme "Kænguru" Polyga - Hellman ordreberegning Funktion feltsigte
Største fælles deler	Binær algoritme Euklids algoritme Udvidet Euklids algoritme Lemaires GCD-algoritme
Modulær kvadratrod	Cipolla algoritme Pocklington algoritme Gelfond-Shanks algoritme
Andre algoritmer	Chakrawala metode Kornakkiyas algoritme LLL heltals kvadratrod Eksponentieringsmodul Shufs algoritme
Kursiv skrift betyder, at algoritmen er designet til tal af en særlig art