Tartalom

• Lépések
• 1/3 rész: Az egyszerűség tesztjei
• Rész 3 /3: Hogyan működnek az egyszerűségi tesztek
• Rész 3 /3: A kínai maradék tétel használata
• Tippek
• Mire van szükséged

A prímszámok olyan számok, amelyek csak önmagukban és 1 -gyel oszthatók. Az összes többi számot összetett számoknak nevezzük. Számos módszer létezik annak meghatározására, hogy egy szám elsődleges -e, és mindegyiknek megvan a maga előnye és hátránya. Egyrészt néhány módszer nagyon pontos, de meglehetősen bonyolult, ha nagy számokkal van dolgunk. Másrészt vannak sokkal gyorsabb módszerek, de ezek helytelen eredményekhez vezethetnek. A megfelelő módszer kiválasztása attól függ, hogy milyen nagy számokkal dolgozik.

Lépések

1/3 rész: Az egyszerűség tesztjei

Jegyzet: minden képletben n az ellenőrizendő számot jelöli.

1. 1 Osztók felsorolása. Elég osztani n minden prímszámra 2 -től a kerekített értékig (${ displaystyle { sqrt {n}}}$).
2. 2 Fermat kis tétele. Figyelmeztetés: néha a teszt hamisan azonosítja az összetett számokat prímként, még az a minden értékére is.
   • Válasszunk egy egész számot aúgy, hogy 2 ≤ a ≤ n - 1.
   • Ha a (mod n) = a (mod n), akkor a szám valószínűleg prím. Ha az egyenlőség nem teljesül, az n szám összetett.
   • Ellenőrizze a megadott egyenlőséget több érték esetén ahogy növelje annak valószínűségét, hogy a tesztelt szám valóban prímszám.
3. 3 Miller-Rabin teszt. Figyelmeztetés: néha, bár ritkán, a több értéke esetén a teszt hamisan azonosítja az összetett számokat prímként.
   • Keresse meg az s és d mennyiségeket ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Válasszon egy egész számot a 2 ≤ a ≤ n - 1 tartományban.
   • Ha a = +1 (mod n) vagy -1 (mod n), akkor n valószínűleg prímszám. Ebben az esetben menjen a teszt eredményéhez. Ha az egyenlőség nem áll fenn, folytassa a következő lépéssel.
   • Négyszögletes válasz (${ displaystyle a ^ {2d}}$). Ha -1 -et kap (mod n), akkor n valószínűleg prímszám. Ebben az esetben menjen a teszt eredményéhez. Ha az egyenlőség nem sikerül, ismételje meg (${ displaystyle a ^ {4d}}$ és így tovább) addig ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Ha valamilyen lépésben a négyzet négyzete után nem ${ displaystyle pm 1}$ (mod n), +1 (mod n) van, tehát n összetett szám. Ha ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), akkor n nem prím.
   • Vizsgálati eredmény: ha n megfelel a teszten, ismételje meg más értékeknél is ahogy növelje a bizalmat.

Rész 3 /3: Hogyan működnek az egyszerűségi tesztek

1. 1 Osztók felsorolása. Értelemszerűen a szám n csak akkor egyszerű, ha nem osztható 2 -vel és más egész számokkal, kivéve 1 -et és önmagát. A fenti képlet lehetővé teszi a felesleges lépések eltávolítását és az idő megtakarítását: például miután ellenőrizte, hogy egy szám osztható -e 3 -mal, nem kell ellenőrizni, hogy osztható -e 9 -gyel.
   • A padló (x) függvény az x -et kerekíti az x -nél kisebb vagy azzal egyenlő legközelebbi egész számhoz.
2. 2 Ismerje meg a moduláris aritmetikát. Az "x mod y" művelet (a mod a latin "modulo" szó, azaz "modul" rövidítése) azt jelenti, hogy "oszd meg x -et y -val, és keresd meg a maradékot". Más szóval, moduláris aritmetikában, egy bizonyos érték elérésekor, amelyet ún modul, a számok ismét "nullára" fordulnak. Például az óra visszaszámol a 12 -es modullal: 10, 11 és 12 órát mutat, majd visszatér 1 -re.
   • Sok számológép rendelkezik modkulccsal. A szakasz végén bemutatjuk, hogyan kell manuálisan kiszámítani ezt a funkciót nagy számok esetén.
