Innehåll

• Att gå
• Metod 1 av 4: Försök dela
• Metod 2 av 4: Använda Fermats lilla sats
• Metod 3 av 4: Använda Miller-Rabin-testet
• Metod 4 av 4: Använd den kinesiska återstående satsen
• Tips
• Förnödenheter

Primtal är nummer som bara är delbara av sig själva och kallas 1 - andra nummer förening tal. När det gäller att testa om ett nummer är primärt finns det flera alternativ. Några av dessa metoder är relativt enkla men inte alls praktiska för större antal. Andra tester som ofta används är faktiskt kompletta algoritmer baserade på en sannolikhet som ibland felaktigt betraktar ett tal som primärt. Läs vidare till steg 1 för att lära dig hur du testar dig själv om du har att göra med ett primtal.

Att gå

Metod 1 av 4: Försök dela

Att försöka dela är det överlägset enklaste sättet att testa ett nummer. För små siffror är det vanligtvis också det snabbaste sättet. Testet baseras på definitionen av ett primtal: ett tal är primt om det bara är delbart av sig själv och 1.

1. Anta n är det nummer du vill testa. Dela antalet n med alla möjliga delbara heltal. För större siffror som n = 101 är det oerhört opraktiskt att dela med något möjligt heltal mindre än n. Lyckligtvis finns det flera knep för att minska antalet faktorer som ska testas.
2. Bestäm om n även. Alla jämna tal är helt delbara med 2. Om n är jämnt kan du säga det n är ett sammansatt tal (och därför inte ett primtal). För att snabbt avgöra om ett nummer är jämnt behöver du bara vara uppmärksam på den sista siffran. Om den sista siffran är 2, 4, 6, 8 eller 0, är ​​siffran jämn och inte primär.
   • Det enda undantaget från denna regel är själva siffran 2, som, eftersom den är delbar av sig själv och 1, också är primär. 2 är den enda jämna prime.
3. Del n med valfritt tal mellan 2 och n-1. Eftersom ett primtal inte har några andra faktorer än sig själv och 1, och eftersom heltalsfaktorer är mindre än deras produkt, avgör kontroll av delbarheten för ett heltal mindre än n och större än 2 om n är prim. Vi börjar efter 2 eftersom jämna tal (multiplar av 2) inte kan vara primtal. Detta är långt ifrån ett effektivt sätt att testa, som du kommer att se nedan.
   • Om vi ​​till exempel vill använda den här metoden för att testa om 11 är primt eller inte, skulle vi dela 11 med 3, 4, 5, 6, 7, 8, 9 och 10 och leta efter ett heltalssvar utan återstod. Eftersom inget av dessa siffror passar helt in i 11 kan vi säga att 11 är ett är prime.
4. För att spara tid, testa bara upp till sqrt (n), avrundat uppåt. Att testa ett nummer n genom att kontrollera alla siffror mellan 2 och n-1 kan snabbt ta mycket tid. Till exempel, om vi ville kontrollera om 103 är primär med den här metoden, måste vi dela med 3, 4, 5, 6, 7 ... etc, hela vägen till 102! Lyckligtvis är det inte nödvändigt att testa så här. I praktiken är det bara nödvändigt att testa för faktorerna mellan 2 och kvadratroten av n. Om kvadratroten av n inte är ett tal, runda det till närmaste heltal och testa det här numret. Se nedan för en förklaring:
   • Låt oss undersöka faktorerna 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 och 100 × 1. Observera att efter 10 × 10 är faktorerna desamma om det för 10 × 10, bara sedan vänt. I allmänhet kan vi ignorera faktorerna n större än sqrt (n) eftersom de helt enkelt är en fortsättning av faktorer mindre än sqrt (n).
   • Låt oss prova ett exempel. Om n = 37 behöver vi inte testa alla siffror från 3 till 36 för att avgöra om n är primär. Istället behöver vi bara titta på siffrorna mellan 2 och sqrt (37) (avrundade uppåt).
     • sqrt (37) = 6,08 - vi ska runda upp detta till 7.
     • 37 är inte helt delbart med 3, 4, 5, 6 och 7 och så kan vi med säkerhet säga att det är en primtal är.
