Efni.

• Að stíga
• Aðferð 1 af 4: Reyndu að skipta
• Aðferð 2 af 4: Notkun litla setningar Fermats
• Aðferð 3 af 4: Nota Miller-Rabin prófið
• Aðferð 4 af 4: Notaðu kínversku restarsetninguna
• Ábendingar
• Nauðsynjar

Frumtölur eru tölur sem eru aðeins deilanlegar með sjálfum sér og kallast 1 - aðrar tölur efnasamband tölur. Þegar kemur að því að prófa hvort tala sé frum, þá eru nokkrir möguleikar. Sumar þessara aðferða eru tiltölulega einfaldar en alls ekki hagnýtar fyrir stærri tölur. Önnur próf sem oft eru notuð eru í raun heill reiknirit byggð á einni líkur sem líta stundum á ranga tölu sem frumefni. Lestu áfram í skref 1 til að læra að prófa sjálfan þig ef þú ert að fást við frumtölu.

Að stíga

Aðferð 1 af 4: Reyndu að skipta

Að reyna að skipta er lang auðveldasta leiðin til að prófa tölu. Fyrir litlar tölur er það venjulega einnig fljótlegasta leiðin. Prófið byggir á skilgreiningu á frumtölu: tala er frumtala ef hún er aðeins deilanleg af sjálfu sér og 1.

1. Geri ráð fyrir n er númerið sem þú vilt prófa. Deildu tölunni n með öllum mögulegum deilanlegum heiltölum. Fyrir stærri tölur eins og n = 101 er mjög óframkvæmanlegt að deila með mögulegri heiltölu minna en n. Sem betur fer eru nokkur brögð til að fækka þeim þáttum sem á að prófa.
2. Ákveðið hvort n jafnvel. Allar jafnar tölur eru alveg deilanlegar með 2. Þess vegna, ef n er jafnt, geturðu sagt það n er samsett tala (og því ekki frumtala). Til að ákvarða fljótt hvort tala sé jöfn, þarftu aðeins að borga eftir síðustu tölustaf. Ef síðasta tölustafurinn er 2, 4, 6, 8 eða 0, þá er talan jöfn og ekki frum.
   • Eina undantekningin frá þessari reglu er talan 2 sjálf, sem, vegna þess að hún er deilanleg af sjálfu sér og 1, er einnig aðal. 2 er eina jafna blómin.
3. Hluti n með hvaða tölu sem er á milli 2 og n-1. Vegna þess að frumtala hefur enga þætti aðra en sjálfa sig og 1, og vegna þess að heiltöluþættir eru minni en afurð þeirra, að athuga deilanleika heiltölu minna en n og meiri en 2 mun ákvarða hvort n er frumtala. Við byrjum eftir 2 vegna þess að sléttar tölur (margfeldi af 2) geta ekki verið frumtölur. Þetta er langt frá því að vera skilvirk leið til að prófa, eins og þú munt sjá hér að neðan.
   • Til dæmis, ef við vildum nota þessa aðferð til að prófa hvort 11 sé frumefni eða ekki, þá myndum við deila 11 með 3, 4, 5, 6, 7, 8, 9 og 10 og leita að heiltölu án afgangs. Þar sem engin af þessum tölum fellur alveg að 11, getum við sagt að 11 sé ein er aðal.
4. Til að spara tíma skaltu prófa aðeins allt að sqrt (n), námundað. Að prófa tölu n með því að athuga allar tölur milli 2 og n-1 getur fljótt tekið mikinn tíma. Til dæmis, ef við vildum athuga hvort 103 sé aðal með þessari aðferð, þá yrðum við að deila með 3, 4, 5, 6, 7 ... osfrv, allt að 102! Sem betur fer er ekki nauðsynlegt að prófa svona. Í reynd er aðeins nauðsynlegt að prófa þættina milli 2 og ferningsrótar n. Ef kvaðratrót n er ekki tala, hringdu hana í næstu heiltölu og prófaðu að þessari tölu. Sjá hér að neðan til að fá skýringar:
   • Skoðum þættina 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 og 100 × 1. Athugaðu að eftir 10 × 10 eru þættirnir þeir sömu ef það fyrir 10 × 10, aðeins þá velt. Almennt getum við hunsað þætti n stærri en sqrt (n) þar sem þeir eru einfaldlega framhald þátta minna en sqrt (n).
   • Reynum dæmi. Ef n = 37, þá þurfum við ekki að prófa allar tölur frá 3 til 36 til að ákvarða hvort n sé frumtala. Í staðinn þurfum við bara að skoða tölurnar á milli 2 og sqrt (37) (námundaðar upp).
     • sqrt (37) = 6,08 - við ætlum að ná þessu upp í 7.
     • 37 er ekki deilanlegt með 3, 4, 5, 6 og 7 og svo getum við fullviss um að það er eitt prímtala er.
