Indhold

• At træde
• Metode 1 af 4: Prøv at dele
• Metode 2 af 4: Brug af Fermats lille sætning
• Metode 3 af 4: Brug af Miller-Rabin-testen
• Metode 4 af 4: Brug af den kinesiske restsætning
• Tips
• Nødvendigheder

Primtal er tal, der kun kan deles af sig selv og kaldes 1 - andre tal forbindelse numre. Når det kommer til at teste, om et tal er prime, er der flere muligheder. Nogle af disse metoder er relativt enkle, men slet ikke praktiske for større antal. Andre tests, der ofte bruges, er faktisk komplette algoritmer baseret på en sandsynlighed der undertiden fejlagtigt betragter et tal som prim. Læs videre til trin 1 for at lære at teste dig selv, hvis du har at gøre med et primtal.

At træde

Metode 1 af 4: Prøv at dele

At prøve at dele er langt den nemmeste måde at teste et nummer på. For små antal er det normalt også den hurtigste måde. Testen er baseret på definitionen af ​​et primtal: et tal er prime, hvis det kun er deleligt af sig selv og 1.

1. Formode n er det nummer, du vil teste. Del tallet n med alle mulige delbare heltal. For større tal som n = 101 er det enormt upraktisk at dividere med ethvert muligt heltal mindre end n. Heldigvis er der flere tricks til at reducere antallet af faktorer, der skal testes.
2. Find ud af om n også selvom. Alle lige tal kan deles med 2. Derfor, hvis n er lige, kan du sige det n er et sammensat tal (og derfor ikke et primtal). For hurtigt at afgøre, om et tal er lige, skal du kun være opmærksom på det sidste ciffer. Hvis det sidste ciffer er et 2, 4, 6, 8 eller 0, er tallet lige og ikke prime.
   • Den eneste undtagelse fra denne regel er selve tallet 2, som, fordi det er deleligt af sig selv og 1, også er det primære. 2 er den eneste lige prime.
3. En del n med et hvilket som helst tal mellem 2 og n-1. Fordi et primtal ikke har nogen andre faktorer end sig selv og 1, og fordi heltalsfaktorer er mindre end deres produkt, vil kontrol af delbarheden af ​​et heltal mindre end n og større end 2 afgøre, om n er primær. Vi starter efter 2, fordi lige tal (multipla af 2) ikke kan være primtal. Dette er langt fra en effektiv måde at teste på, som du vil se nedenfor.
   • For eksempel, hvis vi ønskede at bruge denne metode til at teste, om 11 er primær eller ej, dividerer vi 11 med 3, 4, 5, 6, 7, 8, 9 og 10 og søger efter et heltal uden resten. Da ingen af ​​disse tal passer helt ind i 11, kan vi sige, at 11 er et er prime.
4. For at spare tid skal du kun teste op til sqrt (n), rundet op. At teste et tal n ved at kontrollere alle tal mellem 2 og n-1 kan hurtigt tage meget tid. For eksempel, hvis vi ønskede at kontrollere, om 103 er prime med denne metode, skulle vi dele med 3, 4, 5, 6, 7 ... osv., Hele vejen til 102! Heldigvis er det ikke nødvendigt at teste sådan. I praksis er det kun nødvendigt at teste for faktorerne mellem 2 og kvadratroden af ​​n. Hvis kvadratroden af ​​n ikke er et tal, rundes det til nærmeste heltal og testes til dette tal. Se nedenfor for en forklaring:
   • Lad os undersøge faktorerne på 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 og 100 × 1. Bemærk at efter 10 × 10 er faktorerne de samme hvis det for 10 × 10, kun derefter vendt. Generelt kan vi ignorere faktorerne for n større end sqrt (n), da de simpelthen er en fortsættelse af faktorer mindre end sqrt (n).
   • Lad os prøve et eksempel. Hvis n = 37, behøver vi ikke teste alle tal fra 3 til 36 for at afgøre, om n er primær. I stedet skal vi bare se på tallene mellem 2 og sqrt (37) (afrundet op).
     • sqrt (37) = 6.08 - vi afrunder dette op til 7.
     • 37 kan ikke deles fuldstændigt med 3, 4, 5, 6 og 7, og så kan vi med sikkerhed fastslå, at det er en primtal er.