5. För att spara ännu mer tid använder vi bara huvudfaktorer. Det är möjligt att göra testprocessen genom att dela ännu kortare genom att inte inkludera de faktorer som inte är primtal. Per definition kan varje sammansatt tal uttryckas som produkten av två eller flera primtal. Så att dela talet n med ett sammansatt tal är onödigt - det motsvarar att dela med primtal flera gånger. Så vi kan ytterligare begränsa listan över möjliga faktorer till endast primtal mindre än sqrt (n).
   • Detta innebär att alla jämna faktorer, liksom de faktorer som är multiplar av primtal, kan hoppas över.
   • Låt oss till exempel försöka avgöra om 103 är prime eller inte. Kvadratroten på 103 är 11 (avrundat uppåt). Primtal mellan 2 och 11 är 3, 5, 7 och 11. 4, 6, 8 och 10 är jämna och 9 är en multipel av 3, ett primtal, så att vi kan hoppa över det. Genom att göra detta har vi minskat vår lista med möjliga faktorer till bara 4 siffror!
     • 103 är inte helt delbart med varken 3, 5, 7 eller 11, så vi vet nu att 103 är en primtal är.

Metod 2 av 4: Använda Fermats lilla sats

År 1640 föreslog den franska matematikern Pierre de Fermat först en sats (nu uppkallad efter honom) som kan vara till stor hjälp för att avgöra om ett tal är primt. Tekniskt sett är Fermats test avsett att verifiera att ett tal är sammansatt snarare än primt. Detta beror på att testet kan visa med "absolut säkerhet" att ett tal är sammansatt, men bara en "sannolikhet" att ett tal är primt. Fermats lilla sats är användbar i situationer där försök att dela är opraktiskt och när det finns en lista med siffror tillgängliga som är undantag från satsen.

1. Anta n numret är för testning. Du använder detta test för att avgöra om ett visst tal n är primt. Men som nämnts ovan kan denna sats ibland felaktigt karakterisera någon förening som primär. Det är viktigt att ta hänsyn till detta och kontrollera ditt svar, vilket förklaras nedan.
2. Välj ett heltal a mellan 2 och n-1 (inklusive). Det exakta heltalet du väljer är inte viktigt. Eftersom parametrarna för a inkluderar 2 och n-1 kan du också använda dem.
   • Ett exempel: Är 100 prime eller inte. Antag att vi tar 3 som ett testvärde - detta är mellan 2 och n-1, så det är tillräckligt.
3. Beräkna a (mod n). Att utarbeta detta uttryck kräver viss kunskap om ett matematiskt system som kallas modulär matematik. I modulär matematik återgår siffrorna till noll när de når ett visst värde, även känt som modul. Du kan tänka på detta som en klocka: så småningom kommer klockans hand att återgå till klockan 13 efter klockan 12, inte till klockan 13. Modulen noteras som (mod n). Så i detta steg beräknar du a med en modul av n.
   • En annan metod är att beräkna a, sedan dela det med n och sedan använda resten som svar. Specialiserade miniräknare med en modulfunktion kan vara mycket användbara när man delar stora siffror, eftersom de omedelbart kan beräkna resten av en division.
   • Med en sådan räknare i vårt exempel kan vi se att 3/100 har en återstod på 1. Så, 3 (mod 100) är 1.
4. Om vi ​​beräknar detta för hand använder vi exponenten som ett kort format. Om du inte har en miniräknare med en modulfunktion, använd notationen med en exponent för att förenkla proceduren för att bestämma resten. Se nedan:
   • I vårt exempel beräknar vi 3 med en modul på 100. 3 är ett mycket, mycket stort antal - 515,377,520,732,011,331,036,461,129,765,621,272,702,107,522,001 - så stort att det blir väldigt svårt att arbeta med. I stället för att använda det 48-siffriga svaret för 3, borde vi skriva det som en exponent, så (((((((3)*3))))*3)). Kom ihåg att ta exponenten för en exponent har effekten att multiplicera exponenterna ((x) = x).
     • Nu kan vi bestämma resten. Börja med att lösa ((((((3) * 3))) * 3)) i den inre parentesuppsättningen och arbeta dig ut genom att dela varje steg med 100. När vi har hittat resten använder vi det för nästa steg snarare än det faktiska svaret. Se nedan:
       • ((((((9) * 3))) * 3)) - 9/100 har ingen återstod, så vi kan fortsätta.
       • (((((27)))) * * 3)) - 27/100 har ingen återstod, så vi kan gå vidare.
       • ((((729))) * 3)) - 729/100 = 7 R 29. Vår återstående är 29. Vi fortsätter med nästa steg, inte 729.
       • ((((29=841)) * * 3)) - 841/100 = 8 R 41. Vi använder vår återstående 41 igen i nästa steg.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Vi använder vår återstående 81 i nästa steg.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Vi använder vår återstående 43 i nästa steg.
       • (43 = 1849) - 1849/100 = 18 R 49. Vi använder vår återstående 49 i nästa steg.
       • 49 = 2401 - 2401/100 = 24 R 1. vår sista rest är 1. Med andra ord, 3 (mod 100) = 1. Observera att detta är samma svar som vi beräknade i föregående steg!
