Tartalom

• Lépni
• 1. módszer a 4-ből: Próbáljon megosztani
• 2/4 módszer: Fermat kis tételének használata
• 3/4 módszer: Miller-Rabin teszt alkalmazása
• 4/4-es módszer: A kínai fennmaradó tétel használata
• Tippek
• Szükségletek

A prímszámok olyan számok, amelyek csak önmagukban oszthatók meg, és 1 - más számoknak hívják őket összetett számok. Amikor azt teszteljük, hogy egy szám elsődleges-e, számos lehetőség van. Ezen módszerek némelyike ​​viszonylag egyszerű, de nagyobb számban egyáltalán nem praktikus. Más gyakran használt tesztek valójában egy komplett algoritmusok, amelyek az egyiken alapulnak valószínűség akik néha tévesen tekintenek elsődlegesnek egy számot. Olvassa el az 1. lépést, hogy megtanulja, hogyan tesztelje magát, ha prímszámmal van dolga.

Lépni

1. módszer a 4-ből: Próbáljon megosztani

Az osztás megkísérlése messze a legegyszerűbb módszer egy szám tesztelésére. Kis szám esetén ez általában a leggyorsabb út is. A teszt a prímszám meghatározásán alapul: egy szám akkor prím, ha csak önmagával és 1-vel osztható.

1. Tegyük fel n a tesztelni kívánt szám. Osszuk el az n számot az összes lehetséges osztható egész számmal. Nagyobb számoknál, például n = 101, rendkívül nem praktikus az esetleges n-nél kisebb egész számokkal osztani. Szerencsére számos trükk létezik a tesztelendő tényezők számának csökkentésére.
2. Határozza meg, hogy n még. Minden páros szám teljesen osztható 2-vel. Ezért ha n páros, akkor ezt mondhatja n összetett szám (és ezért nem prímszám). Ahhoz, hogy gyorsan megállapítsa, hogy egy szám páros-e, csak az utolsó számjegyre kell figyelnie. Ha az utolsó számjegy 2, 4, 6, 8 vagy 0, akkor a szám páros és nem prím.
   • Az egyetlen kivétel ez alól a szabály alól maga a 2-es szám áll, amely, mivel önmagában osztható és 1, szintén elsődleges. 2 az egyetlen páros prím.
3. Rész n 2 és n-1 közötti tetszőleges számmal. Mivel egy prímszámnak nincs más tényezője, csak ő maga és 1, és mivel az egész faktorok kisebbek, mint szorzatuk, az n-nél kisebb és 2-nél nagyobb egészek oszthatóságának ellenőrzése meghatározza, hogy n prím-e. 2 után kezdjük, mert a páros számok (2-es többszörösei) nem lehetnek prímszámok. Ez messze nem hatékony tesztelési módszer, amint az alább látható lesz.
   • Például, ha ezt a módszert szeretnénk használni annak tesztelésére, hogy 11 prím-e vagy sem, akkor a 11-et elosztanánk 3-mal, 4-vel, 5-vel, 6-tal, 7-vel, 8-mal, 9-vel és 10-gyel, és maradék nélkül keresnénk egy egész választ. Mivel ezen számok egyike sem illik teljesen a 11-be, azt mondhatjuk, hogy a 11 egy elsődleges.
4. Időmegtakarítás érdekében csak az sqrt (n), kerekítve. Az n szám tesztelése a 2 és n-1 közötti összes szám ellenőrzésével gyorsan sok időt vehet igénybe. Például, ha ellenőrizni akarjuk, hogy a 103-as érték elsődleges-e ezzel a módszerrel, akkor 3, 4, 5, 6, 7 ... stb-vel kell osztanunk, egészen a 102-ig! Szerencsére nem szükséges így tesztelni. A gyakorlatban csak a 2 és az n négyzetgyöke közötti tényezők tesztelésére van szükség. Ha n négyzetgyöke nem szám, kerekítse a legközelebbi egész számra, és tesztelje ezt a számot. Az alábbiakban magyarázatot talál:
   • Vizsgáljuk meg a 100-as tényezőket. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 és 100 × 1. Vegye figyelembe, hogy 10 × 10 után a tényezők ugyanazok ha ez 10 × 10-re, csak akkor fordítsa meg. Általánosságban figyelmen kívül hagyhatjuk az n-nél nagyobb tényezőket, mint az sqrt (n), mivel ezek egyszerűen az sqrt (n) -nél kisebb tényezők folytatását jelentik.
   • Próbáljunk ki egy példát. Ha n = 37, akkor nem kell minden 3 és 36 közötti számot tesztelnünk annak megállapításához, hogy n prím-e. Ehelyett csak meg kell néznünk a 2 és az sqrt (37) közötti számokat (felfelé kerekítve).
     • sqrt (37) = 6,08 - ezt kerekítjük 7-ig.
     • A 37 nem osztható teljesen 3-mal, 4-vel, 5-vel, 6-mal és 7-gyel, így magabiztosan kijelenthetjük, hogy egy prímszám van.
