Sisu

• Astuda
• 1. meetod 4st: proovige jagada
• 2. meetod 4-st: Fermati väikese teoreemi kasutamine
• Meetod 3/4: Milleri-Rabini testi kasutamine
• Meetod 4/4: Hiina ülejäänud teoreemi kasutamine
• Näpunäited
• Vajadused

Algarvud on arvud, mis jagunevad ainult iseenesest ja mida nimetatakse 1 - muudeks numbriteks ühend numbrid. Mis puutub numbri algarvu testimisse, siis on mitu võimalust. Mõned neist meetoditest on suhteliselt lihtsad, kuid suuremate arvude puhul pole need üldse praktilised. Muud sageli kasutatavad testid on tegelikult ühel põhinevad täielikud algoritmid tõenäosus kes mõnikord arvavad ekslikult arvu peamiseks. Lugege edasi 1. sammust, et teada saada, kuidas ennast proovida, kui tegemist on algarvuga.

Astuda

1. meetod 4st: proovige jagada

Jagamise proovimine on numbri testimiseks kaugelt kõige lihtsam viis. Väikeste numbrite puhul on see tavaliselt ka kiireim viis. Testi aluseks on algarvu määratlus: arv on algarv, kui see jagub ainult iseenesest ja 1.

1. Oletame n on number, mida soovite testida. Jagage arv n kõigi võimalike jagatavate täisarvudega. Suuremate arvude, näiteks n = 101, puhul on ülipraktiline jagada mis tahes võimaliku täisarvuga, mis on väiksem kui n. Õnneks on testitavate tegurite arvu vähendamiseks mitu nippi.
2. Tehke kindlaks, kas n ühtlane. Kõik paarisarvud on täielikult jagatavad 2-ga. Seega, kui n on paaris, võite seda öelda n on liitarv (ja seega mitte algarv). Arvu paarisarvu kiireks tuvastamiseks peate tähelepanu pöörama ainult viimasele numbrile. Kui viimane number on 2, 4, 6, 8 või 0, siis on see arv paaris ja mitte algarv.
   • Ainus erand sellest reeglist on number 2 ise, mis on ka peamine, kuna see on iseenesest jagatav ja 1. 2 on ainus ühtlane algarv.
3. Osa n mis tahes arvuga vahemikus 2 kuni n-1. Kuna algarvul pole muid tegureid peale tema enda ja 1 ning kuna täisarvutegurid on väiksemad kui nende korrutis, saab väiksema kui n ja suurema kui 2 täisarvu jagatavuse kontrollimisel kindlaks, kas n on algarv. Alustame pärast 2, sest paarisarvud (2 korrutised) ei saa olla algarvud. See pole kaugeltki tõhus viis testimiseks, nagu näete allpool.
   • Näiteks kui me sooviksime selle meetodi abil testida, kas 11 on põhiline või mitte, jagaksime 11 3, 4, 5, 6, 7, 8, 9 ja 10-ga, otsides täisarvu vastuseta ülejäänu. Kuna ükski neist numbritest ei mahu täielikult 11-sse, võime öelda, et 11 on üks on peamine.
4. Aja kokkuhoiuks testige ainult kuni sqrt (n), üles ümardatud. Numbri n testimine kõigi arvude vahemikus 2 kuni n-1 kontrollimisega võib kiiresti võtta palju aega. Näiteks kui me tahtsime kontrollida, kas selle meetodi puhul on algarv 103, peame jagama arvuga 3, 4, 5, 6, 7 ... jne, kuni 102! Õnneks pole vaja niimoodi katsetada. Praktikas on vaja testida ainult tegureid 2 ja n ruutjuure vahel. Kui n ruutjuur pole arv, ümardage see lähima täisarvuni ja testige selle arvuga. Vt selgitust allpool.
   • Uurime tegureid 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 ja 100 × 1. Pange tähele, et pärast 10 × 10 on tegurid samad kui see on 10 × 10, siis ainult siis pööratud. Üldiselt võime ignoreerida tegureid, mis on suuremad kui sqrt (n), kuna need on lihtsalt jätkud teguritele, mis on väiksemad kui sqrt (n).
   • Proovime näidet. Kui n = 37, siis pole meil vaja kõiki numbreid 3 kuni 36 testida, et teha kindlaks, kas n on algarv. Selle asemel peame lihtsalt vaatama numbreid 2 ja sqrt (37) vahel (ümardatuna ülespoole).
     • sqrt (37) = 6,08 - ümardame selle kuni seitsmeni.
     • 37 ei ole täielikult jagatav arvudega 3, 4, 5, 6 ja 7 ning seega võime kindlalt väita, et see on üks algarv on.