5. Ta reda på om a (mod n) = a (mod n). Om inte är n förening. Om det är sant så är n förmodligen, (men inte säker) ett primtal. Upprepa testet med olika värden för a kan göra resultatet säkrare, men det finns sällsynta sammansatta tal som uppfyller Fermats sats för Allt värden på a. Dessa kallas Carmichael-siffrorna - det minsta av dessa siffror är 561.
   • I vårt exempel är 3 (mod 100) = 1 och 3 (mod 100) = 3.1 ≠ 3, så vi kan säga att 100 är ett sammansatt tal.
6. Använd Carmichael-siffrorna för att vara säker på ditt resultat. Att veta vilka siffror som uppfyller Carmichael-serien innan du fortsätter kan spara dig mycket oro för huruvida ett nummer är primärt eller inte. I allmänhet är Carmichael-tal produkten av enskilda primtal, där det för alla primtal tal hävdar att om p är en delare av n, så är också p-1 en delare av n-1. Online-listan över Carmichael-nummer kan vara mycket användbar för att avgöra om ett tal är primärt, med hjälp av Fermats lilla sats.
   
   

Metod 3 av 4: Använda Miller-Rabin-testet

Miller-Rabin-testet fungerar på samma sätt som Fermats lilla sats, men handlar bättre om icke-standardnummer som Carmichael-siffror.

1. Anta n är ett udda tal som vi vill testa för primalitet. Som i metoderna som anges ovan är n variabeln som vi vill bestämma primaliteten för.
2. Tryck n-1 i formen 2 × d vid vilken d är udda. Siffran n är primär om den är udda. Så n - 1 måste vara jämnt. Eftersom n - 1 är jämnt kan den skrivas som en kraft på 2 gånger ett udda tal. Så, 4 = 2 × 1; 80 = 2 × 5; och så vidare.
   • Antag att vi vill avgöra om n = 321 är prim. 321 - 1 = 320, som vi kan uttrycka som 2 × 5.
     • I detta fall är n = 321 ett lämpligt nummer. Att bestämma n - 1 för n = 371 kan kräva ett stort värde för d, vilket gör hela processen svårare i ett senare skede. 371 - 1 = 370 = 2 × 185
3. Välj valfritt nummer a mellan 2 och n-1. Det exakta antalet du väljer spelar ingen roll - bara att det måste vara mindre än n och större än 1.
   • I vårt exempel med n = 321 väljer vi a = 100.
4. Beräkna a (mod n). Om a = 1 eller -1 (mod n) och passerar sedan n Miller-Rabin-testet och är förmodligen ett primtal. Precis som med Fermats lilla sats kan detta test inte med absolut säkerhet avgöra ett tals primalitet utan kräver ytterligare tester.
   • I vårt exempel med n = 321 är a (mod n) = 100 (mod 321). 100 = 10.000.000.000 (mod 321) = 313. Vi använder en speciell kalkylator, eller förkortningsmetoden med en exponent som beskrivits tidigare, för att hitta resten av 100/321.
     • Eftersom vi inte har fått 1 eller -1 kan vi inte säga med säkerhet att n är prim. Men det är fortfarande mer vi behöver göra - läs vidare.
5. Eftersom resultatet inte är lika med 1 eller -1, beräkna a, a, ... och så vidare, upp till ad. Beräkna en höjning till kraften av d gånger, upp till 2. Om någon av dessa är lika med 1 eller -1 (mod n) och passerar sedan n Miller-Rabin testar och är förmodligen prime. Om du har bestämt att n klarar testet, kontrollera sedan ditt svar (se steg nedan). Om n misslyckas med något av dessa tester är det ett sammansatt siffra.
   • Som en påminnelse, i vårt exempel är värdet på a 100, värdet på s är 6 och d är 5. Vi fortsätter att testa enligt nedan:
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 64,64 ≠’ 1 eller -1. Fortsätt lugnt.
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 244,244 ≠ 1 eller -1.
     • Vid denna tidpunkt kan vi sluta. s - 1 = 6 - 1 = 5. Vi har nu nått 4d = 2, och det finns inga krafter på 2 gånger d under 5d. Eftersom ingen av våra beräkningar svarade 1 eller -1 kan vi säga att n = 321 sammansatt nummer är.