5. Til að spara enn meiri tíma notum við aðeins frumþætti. Það er hægt að gera prófunarferlið með því að deila enn styttra með því að taka ekki með þá þætti sem eru ekki frumtölur. Samkvæmt skilgreiningu getur hver samsett tala verið gefin upp sem afurð tveggja eða fleiri frumtala. Svo að deila tölunni n með samsettri tölu er óþarfi - þetta jafngildir því að deila með frumtölum nokkrum sinnum. Þannig að við getum þrengt listann yfir mögulega þætti frekar í aðeins frumtölur sem eru minni en sqrt (n).
   • Þetta þýðir að hægt er að sleppa öllum jöfnum þáttum, sem og þeim þáttum sem eru margfaldir af frumtölum.
   • Við skulum til dæmis reyna að ákvarða hvort 103 sé aðal eða ekki. Ferningsrótin 103 er 11 (ávalið upp). Frumtölurnar milli 2 og 11 eru 3, 5, 7 og 11. 4, 6, 8 og 10 eru jafnar og 9 er margfeldi af 3, frumtala, svo við getum sleppt því. Með því að gera þetta höfum við fækkað lista okkar yfir mögulega þætti í aðeins 4 tölur!
     • 103 er ekki alveg deilanlegt með 3, 5, 7 eða 11, svo við vitum núna að 103 er einn prímtala er.

Aðferð 2 af 4: Notkun litla setningar Fermats

Árið 1640 lagði franski stærðfræðingurinn Pierre de Fermat fyrst til setningu (nú kennd við hann) sem getur verið mjög gagnlegur við að ákvarða hvort tala sé frumstig eða ekki. Tæknilega séð er próf Fermat ætlað að sannreyna að tala sé samsett, frekar en frumefni. Þetta er vegna þess að prófið getur sýnt með „algerri vissu“ að tala er samsett, en aðeins „líkur“ á að tala sé frum. Litla setning Fermats er gagnleg í aðstæðum þar sem að reyna að skipta er óframkvæmanlegt og þegar listi yfir tölur er í boði sem eru undantekningar frá setningunni.

1. Geri ráð fyrir n fjöldinn er til prófunar. Þú notar þetta próf til að ákvarða hvort tiltekin tala n sé frum. Hins vegar, eins og fram kemur hér að ofan, getur þessi setning einstaka sinnum ranglega lýst einhverju efnasambandi sem frumefni. Mikilvægt er að taka tillit til þessa og athuga svar þitt, sem útskýrt er hér að neðan.
2. Veldu heiltölu a milli 2 og n-1 (innifalið). Nákvæm heildartala sem þú velur skiptir ekki máli. Þar sem breytur fyrir a fela í sér 2 og n-1 er einnig hægt að nota þær.
   • Dæmi: Er 100 prime eða ekki. Segjum að við tökum 3 sem prófgildi - þetta er á milli 2 og n-1, svo það er nægjanlegt.
3. reikna a (mod n). Að vinna úr þessari tjáningu krefst nokkurrar þekkingar á stærðfræðikerfi sem kallast mát stærðfræði. Í stærðfræðilegri stærðfræði fara tölur í núll þegar þær ná ákveðnu gildi, einnig þekkt sem stuðull. Þú getur hugsað um þetta eins og klukku: að lokum mun hönd klukkunnar snúa aftur til klukkan 1 eftir klukkan 12, ekki til klukkan 13. Stuðullinn er nefndur sem (mod n). Þannig að í þessu skrefi reiknarðu a með stuðulinn n.
   • Önnur aðferð er að reikna a, deila því með n og nota afganginn sem svar þitt. Sérhæfðir reiknivélar með modulusaðgerð geta verið mjög gagnlegar þegar stórum tölum er deilt, vegna þess að þeir geta strax reiknað það sem eftir er af deili.
   • Með því að nota slíkan reiknivél í dæminu okkar getum við séð að 3/100 hefur afganginn af 1. Svo, 3 (mod 100) er 1.