5. Veelgi suurema aja kokkuhoiuks kasutame ainult peamisi tegureid. Testimisprotsessi on võimalik jagada veelgi lühemaks jagades need tegurid, mis pole algarvud. Definitsiooni järgi saab iga liitarvu väljendada kahe või enama algarvu korrutisena. Nii et numbri n jagamine liitarvuga ei ole vajalik - see on samaväärne mitu korda algarvudega jagamisega. Niisiis, saame veelgi kitsendada võimalike tegurite loetelu ainult algarvudele, mis on väiksemad kui sqrt (n).
   • See tähendab, et kõik paarisfaktorid ja ka algarvude kordsed tegurid saab vahele jätta.
   • Näiteks proovime kindlaks teha, kas 103 on peamine või mitte. Ruutjuur 103 on 11 (ümardatud ülespoole). Algarvud vahemikus 2 kuni 11 on 3, 5, 7 ja 11. 4, 6, 8 ja 10 on paarisarvud ja 9 on 3 korrutis, algarv, nii et võime selle vahele jätta. Seda tehes vähendasime võimalike tegurite loendit vaid 4 numbrini!
     • 103 ei ole täielikult jagatav kas 3, 5, 7 ega 11-ga, seega teame nüüd, et 103 on üks algarv on.

2. meetod 4-st: Fermati väikese teoreemi kasutamine

Aastal 1640 pakkus prantsuse matemaatik Pierre de Fermat esmalt välja teoreemi (nüüd tema nime saanud), millest võib olla palju abi, kui otsustatakse, kas arv on algarv. Tehniliselt on Fermati test mõeldud kontrollima, kas number on kompositsioon, mitte algarv. Seda seetõttu, et test võib "absoluutse kindlusega" näidata, et number on liit, kuid ainult "tõenäosus", et arv on algarv. Fermati väike teoreem on kasulik olukordades, kus jagamise proovimine on ebapraktiline ja kui on olemas loend numbritest, mis on teoreemi erandid.

1. Oletame n number on testimiseks. Selle testi abil saate kindlaks teha, kas antud arv n on algarv. Kuid nagu eespool märgitud, võib see teoreem aeg-ajalt ekslikult iseloomustada mõnda ühendit algarvuna. Oluline on seda arvesse võtta ja kontrollida oma vastust, mida selgitatakse allpool.
2. Valige täisarv a vahemikus 2 kuni n-1 (kaasa arvatud). Teie valitud täpne täisarv pole oluline. Kuna a parameetrid hõlmavad 2 ja n-1, saate neid ka kasutada.
   • Näide: kas 100 on peamine või mitte. Oletame, et võtame 3 testväärtusena - see on vahemikus 2 kuni n-1, nii et see on piisav.
3. arvutama a (mod n). Selle väljendi väljatöötamine nõuab teatud teadmisi matemaatilisest süsteemist, mida nimetatakse modulaarne matemaatika. Moodulmatemaatikas pöörduvad arvud teatud väärtuse saavutamisel nulli, mida tuntakse ka kui moodul. Sellest võib mõelda nagu kellast: lõpuks naaseb kellaosuti kella 12 pärast kella 12, mitte kella 13 juurde. Moodul on märgitud kui (mod n). Nii et selles etapis arvutate a mooduliga n.
   • Teine meetod on arvutada a, seejärel jagada see n-ga, seejärel kasutada ülejäänud osa vastusena. Spetsiaalsed moodulfunktsiooniga kalkulaatorid võivad suurte arvude jagamisel olla väga kasulikud, sest nad saavad kohe arvutada jaotuse ülejäänud osa.
   • Kasutades oma näites sellist kalkulaatorit, näeme, et 3/100 on ülejäänud 1. Seega on 3 (mod 100) 1.