5. For at spare endnu mere tid bruger vi kun primære faktorer. Det er muligt at gøre testprocessen ved at dividere endnu kortere ved ikke at medtage de faktorer, der ikke er primtal. Per definition kan hvert sammensat tal udtrykkes som produktet af to eller flere primtal. Så det er unødvendigt at dividere tallet n med et sammensat tal - dette svarer til at dividere med primtal flere gange. Så vi kan indsnævre listen over mulige faktorer yderligere til kun primtal mindre end sqrt (n).
   • Dette betyder, at alle lige faktorer såvel som de faktorer, der er multipla af primtal, kan springes over.
   • Lad os for eksempel prøve at afgøre, om 103 er prime eller ej. Kvadratroden på 103 er 11 (afrundet op). Primtalene mellem 2 og 11 er 3, 5, 7 og 11. 4, 6, 8 og 10 er lige og 9 er et multiplum af 3, et primtal, så vi kan springe det over. Ved at gøre dette har vi reduceret vores liste over mulige faktorer til kun 4 tal!
     • 103 er ikke helt delelig med hverken 3, 5, 7 eller 11, så vi ved nu, at 103 er en primtal er.

Metode 2 af 4: Brug af Fermats lille sætning

I 1640 foreslog den franske matematiker Pierre de Fermat først en sætning (nu opkaldt efter ham), der kan være meget nyttig til at afgøre, om et tal er primt eller ej. Teknisk set er Fermats test beregnet til at verificere, at et tal er sammensat snarere end prime. Dette skyldes, at testen kan vise med "absolut sikkerhed", at et tal er sammensat, men kun en "sandsynlighed" for, at et tal er prime. Fermats lille sætning er nyttig i situationer, hvor forsøg på at opdele er upraktisk, og når der er en liste over numre til rådighed, der er undtagelser fra sætningen.

1. Formode n tallet er til test. Du bruger denne test til at bestemme, om et givet tal n er prime. Som nævnt ovenfor kan denne sætning imidlertid lejlighedsvis fejlagtigt karakterisere en forbindelse som primær. Det er vigtigt at tage dette i betragtning og kontrollere dit svar, som forklares nedenfor.
2. Vælg et heltal -en mellem 2 og n-1 (inklusive). Det nøjagtige heltal, du vælger, er ikke vigtigt. Da parametrene for a inkluderer 2 og n-1, kan du også bruge dem.
   • Et eksempel: Er 100 prime eller ej. Antag, at vi tager 3 som en testværdi - dette er mellem 2 og n-1, så det er tilstrækkeligt.
3. Beregn -en (mod n). At udarbejde dette udtryk kræver noget kendskab til et matematisk system kaldet modulær matematik. I modulær matematik vender tal tilbage til nul, når de når en bestemt værdi, også kendt som modulus. Du kan tænke på dette som et ur: til sidst vender uret tilbage til klokken 1 efter klokken 12, ikke til klokken 13. Modulet er angivet som (mod n). Så i dette trin beregner du a med et modul på n.
   • En anden metode er at beregne a, derefter dividere det med n og derefter bruge resten som dit svar. Specialiserede regnemaskiner med en modulfunktion kan være meget nyttige ved opdeling af store tal, fordi de straks kan beregne resten af ​​en division.
   • Ved hjælp af en sådan lommeregner i vores eksempel kan vi se, at 3/100 har en rest på 1. Så 3 (mod 100) er 1.
4. Hvis vi beregner dette manuelt, bruger vi eksponenten som et kort format. Hvis du ikke har en lommeregner med en modulfunktion, skal du bruge notationen med en eksponent for at gøre proceduren til bestemmelse af resten lettere. Se nedenunder:
   • I vores eksempel beregner vi 3 med et modul på 100. 3 er et meget, meget stort antal - 515,377,520,732,011,331,036,461,129,765,621,272,702,107,522,001 - så stort, at det bliver meget svært at arbejde med. I stedet for at bruge det 48-cifrede svar til 3, skal vi hellere skrive det som en eksponent (((((((3)*3))))*3)). Husk at tage eksponenten til en eksponent har den virkning at multiplicere eksponenterne ((x) = x).
     • Nu kan vi bestemme resten. Start med at løse ((((((3) * 3)))) * * 3)) i det indvendige sæt af parenteser, og arbejd dig ud og del hvert trin med 100. Når vi har fundet resten, bruger vi det til næste trin i stedet for det egentlige svar. Se nedenunder:
       • ((((((9) * 3))) * 3)) - 9/100 har ingen resterende, så vi kan fortsætte.
       • ((((((27)))) * * 3)) - 27/100 har ingen rest, så vi kan komme videre.
       • ((((729))) * 3)) - 729/100 = 7 R 29. Vores resten er 29. Vi fortsætter med det næste trin, ikke 729.
       • ((((29=841)) * * 3)) - 841/100 = 8 R 41. Vi bruger vores resterende 41 igen i næste trin.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Vi bruger vores resterende 81 i næste trin.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Vi bruger vores resterende 43 i det næste trin.
       • (43 = 1849) - 1849/100 = 18 R 49. Vi bruger vores resterende 49 i næste trin.
       • 49 = 2401 - 2401/100 = 24 R 1. vores sidste rest er 1. Med andre ord 3 (mod 100) = 1. Bemærk, at dette er det samme svar, som vi beregnet i det foregående trin!