4. Ef við reiknum þetta með höndunum, notum við veldisvísirinn sem stutt snið. Ef þú ert ekki með reiknivél með modulusaðgerð skaltu nota táknið með veldisvísi til að auðvelda aðferðina til að ákvarða afganginn. Sjá fyrir neðan:
   • Í dæminu okkar reiknum við 3 með stuðulinn 100. 3 er mjög, mjög stór tala - 515,377,520,732,011,331,036,461,129,765,621,272,702,107,522,001 - svo stór að það verður mjög erfitt að vinna með það. Frekar en að nota 48 stafa svarið fyrir 3, þá skrifum við það betur sem veldisvísir, svo (((((((3)*3))))*3)). Mundu að taka veldisvísis veldisvísis hefur þau áhrif að margfaldast veldisvísindamenn ((x) = x).
     • Nú getum við ákvarðað restina. Byrjaðu á því að leysa ((((((3) * 3))) * 3)) í innri sviganum og vinna þig út og deila hverju skrefi með 100. Þegar við höfum fundið restina munum við nota það fyrir næsta skref frekar en raunverulegt svar. Sjá fyrir neðan:
       • ((((((9) * 3))) * 3)) - 9/100 hefur enga afgang, svo við getum haldið áfram.
       • (((((27)))) * * 3)) - 27/100 hefur enga afgang, svo við getum haldið áfram.
       • ((((729))) * 3)) - 729/100 = 7 R 29. Afgangurinn okkar er 29. Við höldum áfram með næsta skrefi, ekki 729.
       • ((((29=841)) * * 3)) - 841/100 = 8 R 41. Við notum afganginn 41 aftur í næsta skrefi.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Við notum afganginn 81 í næsta skrefi.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Við notum afganginn 43 í næsta skrefi.
       • (43 = 1849) - 1849/100 = 18 R 49. Við notum afganginn 49 í næsta skrefi.
       • 49 = 2401 - 2401/100 = 24 R 1. Lokaafgangurinn okkar er 1. Með öðrum orðum, 3 (mod 100) = 1. Athugaðu að þetta er sama svarið og við reiknuðum út í fyrra skrefi!
5. Finndu út hvort a (mod n) = a (mod n). Ef ekki er n samsett. Ef satt er þá n líklega, (en ekki viss) frumtala. Að endurtaka prófið með mismunandi gildi fyrir a getur gert niðurstöðuna öruggari, en það eru sjaldgæfar samsettar tölur sem fullnægja setningu Fermat fyrir allt gildi a. Þetta eru kölluð Carmichael tölurnar - minnsta talan er 561.
   • Í dæminu okkar eru 3 (mod 100) = 1 og 3 (mod 100) = 3.1 ≠ 3, svo við getum sagt að 100 sé samsett tala.
6. Notaðu Carmichael tölurnar til að vera viss um árangur þinn. Að vita hvaða tölur uppfylla Carmichael seríuna áður en haldið er áfram getur sparað þér miklar áhyggjur af því hvort tala er frumefni eða ekki. Almennt eru Carmichael tölur afurð einstakra frumtala, þar sem fyrir allar frumtölur gildir að ef p er deilir n, þá er einnig p-1 deili n-1. Veflistinn yfir Carmichael tölur getur verið mjög gagnlegur til að ákvarða hvort tala sé frum, með því að nota litla setningu Fermat.
   
   

Aðferð 3 af 4: Nota Miller-Rabin prófið

Miller-Rabin prófið virkar á sama hátt og litla setning Fermats en fjallar betur um óstaðlaðar tölur eins og Carmichael tölur.