4. Kui arvutame selle käsitsi, kasutame eksponenti lühivorminguna. Kui teil pole mooduli funktsiooniga kalkulaatorit, kasutage jäägi määramise protseduuri hõlbustamiseks eksponendiga tähistust. Vaata allpool:
   • Meie näites arvutame 3 mooduliga 100. 3 on väga-väga suur arv - 515 377 520 732 010 331 036 461 129 765 621 272 702 107 522 001 - nii suur, et temaga töötamine muutub väga raskeks. Selle asemel, et kasutada 48-kohalist vastust kolmeks, kirjutame selle parem eksponendina, nii et (((((((3)*3))))*3)). Pidage meeles, et eksponendi eksponendi võtmine korrutab eksponente ((x) = x).
     • Nüüd saame ülejäänud määrata. Alustage sisemise sulgude komplekti ((((((((3) * 3)))) * * 3)) lahendamisest ja liikuge välja, jagades iga sammu 100-ga. Kui oleme ülejäänu leidnud, kasutame seda pigem järgmiseks sammuks kui tegelikuks vastuseks. Vaata allpool:
       • ((((((((9) * 3)))) * * 3)) - 9/100-l pole ülejäänud osa, nii et võime jätkata.
       • ((((((27)))) * 3)) - 27/100-l pole ülejäänut, nii et saame edasi liikuda.
       • (((((729))) * 3)) - 729/100 = 7 R 29. Meie ülejäänud on 29. Jätkame järgmise sammuga, mitte 729.
       • ((((29=841)) * 3)) - 841/100 = 8 R 41. Ülejäänud 41 kasutame järgmises etapis uuesti.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Ülejäänud 81 kasutame järgmises etapis.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Ülejäänud 43 kasutame järgmises etapis.
       • (43 = 1849) - 1849/100 = 18 R 49. Ülejäänud 49 kasutame järgmises etapis.
       • 49 = 2401 - 2401/100 = 24 R 1. meie lõplik jääk on 1. Teisisõnu, 3 (mod 100) = 1. Pange tähele, et see on sama vastus, nagu arvutasime eelmises etapis!
5. Uuri kas a (mod n) = a (mod n). Kui ei, on n ühend. Kui see on tõsi, siis n ilmselt (aga pole kindel) algarv. Testi kordamine a erinevate väärtustega võib muuta tulemuse kindlamaks, kuid on haruldasi liitarvusid, mis rahuldavad Fermati teoreemi kõik a väärtusi. Neid nimetatakse Carmichaeli numbriteks - neist väikseim on 561.
   • Meie näites 3 (mod 100) = 1 ja 3 (mod 100) = 3,1 ≠ 3, seega võime öelda, et 100 on liitarv.
6. Kasutage Carmichaeli numbreid, et oma tulemuses kindel olla. Enne jätkamist teadmine, millised numbrid vastavad Carmichaeli seeriale, võib säästa palju muret selle pärast, kas number on peamine. Üldiselt on Carmichaeli numbrid üksikute algarvude korrutis, kus kõigi algarvude puhul kehtib see, et kui p on jagaja n, siis on ka p-1 jagaja n-1. Carmichaeli numbrite veebiloend võib olla Fermati väikese teoreemi abil väga kasulik, et teha kindlaks, kas arv on algarv.
   
   

Meetod 3/4: Milleri-Rabini testi kasutamine

Miller-Rabini test töötab samamoodi nagu Fermati väike teoreem, kuid tegeleb paremini mittestandardsete numbritega nagu Carmichaeli numbrid.

1. Oletame n on paaritu arv, mida soovime proovida. Nagu ülalkirjeldatud meetodites, on ka n muutuja, mille peame määrama.
2. Rõhk n-1 kujul 2 × d mille juures d on veider. Arv n on algarv, kui see on paaritu. Nii et n - 1 peab olema ühtlane. Kuna n - 1 on paaris, saab selle kirjutada kahekordse paaritu arvuna. Niisiis, 4 = 2 × 1; 80 = 2 × 5; ja nii edasi.
   • Oletame, et tahame kindlaks teha, kas n = 321 on peamine. 321 - 1 = 320, mida saame väljendada kui 2 × 5.
     • Sel juhul on sobiv arv n = 321. N - 1 määramine n = 371 korral võib nõuda d jaoks suurt väärtust, mis muudab kogu protsessi hilisemas etapis raskemaks. 371 - 1 = 370 = 2 × 185
3. Valige suvaline number a vahemikus 2 kuni n-1. Teie valitud täpne arv pole oluline - lihtsalt see peab olema väiksem kui n ja suurem kui 1.
   • Meie näites n = 321 valime a = 100.
4. arvutama a (mod n). Kui a = 1 või -1 (mod n), siis möödub n Milleri-Rabini test ja on ilmselt algarv. Nagu Fermati väikese teoreemi puhul, ei saa selle testiga absoluutse kindlusega kindlaks määrata arvu esmasust, kuid see nõuab täiendavaid katseid.
   • Meie näites n = 321, a (mod n) = 100 (mod 321). 100 = 10 000 000 000 (mod 321) = 313. Ülejäänud osa 100/321 leidmiseks kasutame spetsiaalset kalkulaatorit või varem kirjeldatud astendiga lühikest meetodit.
     • Kuna me pole saanud 1 või -1, ei saa me kindlalt öelda, et n on algarv. Kuid meil on veel vaja teha - loe edasi.
5. Kuna tulemus ei ole võrdne 1 või -1, arvutage a, a, ... ja nii edasi, kuni ad. Arvutage tõstetud väärtus d korda, kuni 2. Kui üks neist on võrdne 1 või -1 (mod n), siis möödub n Miller-Rabin testib ja on ilmselt parim. Kui olete kindlaks teinud, et n läbib testi, siis kontrollige oma vastust (vt allpool olevat sammu). Kui n ühestki neist testidest läbi kukub, on see üks komponeeritud number.
   • Meeldetuletuseks: meie näites on a väärtus 100, s väärtus 6 ja d 5. Jätkame testimist, nagu allpool näidatud:
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 64,64 ≠’ 1 või -1. Edasi rahulikult edasi.
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 244,244 ≠ 1 või -1.
     • Siinkohal võime peatuda. s - 1 = 6 - 1 = 5. Nüüd oleme jõudnud 4d = 2-ni ja 2-kordse d-väärtuse alla 5d pole. Kuna ükski meie arvutustest ei vastanud väärtusele 1 ega -1, võime öelda, et n = 321 üks komponeeritud number on.
6. Kui n läbib Milleri-Rabini testi, korrake teiste väärtuste korral a. Kui olete leidnud, et n väärtus võib olla algväärtus, proovige testi tulemuse kinnitamiseks uuesti a-ga erineva juhusliku väärtusega. Kui n on tegelikult algarv, kehtib see a väärtuse mis tahes väärtuse puhul. Kui n on liitarv, ebaõnnestub see kolmveerandi a väärtustest. See annab teile suurema kindluse kui Fermati väike teoreem, kus teatud liitnumbrid (Carmichaeli numbrid) läbivad testi mis tahes a väärtuse jaoks.

Meetod 4/4: Hiina ülejäänud teoreemi kasutamine

1. Valige kaks numbrit. Üks numbritest ei ole algarv ja teine ​​on arv, mida testitakse primaalsuse järgi.
   • "Katse number1" = 35
   • Katse number2 = 97
2. Valige kaks andmepunkti, mis on suuremad kui null ja väiksemad kui TestNumber1 ja TestNumber2. Nad ei saa olla üksteisega võrdsed.
   • Andmed1 = 1
   • Andmed2 = 2
3. Arvutage MMI (matemaatiline multiplikaatne pöördvõrdeline väärtus) testi numbri 1 ja testi numbri 2 jaoks
   • Arvutage MMI
     • MMI1 = testi number2 ^ -1 Modi testi number1
     • MMI2 = testi number1 ^ -1 Modi testi number2
   • Ainult algarvude puhul (mitte-algarvude puhul on tulemus, kuid see pole MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (TestNumber1 ^ (TestNumber-2))% TestNumber2
   • Niisiis:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Looge iga MMI jaoks binaartabel kuni mooduli Log2
   • MMI jaoks1
     • F (1) = testi number2% testi number1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% testi arv1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% testi arv1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% testi arv1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% testi arv1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% testi arv1 = 1 * 1% 35 = 1
   • Arvutage testNumber1 - 2 binaarlogaritm
     • 35 -2 = 33 (10001) alus 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 Mod 35
     • MMI1 = 27
   • MMI2 jaoks
     • F (1) = testi number 1% testi arv2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% testi arv2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% testi arv2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% testi arv2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% testi arv2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% testi arv2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% testi arv2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% testi arv2 = 35 * 35 mod 97 = 61
   • Arvutage testNumber2 - 2 binaarlogaritm
     • 97 - 2 = 95 = (1011111) alus 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. Arvuta (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Vastus = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Vastus = (2619 + 4270)% 3395
   • Vastus = 99
6. Veenduge, et "TestNumber1" pole algarv1
   • Arvutage (vastus - andmed1)% testi arv1
   • 99 -1 % 35 = 28
   • Kuna 28 on suurem kui 0, pole 35 peamine
7. Kontrollige, kas TestNumber2 on peamine
   • Arvutage (vastus - andmed2)% testi arv2
   • 99 - 2 % 97 = 0
   • Kuna 0 on 0, on 97 potentsiaalne algarv
8. Korrake samme 1 kuni 7 veel vähemalt kaks korda.
   • Kui 7. samm on võrdne 0:
     • Kui TestNumber1 ei ole algarv, kasutage teistsugust "TestNumber1".
     • Kasutage teist TestNumber1, kus TestNumber1 on tegelikult algarv. Sel juhul on sammud 6 ja 7 võrdsed 0-ga.
     • Andmete1 ja andmete2 jaoks kasutage erinevaid andmepunkte.
   • Kui samm 7 on alati võrdne 0-ga, siis on tõenäosus, et number 2 on algarv, väga suur.
   • Sammud 1 kuni 7 on teatavatel juhtudel valed, kui esimene number pole algarv ja teine ​​on algarvu "Test Number1" algtegur. See töötab kõigis stsenaariumides, kus mõlemad numbrid on algarvud.
   • Etappe 1 kuni 7 korratakse seetõttu, et on olemas mõned stsenaariumid, kus isegi siis, kui TestNumber1 pole algarv ja TestNumber2 pole algarv, on kumbki sammust 7 saadud number ikkagi null. Need seisundid on haruldased. Kui TestNumber1 muudetakse peaarvuks, siis kui TestNumber2 ei ole algarv, ei võrdu TestNumber2 enam punktis 7. Välja arvatud juhul, kui "TestNumber1" on TestNumber2 tegur, on algarvud alati nullis. 7. samm.

Näpunäited

• 168 algarvu alla 1000 on: 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
• Kui proovite jagada on aeglasem kui keerukamad meetodid, on see väiksemate arvude jaoks siiski tõhus. Isegi suuremate arvude testimisel pole haruldane, et enne arenenumatele meetoditele üleminekut kontrollitakse esmalt väikseid numbreid.

Vajadused

• Trennimiseks paber, pastakas, pliiats ja / või kalkulaator