6. Om n klarar Miller-Rabin-testet, upprepa för de andra värdena för a. Om du har upptäckt att värdet på n kan vara primt, försök igen med ett annat slumpmässigt värde för a för att bekräfta testresultatet. Om n faktiskt är primärt kommer det att vara sant för alla värden på a. Om n är ett sammansatt tal kommer det att misslyckas i tre fjärdedelar av värdena på a. Detta ger dig mer säkerhet än Fermats lilla sats, där vissa sammansatta siffror (Carmichael-siffrorna) klarar testet för valfritt värde av a.

Metod 4 av 4: Använd den kinesiska återstående satsen

1. Välj två nummer. Ett av siffrorna är inte primärt och det andra är numret som testas för primalitet.
   • "Testnummer1" = 35
   • Testnummer2 = 97
2. Välj två datapunkter som är större än noll respektive mindre än TestNumber1 och TestNumber2. De kan inte vara lika med varandra.
   • Data1 = 1
   • Data2 = 2
3. Beräkna MMI (matematisk multiplikativ invers) för testnummer1 och testnummer2
   • Beräkna MMI
     • MMI1 = Testnummer2 ^ -1 Modtestnummer1
     • MMI2 = Testnummer1 ^ -1 Modtestnummer2
   • Endast för primtal (det kommer att bli ett resultat för icke-primtal, men det är inte MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (TestNumber1 ^ (TestNumber-2))% TestNumber2
   • Så:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Skapa en binär tabell för varje MMI upp till Log2 i Modulus
   • För MMI1
     • F (1) = Testnummer2% Testnummer1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Testnummer1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Testnummer1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Testnummer1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Testnummer1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Testnummer1 = 1 * 1% 35 = 1
   • Beräkna den binära logaritmen för TestNumber1 - 2
     • 35 -2 = 33 (10001) bas 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 Mod 35
     • MMI1 = 27
   • För MMI2
     • F (1) = Testnummer 1% 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
   • Beräkna den binära logaritmen för TestNumber2 - 2
     • 97 - 2 = 95 = (1011111) bas 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. Beräkna (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Svar = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Svar = (2619 + 4270)% 3395
   • Svar = 99
6. Kontrollera att "TestNumber1" inte är prime1
   • Beräkna (Svar - Data1)% Testnummer1
   • 99 -1 % 35 = 28
   • Eftersom 28 är större än 0 är 35 inte primt
7. Kontrollera om TestNumber2 är prime
   • Beräkna (Svar - Data2)% Testnummer2
   • 99 - 2 % 97 = 0
   • Eftersom 0 är lika med 0 är 97 ett potentiellt primtal
8. Upprepa steg 1 till 7 minst två gånger till.
   • Om steg 7 är lika med 0:
     • Använd ett annat "TestNumber1" om TestNumber1 inte är primt.
     • Använd ett annat TestNumber1 där ett TestNumber1 faktiskt är primärt. I detta fall är steg 6 och 7 lika med 0.
     • Använd olika datapunkter för data1 och data2.
   • Om steg 7 alltid är lika med 0, är ​​sannolikheten att siffran 2 är ett primtal mycket hög.
   • Steg 1 till 7 är kända för att vara felaktiga i vissa fall när den första siffran inte är prim och den andra är en primfaktor för det icke-primtalet "Test Number1". Det fungerar i alla scenarier där båda siffrorna är primära.
   • Anledningen till att steg 1 till 7 upprepas är att det finns några scenarier där, även om TestNumber1 inte är primt och TestNumber2 inte är primt, är något av siffrorna från steg 7 fortfarande noll. Dessa tillstånd är sällsynta. Genom att ändra TestNumber1 till ett annat icke-primtal, och om TestNumber2 inte är prime, kommer TestNumber2 inte längre vara lika med noll, i steg 7. Med undantag för det fall där "TestNumber1" är en faktor för TestNumber2, kommer primtal alltid att vara noll. steg 7.

Tips

• De 168 primtalen under 1000 är: 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 försök att dela är långsammare än de mer sofistikerade metoderna är det fortfarande effektivt för mindre antal. Även när man testar större siffror är det inte ovanligt att först kontrollera de små siffrorna innan man byter till de mer avancerade metoderna.

Förnödenheter

• Papper, penna, penna och / eller miniräknare för träning