1. Geri ráð fyrir n er oddatala sem við viljum prófa fyrir frumleika. Eins og í aðferðunum sem gefnar eru upp hér að ofan, er n breytan sem við viljum ákvarða frumstæði.
2. Þrýstingur n-1 í formi 2 × d við hvaða d er skrýtið. Talan n er frumefni ef hún er skrýtin. Svo að n - 1 hlýtur að vera jafnt. Þar sem n - 1 er jafnt, er hægt að skrifa það sem kraftur sem er tvöfalt oddatala. Svo, 4 = 2 × 1; 80 = 2 × 5; og svo framvegis.
   • Segjum sem svo að við viljum ákvarða hvort n = 321 sé frum. 321 - 1 = 320, sem við getum tjáð sem 2 × 5.
     • Í þessu tilfelli er n = 321 heppileg tala. Að ákvarða n - 1 fyrir n = 371 gæti þurft mikið gildi fyrir d, sem gerir allt ferlið erfiðara á síðari stigum. 371 - 1 = 370 = 2 × 185
3. Veldu hvaða númer sem er a milli 2 og n-1. Nákvæm tala sem þú velur skiptir ekki máli - bara að hún verður að vera minni en n og meiri en 1.
   • Í dæminu okkar með n = 321 veljum við a = 100.
4. reikna a (mod n). Ef a = 1 eða -1 (mod n), líður þá framhjá n Miller-Rabin prófið og er líklega frumtala. Eins og með litla setningu Fermats, getur þetta próf ekki ákvarðað með fullkominni vissu frumleika tölu, heldur þarf viðbótarpróf.
   • Í dæmi okkar með n = 321, a (mod n) = 100 (mod 321). 100 = 10.000.000.000 (mod 321) = 313. Við notum sérstaka reiknivél, eða styttri aðferð með veldisvísi eins og áður var lýst, til að finna afganginn af 100/321.
     • Þar sem við höfum ekki fengið 1 eða -1 getum við ekki sagt með vissu að n sé frum. En það er samt meira sem við þurfum að gera - lestu áfram.
5. Þar sem niðurstaðan er ekki jöfn 1 eða -1, reiknið a, a, ... og svo framvegis, upp í ad. Reiknið hækkað upp á kraft d sinnum, allt að 2. Ef annað hvort af þessu er 1 eða -1 (mod n), líður þá framhjá n Miller-Rabin prófin og er líklega prime. Ef þú hefur ákveðið að n standist prófið skaltu athuga svarið þitt (sjá skrefið hér að neðan). Ef n fellur á einhverjum af þessum prófum er það eitt samið númer.
   • Til að minna á, í dæminu okkar, er gildi a 100, gildi s er 6 og d er 5. Við höldum áfram að prófa eins og sýnt er hér að neðan:
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 64,64 ≠’ 1 eða -1. Haltu áfram í rólegheitum.
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 244,244 ≠ 1 eða -1.
     • Á þessum tímapunkti getum við hætt. s - 1 = 6 - 1 = 5. Við höfum nú náð 4d = 2, og það eru engir kraftar tvisvar sinnum d undir 5d. Þar sem enginn af útreikningum okkar svaraði 1 eða -1 getum við sagt að n = 321 einn samið númer er.
6. Ef n standist Miller-Rabin prófið, endurtaktu fyrir önnur gildi í a. Ef þú hefur komist að því að gildi n gæti verið aðal, reyndu aftur með öðru, handahófi gildi fyrir a til að staðfesta niðurstöðu prófsins. Ef n er í raun frum, þá mun það vera satt fyrir hvaða gildi sem er. Ef n er samsett tala, mun það mistakast í þremur fjórðu af gildum a. Þetta gefur þér meiri vissu en litla setning Fermats, þar sem viss samsettar tölur (Carmichael tölurnar) standast prófið fyrir hvaða gildi sem er a.

Aðferð 4 af 4: Notaðu kínversku restarsetninguna

1. Veldu tvær tölur. Ein talan er ekki frum og hin er talan sem er prófuð fyrir frumleiki.
   • "Prófnúmer 1" = 35
   • Próf númer2 = 97
2. Veldu tvo gagnapunkta sem eru stærri en núll og minni en TestNumber1 og TestNumber2. Þeir geta ekki verið jafnir hver öðrum.
   • Gögn1 = 1
   • Gögn2 = 2