3. 3 Ismerje meg Fermat kis tételének buktatóit. Minden szám, amelyhez a vizsgálati feltételek nem teljesülnek, összetett, de a többi szám csak valószínűleg egyszerűek. Ha el szeretné kerülni a helytelen találatokat, keressen n a "Carmichael -számok" (ezen tesztnek megfelelő összetett számok) és a "Fermat pszeudoprime -számok" listájában (ezek a számok csak bizonyos értékek esetén felelnek meg a vizsgálati feltételeknek a).
4. 4 Ha kényelmes, használja a Miller-Rabin tesztet. Bár ez a módszer meglehetősen nehézkes a kézi számításokhoz, gyakran használják számítógépes programokban. Elfogadható sebességet és kevesebb hibát biztosít, mint a Fermat módszer. Az összetett szám nem számít prímszámnak, ha a számításokat több mint ¼ értékre végzik a... Ha véletlenszerűen választ különböző értékeket a és mindegyikük esetében a teszt pozitív eredményt ad, meglehetősen magabiztosan feltételezhetjük, hogy n prímszám.
5. 5 Nagy számok esetén használjon moduláris számtant. Ha nincs kéznél mod -számológép, vagy a számológépet nem tervezték ilyen nagy számok kezelésére, használja a teljesítménytulajdonságokat és a moduláris számtant a számítások megkönnyítése érdekében. Az alábbiakban egy példa erre ${ displaystyle 3 ^ {50}}$ mod 50:
   • Írja át a kifejezést kényelmesebb formában: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. A kézi számítások további egyszerűsítéseket igényelhetnek.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}})$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Itt figyelembe vettük a moduláris szorzás tulajdonságát.
   • ${ displaystyle 3 ^ {25}}$ mod 50 = 43.
   • ${ displaystyle (3 ^ {25}})$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ displaystyle (43 * 43)}$ mod 50.
   • ${ displaystyle = 1849}$ mod 50.
   • ${ displaystyle = 49}$.

Rész 3 /3: A kínai maradék tétel használata

1. 1 Válasszon két számot. Az egyik számnak összetettnek, a másiknak pedig pontosan olyannak kell lennie, amelyet az egyszerűség érdekében tesztelni szeretne.
   • Szám1 = 35
   • 2. szám = 97
2. 2 Válasszon két értéket, amelyek nagyobbak nullánál, illetve kisebbek, mint a Number1 és Number2 számok. Ezek az értékek nem lehetnek egyformák.
   • Érték1 = 1
   • Érték2 = 2
3. 3 Számítsa ki az MMI -t (Mathematical Multiplicative Inverse) a szám1 és szám2 számára.
   • Számítsa ki az MMI -t
     • MMI1 = Szám2 ^ -1 Mod Szám1
     • MMI2 = Szám1 ^ -1 Mod Szám2
   • Csak prímszámok esetén (ez számot ad az összetett számokhoz, de nem ez lesz az MMI -je):
     • MMI1 = (Szám2 ^ (Szám1-2))% Szám1
     • MMI2 = (Szám1 ^ (Szám2-2))% Szám2
   • Például:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Hozzon létre egy táblázatot minden MMI -hez a log2 modulokig:
   • Az MMI1 számára
     • F (1) = szám2% szám1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Szám1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Szám1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Szám1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Szám1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Szám1 = 1 * 1% 35 = 1
   • Páros számok kiszámítása 1 - 2
     • 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) = szám1% szám2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Szám2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Szám2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Szám2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Szám2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Szám2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Szám2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Szám2 = 35 * 35 mod 97 = 61
   • Számítsa ki a 2-2 páros számot
     • 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. 5 Számítás (Érték1 * Szám2 * MMI1 + Érték2 * Szám1 * MMI2)% (Szám1 * Szám2)
   • Válasz = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Válasz = (2619 + 4270)% 3395
   • Válasz = 99
6. 6 Ellenőrizze, hogy a Number1 nem prím
   • Számítsa ki (Válasz - Érték1)% Szám1
   • 99 – 1 % 35 = 28
   • Mivel 28 nagyobb, mint 0, a 35 nem prímszám.
7. 7 Ellenőrizze, hogy a Number2 elsődleges.
   • Számítsa ki (Válasz - Érték2)% Szám2
   • 99 – 2 % 97 = 0
   • Mivel a 0 0, a 97 valószínűleg prímszám.
8. 8 Ismételje meg az 1-7. Lépéseket még legalább kétszer.
   • Ha a 7. lépésben 0 -t kap:
     • Használjon másik számot1, ha a szám1 nem prímszám.
     • Használjon másik számot1, ha a szám1 prímszám. Ebben az esetben a 6. és 7. lépésben 0 -t kell kapnia.
     • Használjon különböző Jelentést1 és Jelentést2.
   • Ha a 7. lépésben következetesen 0 -t kap, akkor a 2 -es szám nagy valószínűséggel prímszám.
   • Az 1-7. Lépések hibát okozhatnak, ha a Number1 nem prímszám, a Number2 pedig a Number1 osztója. A leírt módszer minden esetben működik, ha mindkét szám prím.
   • Az 1-7. Lépést meg kell ismételni, mert bizonyos esetekben, még akkor is, ha a Number1 és a Number 2 nem prímszám, a 7. lépésben 0 -t kap (egy vagy mindkét szám esetén). Ez ritkán fordul elő.Válasszon másik számot1 (összetett), és ha a szám2 nem prímszám, akkor a szám2 nem lesz nulla a 7. lépésben (kivéve azt az esetet, amikor a szám1 osztja a szám2 -t - itt a prímszámok mindig egyenlők nullával a 7. lépésben).

Tippek

• Prímszámok 168 és 1000 között: 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.
• Bár a nyers erő tesztelése fárasztó teszt, ha nagy számokkal dolgozik, kis számok esetén meglehetősen hatékony. Még nagy számok esetén is kezdje a kis osztók tesztelésével, majd folytassa a kifinomultabb módszerekkel a számok egyszerűségének ellenőrzésére (ha nem talál kis osztókat).

Mire van szükséged

• Papír, toll vagy számítógép