5. Find ud af om -en (mod n) = -en (mod n). Hvis ikke, er n forbindelse. Hvis det er sandt, så er n sandsynligvis (men ikke sikker) et primtal. Gentagelse af testen med forskellige værdier for a kan gøre resultatet mere sikkert, men der er sjældne sammensatte tal, der tilfredsstiller Fermats sætning for alle værdier af a. Disse kaldes Carmichael-numrene - det mindste af disse tal er 561.
   • I vores eksempel er 3 (mod 100) = 1 og 3 (mod 100) = 3,1 ≠ 3, så vi kan sige, at 100 er et sammensat tal.
6. Brug Carmichael-numrene for at være sikker på dit resultat. At vide, hvilke numre der opfylder Carmichael-serien, inden du fortsætter, kan spare dig for en masse bekymring for, om et tal er primt eller ej. Generelt er Carmichael-tal produktet af individuelle primtal, hvor det for alle primtal tal hævder, at hvis p er en skillevægge af n, så er også p-1 en skillevægge af n-1. Online-listen over Carmichael-numre kan være meget nyttig til at bestemme, om et tal er prime ved hjælp af Fermats lille sætning.
   
   

Metode 3 af 4: Brug af Miller-Rabin-testen

Miller-Rabin-testen fungerer på samme måde som Fermats lille sætning, men beskæftiger sig bedre med ikke-standardiserede tal som Carmichael-tal.

1. Formode n er et ulige tal, som vi vil teste for primalitet. Som i metoderne angivet ovenfor er n den variabel, som vi ønsker at bestemme primaliteten af.
2. Tryk n-1 i form 2 × d hvor d er underligt. Nummeret n er primært, hvis det er ulige. Så n - 1 skal være jævn. Da n - 1 er lige, kan den skrives som en styrke på 2 gange et ulige tal. Så, 4 = 2 × 1; 80 = 2 × 5; og så videre.
   • Antag, at vi vil bestemme, om n = 321 er primær. 321 - 1 = 320, som vi kan udtrykke som 2 × 5.
     • I dette tilfælde er n = 321 et passende tal. Bestemmelse af n - 1 for n = 371 kan kræve en stor værdi for d, hvilket gør hele processen vanskeligere på et senere tidspunkt. 371 - 1 = 370 = 2 × 185
3. Vælg et hvilket som helst nummer -en mellem 2 og n-1. Det nøjagtige antal, du vælger, betyder ikke noget - bare at det skal være mindre end n og større end 1.
   • I vores eksempel med n = 321 vælger vi a = 100.
4. Beregn -en (mod n). Hvis -en = 1 eller -1 (mod n) og derefter passerer n Miller-Rabin test og er sandsynligvis et primtal. Som med Fermats lille sætning kan denne test ikke med absolut sikkerhed bestemme et tales primalitet, men kræver yderligere tests.
   • I vores eksempel med n = 321 er a (mod n) = 100 (mod 321). 100 = 10.000.000.000 (mod 321) = 313. Vi bruger en speciel lommeregner eller stenografimetoden med en eksponent som beskrevet tidligere for at finde resten af ​​100/321.
     • Da vi ikke har opnået 1 eller -1, kan vi ikke med sikkerhed sige, at n er primær. Men der er stadig mere, vi skal gøre - læs videre.
5. Da resultatet ikke er lig med 1 eller -1, beregnes det -en, -en, ... og så videre, op til -end. Beregn en hævet til d gange, op til 2. Hvis en af ​​disse er lig med 1 eller -1 (mod n) og derefter passerer n Miller-Rabin tester og er sandsynligvis prime. Hvis du har fastslået, at n består testen, skal du kontrollere dit svar (se trin nedenfor). Hvis n ikke opfylder nogen af ​​disse tests, er det en sammensat nummer.
   • Som en påmindelse, i vores eksempel, er værdien af ​​a 100, værdien af ​​s er 6, og d er 5. Vi fortsætter med at teste som vist nedenfor:
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 64,64 ≠’ 1 eller -1. Fortsæt roligt.
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 244,244 ≠ 1 eller -1.
     • På dette tidspunkt kan vi stoppe. s - 1 = 6 - 1 = 5. Vi har nu nået 4d = 2, og der er ingen kræfter 2 gange d under 5d. Da ingen af ​​vores beregninger svarede på 1 eller -1, kan vi sige, at n = 321 sammensat nummer er.