3. Reiknið MMI (stærðfræðilegt margföldunar andhverfu) fyrir prófnúmer 1 og prófnúmer 2
   • Reiknið MMI
     • MMI1 = Prófnúmer2 ^ -1 Modprófunúmer1
     • MMI2 = prófanúmer1 ^ -1 Mod prófunarnúmer2
   • Aðeins fyrir frumtölur (það verður niðurstaða fyrir aðrar frumtölur, en það er ekki MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (TestNumber1 ^ (TestNumber-2))% TestNumber2
   • Svo:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Búðu til tvöfalda töflu fyrir hvern MMI upp í Log2 í Modulus
   • Fyrir MMI1
     • F (1) = prófanúmer2% prófunarnúmer1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Prófnúmer1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Prófnúmer1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Prófnúmer1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Prófnúmer1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Prófnúmer1 = 1 * 1% 35 = 1
   • Reiknið tvöfaldan lógaritma TestNumber1 - 2
     • 35 -2 = 33 (10001) grunnur 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 Mod 35
     • MMI1 = 27
   • Fyrir MMI2
     • F (1) = prófanúmer1% prófunarnúmer2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% prófanúmer2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Prófnúmer2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Prófnúmer2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Prófnúmer2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Prófnúmer2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% prófanúmer2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Prófnúmer2 = 35 * 35 mod 97 = 61
   • Reiknið tvöfaldan lógaritma TestNumber2 - 2
     • 97 - 2 = 95 = (1011111) grunnur 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. Reiknið út (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Svar = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Svar = (2619 + 4270)% 3395
   • Svar = 99
6. Athugaðu að „TestNumber1“ er ekki prime1
   • Reiknið (svar - gögn1)% prófanúmer1
   • 99 -1 % 35 = 28
   • Þar sem 28 er stærri en 0, er 35 ekki frumefni
7. Athugaðu hvort TestNumber2 sé besta
   • Reiknaðu út (svar - gögn2)% prófanúmer2
   • 99 - 2 % 97 = 0
   • Þar sem 0 er jafnt og 0 er 97 möguleg frumtala
8. Endurtaktu skref 1 til 7 að minnsta kosti tvisvar í viðbót.
   • Ef skref 7 er jafnt og 0:
     • Notaðu annað „TestNumber1“ ef TestNumber1 er ekki prime.
     • Notaðu annað TestNumber1 þar sem TestNumber1 er í raun aðal. Í þessu tilfelli eru skref 6 og 7 jafnt og 0.
     • Notaðu mismunandi gagnapunkta fyrir data1 og data2.
   • Ef skref 7 er alltaf jafnt og 0, þá eru líkurnar á því að tala 2 sé frumtala mjög mikil.
   • Þrep 1 til 7 eru þekkt fyrir að vera röng í vissum tilvikum þegar fyrsta talan er ekki frum og önnur er frumstuðull tölunnar sem er ekki frumtala „Prófnúmer 1“. Það virkar í öllum atburðarásum þar sem báðar tölurnar eru frumtölur.
   • Ástæðan fyrir því að skref 1 til 7 eru endurtekin er vegna þess að það eru nokkrar sviðsmyndir þar sem, jafnvel þótt TestNumber1 sé ekki prime og TestNumber2 er ekki prime, þá er annaðhvort talan úr 7. þrepi ennþá núll. Þessar aðstæður eru sjaldgæfar. Með því að breyta TestNumber1 í aðra tölu sem ekki er frumtala, ef TestNumber2 er ekki frumtala, mun TestNumber2 ekki lengur vera núll, í þrepi 7. Nema þegar „TestNumber1“ er þáttur í TestNumber2, þá eru frumtölur alltaf núll. 7. þrep.

Ábendingar

• 168 frumtölurnar undir 1000 eru: 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
• Þegar reynir að skipta er hægar en flóknari aðferðirnar er það samt skilvirkt fyrir minni tölur. Jafnvel þegar prófaðar eru stærri tölur er ekki óalgengt að skoða litlu tölurnar fyrst áður en skipt er yfir í fullkomnari aðferðir.

Nauðsynjar

• Pappír, penni, blýantur og / eða reiknivél til að æfa