Ako zistiť, či je číslo prvočíslo (s obrázkami)

Prvočísla sú čísla deliteľné len samými sebou a 1; všetky ostatné sa nazývajú zložené čísla. Hoci existuje množstvo spôsobov testovania prvočíselnosti, existujú kompromisy. dokonalé testy existujú, ale sú extrémne pomalé pre veľké čísla, zatiaľ čo oveľa rýchlejšie môžu poskytnúť falošné výsledky. Tu je niekoľko možností, z ktorých si môžete vybrať v závislosti od toho, aké veľké číslo testujete.

Časť 1 z 3:Testy prvočísel

Poznámka: Vo všetkých vzorcoch, n je číslo, ktoré sa testuje na prvočíselnosť.

Skúšobný test delenia. Rozdeľte n každým prvočíslom od 2 do floor(

n{\displaystyle {\sqrt {n}}

).


Fermatova malá veta. Upozornenie: falošne pozitívne výsledky sú možné aj pre všetky hodnoty a.

  • Zvoľte celočíselnú hodnotu pre a tak, že 2 ≤ a ≤ n – 1.
  • Ak an (mod n) = a (mod n), potom n je pravdepodobne prvočíslo. Ak to nie je pravda, n nie je prvočíslo.
  • Opakujte s rôznymi hodnotami a na zvýšenie dôvery v prvočíselnosť


Miller-Rabinov test. Upozornenie: falošne pozitívne výsledky sú možné, ale zriedkavo pre viacero hodnôt a.

  • Nájdite také hodnoty s a d, aby
    n1=2sd{\displaystyle n-1=2^{s}*d}

    .

  • Zvoľte celočíselnú hodnotu pre a tak, že 2 ≤ a ≤ n – 1.
  • Ak ad = +1 (mod n) alebo -1 (mod n), potom n je pravdepodobne prvočíslo. Prejsť na výsledok testu. V opačnom prípade prejdite na ďalší krok.
  • Odpočítajte svoju odpoveď na druhú stranu (
    a2d{\displaystyle a^{2d}}

    ). Ak sa rovná -1 (mod n), potom n je pravdepodobne prvočíslo. Prejsť na výsledok testu. V opačnom prípade opakujte (

    a4d{\displaystyle a^{4d}}

    atď.), kým

    a2s1d{\displaystyle a^{2^{s-1}d}}

    .

  • Ak niekedy odmocníte číslo, ktoré nie je
    ±1{\displaystyle \pm 1}

    (mod n) a skončíte s výsledkom +1 (mod n), potom n nie je prvočíslo. Ak

    a2s1d±1{\displaystyle a^{2^{s-1}d}\neq \pm 1}

    (mod n), potom n nie je prvočíslo.

  • Výsledok testu: Ak n prejde testom, zopakujte ho s rôznymi hodnotami a na zvýšenie dôvery.

Druhá časť z 3:Pochopenie testovania prvočísel

Pochopte metódu pokusného delenia. Podľa definície primality, n je prvočíslo len vtedy, ak sa nedá rovnomerne rozdeliť celými číslami 2 alebo väčšími. Uvedený vzorec šetrí čas tým, že odstraňuje zbytočné testy (e.g. po testovaní 3 nie je potrebné testovať 9).

  • Floor(x) zaokrúhli x na najbližšie celé číslo ≤ x.


Pochopiť modulárnu aritmetiku. Operácia „x mod y“ (skratka pre „modulo“) znamená „vydeľ x y a nájdi zvyšok.“[1]
Inými slovami, v modulárnej aritmetike sa čísla „obrátia“ späť k nule po dosiahnutí určitej hodnoty, tzv modul. Hodiny počítajú modulo 12: idú od 10 cez 11 až po 12 a potom sa vrátia späť k 1.

  • Mnohé kalkulačky majú tlačidlo mod, ale pozri koniec tejto časti, kde sa dozvieš, ako to vyriešiť ručne pre veľké čísla.


Poznajte nástrahy Fermatovej malej vety. Všetky čísla, ktoré týmto testom neprešli, sú zložené (nie sú prvočíselné), ale bohužiaľ čísla, ktoré týmto testom prešli, sú len pravdepodobne prvočísla. Ak si chcete byť istí, že sa vyhnete falošne pozitívnym výsledkom, hľadajte n na zozname „Carmichaelových čísel“ (ktoré týmto testom vždy prejdú) a „Fermatových pseudoprím“ (ktoré týmto testom prejdú len pre niektoré hodnoty a).[2]


Použite Millerov-Rabinov test vždy, keď je to praktické. Hoci je tento test zdĺhavý na ručné vykonanie, bežne sa používa v softvéri. Tento postup sa dá vykonať praktickou rýchlosťou a dáva menej falošne pozitívnych výsledkov ako Fermatova metóda.[3]
Zložené číslo nikdy nedáva falošne pozitívny výsledok pre viac ako ¼ hodnôt a.[4]
Ak zvolíte niekoľko hodnôt a náhodne a všetky prejdú týmto testom, môžete si byť celkom istí, že n je prvočíslo.


Vykonajte modulárnu aritmetiku pre veľké čísla. Ak nemáte prístup ku kalkulačke s funkciou mod, alebo ak vaša kalkulačka nedokáže zobraziť tak vysoké čísla, použite vlastnosti exponentov a modulárnu aritmetiku, aby ste si uľahčili postup.[5]
Tu je príklad pre

350{\displaystyle 3^{50}}

mod 50:

  • Prepíšte výraz s ľahšie zvládnuteľnými exponentmi:
    (325325){\displaystyle (3^{25}*3^{25})}

    mod 50. (Ak počítate ručne, možno to budete musieť ďalej rozdeliť).

  • (325325){\displaystyle (3^{25}*3^{25})}

    mod 50 =

    (325{\displaystyle (3^{25}}

    mod 50

    325{\displaystyle *3^{25}}

    mod 50) mod 50. (Toto je vlastnosť modulárneho násobenia.)

  • 325{\displaystyle 3^{25}}

    mod 50 = 43.

  • (325{\displaystyle (3^{25}}

    mod 50

    325{\displaystyle *3^{25}}

    mod 50) mod 50 =

    (4343){\displaystyle (43*43)}

    mod 50

  • =1849{\displaystyle =1849}

    mod 50

  • =49{\displaystyle =49}

Časť 3 z 3:Test čínskej zvyškovej vety


Vyberte dve čísla. Jedno z čísel nie je prvočíslo a druhé číslo je číslo, ktoré treba otestovať na prvočíselnosť.

  • „Prime1“ = 35
  • Prime2 = 97


Vyberte dva dátové body, ktoré sú väčšie ako nula a menšie ako prime1 a prime2. Nemôžu sa navzájom rovnať.

  • Data1 = 1
  • Data2 = 2



Vypočítajte MMI (matematickú násobnú inverziu) pre prvočíslo1 a prvočíslo2

  • Výpočet MMI
    • MMI1 = Prime2 ^ -1 Mod Prime1
    • MMI2 = Prime1 ^ -1 mod Prime2
  • Iba pre prvočísla (dá číslo pre neprimárne čísla, ale nebude to jeho MMI):
    • MMI1 = (Prime2 ^ (Prime1-2)) % Prime1
    • MMI2 = (Prime1 ^ (Prime2-2)) % Prime2
  • e.g
    • MMI1 = (97 ^ 33) % 35
    • MMI2 = (35 ^ 95) % 97



Vytvorte binárnu tabuľku pre každú MMI až do log2 modulu

  • Pre MMI1
    • F(1) = Prime2 % Prime1 = 97 % 35 = 27
    • F(2) = F(1) * F(1) % Prime1 = 27 * 27 % 35 = 29
    • F(4) = F(2) * F(2) % Prime1 = 29 * 29 % 35 = 1
    • F(8) = F(4) * F(4) % Prime1 = 1 * 1 % 35 = 1
    • F(16) =F(8) * F(8) % Prime1 = 1 * 1 % 35 = 1
    • F(32) =F(16) * F(16) % Prime1 = 1 * 1 % 35 = 1
  • Vypočítajte binárnu hodnotu Prime1 – 2
    • 35 -2 = 33 (10001) základ 2
    • MMI1 = F(33) = F(32) * F(1) mod 35
    • MMI1 = F(33) = 1 * 27 mod 35
    • MMI1 = 27
  • Pre MMI2
    • F(1) = Prime1 % Prime2 = 35 % 97 = 35
    • F(2) = F(1) * F(1) % Prime2 = 35 * 35 mod 97 = 61
    • F(4) = F(2) * F(2) % Prime2 = 61 * 61 mod 97 = 35
    • F(8) = F(4) * F(4) % Prime2 = 35 * 35 mod 97 = 61
    • F(16) = F(8) * F(8) % Prime2 = 61 * 61 mod 97 = 35
    • F(32) = F(16) * F(16) % Prime2 = 35 * 35 mod 97 = 61
    • F(64) = F(32) * F(32) % Prime2 = 61 * 61 mod 97 = 35
    • F(128) = F(64) * F(64) % Prime2 = 35 * 35 mod 97 = 61
  • Vypočítajte binárne číslo Prime2 – 2
    • 97 – 2 = 95 = (1011111) základ 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



Vypočítajte (Data1 * Prime2 * MMI1 + Data2 * Prime1 * MMI2) % (Prime1 * Prime2)

  • Odpoveď = (1 * 97 * 27 + 2 * 35 * 61) % (97 * 35)
  • Odpoveď = (2619 + 4270) % 3395
  • Odpoveď = 99



Overte, či „Prime1“ nie je prvočíslo

  • Vypočítajte (Odpoveď – Údaje1) % Prime1
  • 99 -1 % 35 = 28
  • Keďže 28 je väčšie ako 0, 35 nie je prvočíslo



Skontrolujte, či Prime2 je Prime

  • Vypočítajte (odpoveď – údaje2) % prvočíslo2
  • 99 – 2 % 97 = 0
  • Keďže 0 sa rovná 0, 97 je potenciálne prvočíslo

  • Opakujte kroky 1 až 7 ešte aspoň dvakrát.

    • Ak je krok 7 rovný 0:
      • Použite iné „prvočíslo1“, kde prvočíslo1 nie je prvočíslo
      • Použite iné prvočíslo 1, kde prvočíslo 1 je skutočné prvočíslo. V tomto prípade by sa kroky 6 a 7 mali rovnať 0.
      • Použite rôzne dátové body pre dáta1 a dáta2.
    • Ak je krok 7 zakaždým 0, existuje extrémne vysoká pravdepodobnosť, že prvočíslo2 je prvočíslo.
    • Je známe, že kroky 1 až 7 v určitých prípadoch zlyhávajú, keď prvé číslo nie je prvočíslo a druhé prvočíslo je násobkom prvočísla „prvočíslo1“. Funguje vo všetkých scenároch, kde sú obe čísla prvočísla.
    • Dôvod, prečo sa kroky 1 až 7 opakujú, je ten, že existuje niekoľko scenárov, keď aj keď prvočíslo1 nie je prvočíslo a prvočíslo2 nie je prvočíslo, krok 7 stále vychádza nulový, pre jedno alebo obe čísla. Tieto okolnosti sú zriedkavé. Zmenou prvočísla1 na iné neprimárne číslo, ak prvočíslo2 nie je primárne, prvočíslo2 sa v kroku 7 rýchlo nebude rovnať nule. S výnimkou prípadu, keď je „prvočíslo1“ násobkom prvočísla2, sa prvočísla v kroku 7 vždy rovnajú nule.
  • Odkazy