6. Hvis n består Miller-Rabin-testen, gentag for de andre værdier af -en. Hvis du har fundet ud af, at værdien af ​​n kunne være primær, skal du prøve igen med en anden tilfældig værdi for a for at bekræfte resultatet af testen. Hvis n faktisk er primær, vil det være sandt for enhver værdi af a. Hvis n er et sammensat tal, vil det mislykkes i tre fjerdedele af værdierne for a. Dette giver dig mere sikkerhed end Fermats lille sætning, hvor visse sammensatte tal (Carmichael-numrene) bestå testen for enhver værdi af a.

Metode 4 af 4: Brug af den kinesiske restsætning

1. Vælg to tal. Et af tallene er ikke primært, og det andet er det nummer, der testes for primalitet.
   • "Testnummer1" = 35
   • Test nummer2 = 97
2. Vælg to datapunkter, der er større end henholdsvis nul og mindre end TestNumber1 og TestNumber2. De kan ikke være lige til hinanden.
   • Data1 = 1
   • Data2 = 2
3. Beregn MMI (matematisk multiplikativ invers) for testnummer1 og testnummer2
   • Beregn MMI
     • MMI1 = Testnummer2 ^ -1 Mod testnummer1
     • MMI2 = testnummer1 ^ -1 mod testnummer2
   • Kun for primtal (der vil være et resultat for ikke-primtal, men det er ikke MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (TestNumber1 ^ (TestNumber-2))% TestNumber2
   • Så:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Opret en binær tabel for hver MMI op til Log2 i Modulus
   • Til MMI1
     • F (1) = Testantal2% Testnummer1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Testantal1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Testantal1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Testantal1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Testantal1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Testantal1 = 1 * 1% 35 = 1
   • Beregn den binære logaritme for TestNumber1 - 2
     • 35 -2 = 33 (10001) base 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 Mod 35
     • MMI1 = 27
   • Til MMI2
     • F (1) = Testantal1% Testnummer2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Testnummer2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Testnummer2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Testnummer2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Testnummer2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Testnummer2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Testnummer2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Testnummer2 = 35 * 35 mod 97 = 61
   • Beregn den binære logaritme for TestNumber2 - 2
     • 97 - 2 = 95 = (1011111) base 2
     • MMI2 = ((((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = ((((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. Beregn (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Svar = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Svar = (2619 + 4270)% 3395
   • Svar = 99
6. Kontroller, at "TestNumber1" ikke er prime1
   • Beregn (svar - data1)% testnummer1
   • 99 -1 % 35 = 28
   • Da 28 er større end 0, er 35 ikke prime
7. Kontroller, om TestNumber2 er prime
   • Beregn (svar - data2)% testnummer2
   • 99 - 2 % 97 = 0
   • Da 0 er lig med 0, er 97 et potentielt primtal
8. Gentag trin 1 til 7 mindst to gange til.
   • Hvis trin 7 er lig med 0:
     • Brug et andet "TestNumber1", hvis TestNumber1 ikke er prime.
     • Brug en anden TestNumber1, hvor en TestNumber1 faktisk er primær. I dette tilfælde er trin 6 og 7 lig med 0.
     • Brug forskellige datapunkter til data1 og data2.
   • Hvis trin 7 altid er lig med 0, er sandsynligheden for, at tallet 2 er et primtal, meget højt.
   • Trin 1 til 7 vides at være ukorrekte i visse tilfælde, når det første tal ikke er prime, og det andet er en primfaktor for det ikke-primtal "Test Number1". Det fungerer i alle scenarier, hvor begge tal er prime.
   • Årsagen til, at trin 1 til 7 gentages, er fordi der er et par scenarier, hvor, selvom TestNumber1 ikke er prime, og TestNumber2 ikke er prime, er begge tal fra trin 7 stadig nul. Disse forhold er sjældne. Ved at ændre TestNumber1 til et andet ikke-primtal, og hvis TestNumber2 ikke er prime, vil TestNumber2 ikke længere svare til nul, i trin 7. Bortset fra det tilfælde, hvor "TestNumber1" er en faktor for TestNumber2, vil primtal altid være nul. Er i trin 7.

Tips

• De 168 primtal under 1000 er: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
• Når forsøg på at opdele er langsommere end de mere sofistikerede metoder, er det stadig effektivt til mindre antal. Selv når man tester større tal, er det ikke ualmindeligt at kontrollere de små tal først, før man skifter til de mere avancerede metoder.

Nødvendigheder

• Papir, pen, blyant og / eller lommeregner til træning