5. Hogy még több időt spórolhassunk meg, csak elsődleges tényezőket használunk. Lehetséges a tesztelés folyamatát úgy, hogy még rövidebbre osztjuk, ha nem vesszük figyelembe azokat a tényezőket, amelyek nem prímszámok. Definíció szerint minden összetett szám kifejezhető két vagy több prímszám szorzataként. Tehát felesleges osztani az n számot egy összetett számmal - ez egyenértékű a többszörös osztással prímszámokkal. Tehát tovább szűkíthetjük a lehetséges tényezők listáját csak sqrt (n) -nél kisebb prímszámokra.
   • Ez azt jelenti, hogy minden páros tényező, valamint azok a tényezők, amelyek a prímszámok többszörösei, kihagyhatók.
   • Például próbáljuk meg meghatározni, hogy a 103 prím-e vagy sem. A 103 négyzetgyöke 11 (felfelé kerekítve). A 2 és 11 közötti prímszámok 3, 5, 7 és 11. 4, 6, 8 és 10 páros, a 9 pedig a 3 többszöröse, egy prímszám, így kihagyhatjuk. Ezzel a lehetséges tényezők listáját mindössze 4 számra csökkentettük!
     • A 103 nem osztható teljesen sem 3-mal, sem 5-tel, sem 7-gyel, sem 11-gyel, így ma már tudjuk, hogy a 103 egy prímszám van.

2/4 módszer: Fermat kis tételének használata

1640-ben Pierre de Fermat francia matematikus először javasolt egy tételt (amelyet most róla neveztek el), amely nagyon hasznos lehet annak meghatározásában, hogy egy szám prím-e vagy sem. Technikailag a Fermat-teszt célja annak igazolása, hogy egy szám összetett, nem pedig prím. A teszt ugyanis "teljes bizonyossággal" megmutathatja, hogy egy szám összetett, de csak egy "valószínűség", hogy egy szám elsődleges. Fermat kis tétele hasznos azokban a helyzetekben, amikor az osztás megkísérlése nem praktikus, és amikor rendelkezésre áll olyan számok listája, amelyek kivételt képeznek a tétel alól.

1. Tegyük fel n a szám tesztelésre szolgál. Ezt a tesztet használja annak meghatározására, hogy egy adott n szám prím-e. Amint azonban a fentiekben megjegyeztük, ez a tétel esetenként tévesen jellemezhet egyes vegyületeket prímként. Fontos, hogy ezt figyelembe vegye, és ellenőrizze a válaszát, amelyet az alábbiakban ismertetünk.
2. Válasszon egész számot a között 2 és n-1 (beleértve). A kiválasztott pontos egész szám nem fontos. Mivel az a paraméterei közé tartozik a 2 és az n-1, akkor ezeket is használhatja.
   • Példa: 100 prím vagy sem. Tegyük fel, hogy bevesszük 3 tesztértékként - ez 2 és n-1 között van, tehát ez elegendő.
3. kiszámítja a (mod n). Ennek a kifejezésnek a kidolgozása némi ismeretet igényel az úgynevezett matematikai rendszerről moduláris matematika. A moduláris matematikában a számok nullára térnek vissza, amikor elérnek egy bizonyos értéket, más néven modulus. Ezt úgy gondolhatja, mint egy órát: végül az óra mutatója 12 óra után 1 órára tér vissza, nem pedig 13 órára. A modulust a (mod n). Tehát ebben a lépésben kiszámítja az a-t n modulusszal.
   • Egy másik módszer az a kiszámítása, majd elosztása n-vel, majd a maradék felhasználása válaszként. A modulusfüggvényű speciális számológépek nagyon hasznosak lehetnek nagy számok felosztásakor, mert azonnal kiszámíthatják az osztás fennmaradó részét.
   • Ilyen számológépet használva a példánkban láthatjuk, hogy a 3/100 maradéka 1. Tehát 3 (mod 100) 1.
4. Ha ezt kézzel számoljuk, akkor a kitevőt használjuk rövid formátumként. Ha nem rendelkezik modulusfüggvényű számológéppel, használja a kitevővel ellátott jelölést, hogy megkönnyítse a maradék meghatározásának eljárását. Lásd lentebb:
   • Példánkban 3-at számolunk 100 modulussal. 3 nagyon-nagyon nagy szám - 515,377,520,732,011,331,036,461,129,765,621,272,702,107,522,001 - olyan nagy, hogy nagyon nehéz vele dolgozni. Ahelyett, hogy a 48 számjegyű választ 3-ra használnánk, jobb, ha kitevőnek írjuk, tehát (((((((3)*3))))*3)). Ne felejtsük el, hogy a kitevõ kitevõjének felvétele hatással van a kitevõk szorzására ((x) = x).
     • Most meghatározhatjuk a többit. Kezdje azzal, hogy megoldja a (((((((((3) * 3)))) * 3)) elemet a zárójelek belső halmazánál, és haladjon tovább, minden lépést elosztva 100-zal. Miután megtaláltuk a többit, ezt használjuk fel a következő lépésben, nem pedig a tényleges válaszra. Lásd lentebb:
       • ((((((((9) * 3)))) * * 3)) - A 9/100-nak nincs maradéka, így folytathatjuk.
       • ((((((27)))) * * 3)) - a 27/100-nak nincs maradéka, így továbbléphetünk.
       • (((((729))) * 3)) - 729/100 = 7 R 29. A fennmaradó részünk 29. A következő lépéssel folytatjuk, nem a 729-gyel.
       • ((((29=841)) * 3)) - 841/100 = 8 R 41. A maradék 41-ét a következő lépésben újra felhasználjuk.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. A fennmaradó 81-et felhasználjuk a következő lépésben.
       • ((81*3 = 243)) - 243/100 = 2 R 43. A maradék 43-at a következő lépésben használjuk fel.
       • (43 = 1849) - 1849/100 = 18 R 49. A maradék 49-ét a következő lépésben használjuk fel.
       • 49 = 2401 - 2401/100 = 24 R 1. végső maradékunk 1. Más szóval 3 (mod 100) = 1. Vegye figyelembe, hogy ez ugyanaz a válasz, mint amit az előző lépésben kiszámítottunk!
5. Tudja meg, hogy a (mod n) = a (mod n). Ha nem, akkor n jelentése vegyület. Ha igaz, akkor n valószínűleg (de nem biztos) prímszám. A teszt különböző értékekkel történő megismétlése biztosabbá teheti az eredményt, de vannak olyan ritka összetett számok, amelyek kielégítik Fermat tételét minden értékei. Ezeket Carmichael-számoknak nevezzük - ezek közül a legkisebb 561.
   • Példánkban 3 (mod 100) = 1 és 3 (mod 100) = 3,1 ≠ 3, tehát azt mondhatjuk, hogy 100 összetett szám.
6. Használja a Carmichael-számokat, hogy biztos legyen az eredményében. Annak ismerete, hogy a folytatás előtt mely számok felelnek meg a Carmichael sorozatnak, sok aggodalomra adhat okot, hogy egy szám elsődleges-e vagy sem. Általánosságban a Carmichael-számok az egyes prímszámok szorzata, ahol az összes prímszám esetében az áll, hogy ha p osztója n-nek, akkor p-1 is osztója n-1-nek. A Carmichael-számok online listája nagyon hasznos lehet annak megállapításához, hogy egy szám prím-e, Fermat kis tételének felhasználásával.
   
   

3/4 módszer: Miller-Rabin teszt alkalmazása

A Miller-Rabin teszt ugyanúgy működik, mint Fermat kis tétele, de jobban foglalkozik a nem szabványos számokkal, például a Carmichael-számokkal.

1. Tegyük fel n egy páratlan szám, amelyet prímaságra akarunk tesztelni. Ahogy a fentiekben jelzett módszerekben, úgy n is az a változó, amelynek az elsődlegességét meg akarjuk határozni.
2. Nyomás n-1 formában 2 × d ahol d furcsa. Az n szám prím, ha páratlan. Tehát az n - 1-nek egyenletesnek kell lennie. Mivel n - 1 páros, páratlan szám kétszerese hatványként írható. Tehát 4 = 2 × 1; 80 = 2 × 5; stb.
   • Tegyük fel, hogy meg akarjuk határozni, hogy n = 321 prím-e. 321 - 1 = 320, amelyet így fejezhetünk ki 2 × 5.
     • Ebben az esetben n = 321 megfelelő szám. Az n - 1 meghatározása n = 371 esetén nagy d értéket igényelhet, ami egy későbbi szakaszban megnehezíti az egész folyamatot. 371 - 1 = 370 = 2 × 185
3. Válasszon tetszőleges számot a között 2 és n-1. A kiválasztott pontos szám nem számít - csak az, hogy n-nél kisebbnek és 1-nél nagyobbnak kell lennie.
   • Az n = 321-es példánkban az a = értéket választjuk 100.
4. kiszámítja a (mod n). Ha a = 1 vagy -1 (mod n), majd elmúlik n a Miller-Rabin teszt és az valószínűleg prímszám. Csakúgy, mint Fermat kis tételénél, ez a teszt sem képes teljes bizonyossággal meghatározni a szám elsődlegességét, de további teszteket igényel.
   • Példánkban n = 321, a (mod n) = 100 (mod 321). 100 = 10 000 000 000 (mod 321) = 313. Egy speciális számológépet, vagy a korábban leírt exponensű gyorsírásos módszert használunk a 100/321 fennmaradó részének megkeresésére.
     • Mivel nem kaptunk 1-et vagy -1-et, nem mondhatjuk biztosan, hogy n prím. De még mindig van mit tennünk kell - olvass tovább.
5. Mivel az eredmény nem egyenlő 1 vagy -1 értékkel, számítsa ki a, a, ... és így tovább, egészen ad. Számítsuk ki a d-szer hatványáig emelt értéket, legfeljebb 2-ig. Ha ezek bármelyike ​​megegyezik 1-vel vagy -1-vel (mod n), majd elmúlik n a Miller-Rabin teszteli és valószínűleg elsődleges. Ha megállapította, hogy n megfelel a tesztnek, akkor ellenőrizze a válaszát (lásd az alábbi lépést). Ha n nem felel meg ezeknek a teszteknek, akkor az egy komponált szám.
   • Emlékeztetőül: példánkban az a értéke 100, s értéke 6 és d értéke 5. Folytatjuk a tesztelést az alábbiak szerint:
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 64,64 ≠’ 1 vagy -1. Menjen tovább nyugodtan.
     • 100 = 1 × 10.
       • 1 × 10 (321. mód.) = 244,244 ≠ 1 vagy -1.
     • Ezen a ponton megállhatunk. s - 1 = 6 - 1 = 5. Most elértük a 4d = 2 értéket, és 5d alatt nincs 2 d-szeres hatvány. Mivel egyik számításunk sem válaszolt 1-re vagy -1-re, azt mondhatjuk, hogy n = 321 egyet komponált szám az.
6. Ha n megfelel a Miller-Rabin tesztnek, ismételje meg a többi értékét a. Ha megállapította, hogy n értéke prím lehet, próbálkozzon újra egy másik, véletlenszerű értékkel az a számára, hogy megerősítse a teszt eredményét. Ha n valóban elsődleges, akkor az a bármely értékére igaz lesz. Ha n összetett szám, akkor az a értéke háromnegyedéig kudarcot vall. Ez nagyobb bizonyosságot ad, mint Fermat kis tétele, ahol bizonyos az összetett számok (a Carmichael-számok) megfelelnek az a bármely értékének tesztjén.

4/4-es módszer: A kínai fennmaradó tétel használata

1. Válasszon két számot. Az egyik szám nem prím, a második pedig az a szám, amelyet prímásra tesztelnek.
   • "Tesztszám1" = 35
   • 2. tesztszám = 97
2. Válasszon két nullánál nagyobb és kevesebb, mint a TestNumber1 és a TestNumber2 adatpontot. Nem lehetnek egyenlőek egymással.
   • Adatok1 = 1
   • Adatok2 = 2
3. Számítsa ki az 1. és a 2. tesztszám MMI-jét (matematikai multiplikatív inverz)
   • Számítsa ki az MMI-t
     • MMI1 = Tesztszám2 ^ -1 Mod Tesztszám1
     • MMI2 = Tesztszám1 ^ -1 Mod Tesztszám2
   • Csak a prímszámok esetében (nem prímszámok esetén lesz eredmény, de ez nem az MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (TestNumber1 ^ (TestNumber-2))% TestNumber2
   • Így:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Hozzon létre egy bináris táblázatot minden egyes MMI-hez a Modulus Log2-ig
   • Az MMI1 számára
     • F (1) = Tesztszám2% Tesztszám1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Tesztszám1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Tesztszám1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% tesztszám1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% tesztszám1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Tesztszám1 = 1 * 1% 35 = 1
   • Számítsa ki a TestNumber1 - 2 bináris logaritmusát
     • 35 -2 = 33 (10001) 2. bázis
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 Mod 35
     • MMI1 = 27
   • Az MMI2 számára
     • F (1) = Tesztszám1% Tesztszám2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% tesztszám2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% tesztszám2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% tesztszám2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% tesztszám2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% tesztszám2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% tesztszám2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% tesztszám2 = 35 * 35 mod 97 = 61
   • Számítsa ki a TestNumber2 - 2 bináris logaritmusát
     • 97 - 2 = 95 = (1011111) 2. bázis
     • 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. Számítsa ki (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Válasz = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Válasz = (2619 + 4270)% 3395
   • Válasz = 99
6. Ellenőrizze, hogy a "TestNumber1" nem prime1
   • Számítsa ki (Válasz - Adatok1)% Tesztszám1
   • 99 -1 % 35 = 28
   • Mivel 28 nagyobb, mint 0, 35 nem elsődleges
7. Ellenőrizze, hogy a TestNumber2 elsődleges-e
   • Számítsa ki (Válasz - Adat2)% Teszt2
   • 99 - 2 % 97 = 0
   • Mivel a 0 értéke 0, a 97 potenciális prímszám
8. Ismételje meg az 1–7. Lépést még legalább kétszer.
   • Ha a 7. lépés értéke 0:
     • Használjon másik "TestNumber1" -t, ha a TestNumber1 nem elsődleges.
     • Használjon másik TestNumber1-et, ahol a TestNumber1 valóban elsődleges. Ebben az esetben a 6. és 7. lépés egyenlő 0-val.
     • Különböző adatpontokat használjon az data1 és az data2 számára.
   • Ha a 7. lépés mindig egyenlő 0-val, akkor nagyon valószínű annak valószínűsége, hogy a 2. szám prímszám.
   • Az 1–7. Lépések köztudottan helytelenek bizonyos esetekben, amikor az első szám nem prím, a második pedig a nem prímszám „Tesztszám1” prímtényezője. Ez minden olyan helyzetben működik, ahol mindkét szám elsődleges.
   • Az 1–7. Lépés megismétlődése az oka, hogy van néhány forgatókönyv, ahol akkor is, ha a TestNumber1 nem prím és a TestNumber2 nem prím, a 7. lépés bármelyik száma még mindig nulla. Ezek az állapotok ritkák. A TestNumber1 másik nem prímszámra váltásával, ha a TestNumber2 nem prím, a TestNumber2 a 7. lépésben már nem lesz nulla, kivéve azt az esetet, ahol a "TestNumber1" a TestNumber2 tényezője, a prímszámok mindig nullaak lesznek. 7. lépés.

Tippek

• Az 1000 alatti 168 prímszám: 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
• Ha a felosztási kísérlet lassabb, mint a kifinomultabb módszerek, akkor is kisebb számok esetén hatékony. Még a nagyobb számok tesztelése során sem ritka, hogy a fejlettebb módszerekre való áttérés előtt először ellenőrizzük a kis számokat.

Szükségletek

• Papír, toll, ceruza és / vagy számológép az edzéshez