Ábhar

• Céimeanna
• Cuid 1 de 3: Tástálacha Simplíochta
• Cuid 2 de 3: Conas a Oibríonn Tástálacha Simplíochta
• Cuid 3 de 3: Teoirim Iarmhair na Síne a Úsáid
• Leideanna
• Céard atá ag teastáil uait

Is uimhreacha príomha iad uimhreacha nach bhfuil inroinnte ach leo féin agus faoi 1. Tugtar uimhreacha ilchodacha ar gach uimhir eile. Tá go leor bealaí ann chun a chinneadh an bhfuil uimhir phríomha, agus tá a buntáistí agus a míbhuntáistí féin ag gach ceann acu. Ar thaobh amháin, tá cuid de na modhanna an-chruinn, ach tá siad casta go leor má tá tú ag déileáil le líon mór. Ar an láimh eile, tá bealaí i bhfad níos gasta ann, ach d’fhéadfadh torthaí míchearta a bheith mar thoradh orthu. Braitheann rogha an mhodha chuí ar cé chomh mór agus atá na huimhreacha a bhfuil tú ag obair leo.

Céimeanna

Cuid 1 de 3: Tástálacha Simplíochta

Nóta: i ngach foirmle n seasann an uimhir atá le seiceáil.

1. 1 Áireamh roinnteoirí. Is leor é a roinnt n do na huimhreacha príomha go léir ó 2 go dtí an luach cruinn (${ displaystyle { sqrt {n}}}$).
2. 2 Teoirim beag Fermat. Rabhadh: uaireanta sainaithneoidh an tástáil go bréagach uimhreacha ilchodacha mar phríomhaí, fiú amháin do luachanna uile a.
   • Déanaimis slánuimhir a roghnú aionas go mbeidh 2 ≤ a ≤ n - 1.
   • Más a (mod n) = a (mod n) ansin is dócha go bhfuil an uimhir príomha. Mura bhfuil an comhionannas sásta, tá an uimhir n ilchodach.
   • Seiceáil an comhionannas a thugtar le haghaidh luachanna iolracha achun an dóchúlacht go bhfuil an líon atá á thástáil príomha a mhéadú.
3. 3 Tástáil Miller-Rabin. Rabhadh: uaireanta, cé gur annamh, i gcás luachanna iolracha a, sainaithneoidh an tástáil go bréagach uimhreacha ilchodacha mar phríomhaí.
   • Faigh na cainníochtaí s agus d sa chaoi go ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Roghnaigh slánuimhir a sa raon 2 ≤ a ≤ n - 1.
   • Más a = +1 (mod n) nó -1 (mod n), ansin is dócha go bhfuil n príomha. Sa chás seo, téigh chuig toradh na tástála. Mura bhfuil an comhionannas ann, téigh ar aghaidh go dtí an chéad chéim eile.
   • Cearnóg do fhreagra (${ displaystyle a ^ {2d}}$). Má fhaigheann tú -1 (mod n), ansin is dócha gur uimhir phríomha í n. Sa chás seo, téigh chuig toradh na tástála. Má theipeann ar an gcomhionannas, déan arís (${ displaystyle a ^ {4d}}$ agus mar sin de) go dtí ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Más rud é ag céim éigin tar éis squaring uimhir seachas ${ displaystyle pm 1}$ (mod n), fuair tú +1 (mod n), mar sin is uimhir ilchodach í n. Dá ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), ansin níl n príomha.
   • Toradh na tástála: má éiríonn le n an tástáil, déan arís é le haghaidh luachanna eile achun an mhuinín a mhéadú.

Cuid 2 de 3: Conas a Oibríonn Tástálacha Simplíochta

1. 1 Áireamh roinnteoirí. De réir sainmhínithe, an uimhir n níl sé simplí ach mura bhfuil sé inroinnte ag 2 agus slánuimhreacha eile seachas 1 agus é féin. Ligeann an fhoirmle thuas duit céimeanna gan ghá a bhaint agus am a shábháil: mar shampla, tar éis duit a sheiceáil an bhfuil uimhir inroinnte faoi 3, ní gá a sheiceáil an bhfuil sí inroinnte faoi 9.
   • Babhtaí feidhme an urláir (x) x go dtí an tslánuimhir is gaire atá níos lú ná nó cothrom le x.
2. 2 Foghlaim faoi uimhríocht mhodúlach. Ciallaíonn an oibríocht "x mod y" (is giorrúchán den fhocal Laidine "modulo" é mod, is é sin, "modúl") ciallaíonn "roinn x ar y agus faigh an fuílleach." Is é sin le rá, in uimhríocht mhodúlach, ar luach áirithe a bhaint amach, ar a dtugtar modúl, casann na huimhreacha go nialas arís. Mar shampla, comhaireamh an clog síos le modúl 12: taispeánann sé 10, 11 agus 12 uair an chloig, agus ansin filleann sé ar 1.
   • Tá eochair mod ag go leor áireamháin. Taispeánann deireadh an ailt seo duit conas an fheidhm seo a ríomh de láimh do líon mór.
3. 3 Faigh amach faoi na deacrachtaí atá ag Teoirim Bheag Fermat. Tá na huimhreacha go léir nach gcomhlíontar na coinníollacha tástála ilchodach ina leith, ach níl sa chuid eile de na huimhreacha ach is dócha atá simplí. Más mian leat torthaí míchearta a sheachaint, déan cuardach n sa liosta “uimhreacha Carmichael” (uimhreacha ilchodacha a shásaíonn an tástáil seo) agus “Uimhreacha pseudoprime Fermat” (ní chomhlíonann na huimhreacha seo na coinníollacha tástála ach do roinnt luachanna a).
4. 4 Más áisiúil, bain úsáid as an tástáil Miller-Rabin. Cé go bhfuil an modh seo sách cumasach le haghaidh ríomhanna láimhe, is minic a úsáidtear é i gcláir ríomhaire. Soláthraíonn sé luas inghlactha agus níos lú earráidí ná modh Fermat. Ní ghlacfar le huimhir ilchodach mar phríomhuimhir má dhéantar ríomhanna ar luach níos mó ná ¼ a... Má roghnaíonn tú luachanna difriúla go randamach a agus dóibh uile tabharfaidh an tástáil toradh dearfach, is féidir linn glacadh leis go muiníneach go leor n is uimhir phríomha í.
5. 5 I gcás líon mór, bain úsáid as uimhríocht mhodúlach. Mura bhfuil áireamhán mod áisiúil agat, nó mura bhfuil an t-áireamhán deartha chun líon chomh mór sin a láimhseáil, bain úsáid as airíonna cumhachta agus uimhríocht mhodúlach chun na ríomhanna a dhéanamh níos éasca. Seo thíos sampla do ${ displaystyle 3 ^ {50}}$ mod 50:
   • Athscríobh an slonn i bhfoirm níos áisiúla: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. D’fhéadfadh go mbeadh gá le simplithe breise chun ríomhanna láimhe a dhéanamh.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Chuir muid san áireamh maoin iolraithe modúlach.
   • ${ 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}$.

Cuid 3 de 3: Teoirim Iarmhair na Síne a Úsáid

1. 1 Roghnaigh dhá uimhir. Caithfidh ceann de na huimhreacha a bheith ilchodach, agus caithfidh an ceann eile a bheith díreach mar an ceann is mian leat a thástáil ar mhaithe le simplíocht.
   • Uimhir1 = 35
   • Uimhir2 = 97
2. 2 Roghnaigh dhá luach is mó ná nialas agus, faoi seach, níos lú ná na huimhreacha Uimhir 1 agus Uimhir 2. Níor cheart go mbeadh na luachanna seo mar an gcéanna.
   • Luach1 = 1
   • Luach2 = 2
3. 3 Ríomh an MMI (inbhéartach iolrach matamaiticiúil) d’Uimhir 1 agus Uimhir 2.
   • Ríomh MMI
     • MMI1 = Uimhir2 ^ -1 Uimhir Mod1
     • MMI2 = Uimhir1 ^ -1 Uimhir Mod2
   • Maidir le huimhreacha príomha amháin (tabharfaidh sé seo uimhir d’uimhreacha ilchodacha, ach ní hé a MMI a bheidh ann):
     • MMI1 = (Uimhir2 ^ (Uimhir1-2))% Uimhir1
     • MMI2 = (Uimhir1 ^ (Uimhir 2-2))% Uimhir2
   • Mar shampla:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Cruthaigh tábla do gach MMI síos go modúil log2:
   • Do MMI1
     • F (1) = Uimhir2% Uimhir1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Uimhir1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Uimhir1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Uimhir1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Uimhir1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Uimhir1 = 1 * 1% 35 = 1
   • Ríomh Uimhreacha Péire 1 - 2
     • 35 -2 = 33 (10001) bonn 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • Do MMI2
     • F (1) = Uimhir1% Uimhir2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Uimhir2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Uimhir2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Uimhir2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Uimhir2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Uimhir2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Uimhir2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Uimhir2 = 35 * 35 mod 97 = 61
   • Ríomh an Uimhir Phéire 2 - 2
     • 97 - 2 = 95 = (1011111) bonn 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. 5 Ríomh (Luach1 * Uimhir2 * MMI1 + Luach2 * Uimhir1 * MMI2)% (Uimhir1 * Uimhir 2)
   • Freagra = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Freagra = (2619 + 4270)% 3395
   • Freagra = 99
6. 6 Seiceáil nach bhfuil Uimhir 1 príomha
   • Ríomh (Freagra - Luach1)% Uimhir1
   • 99 – 1 % 35 = 28
   • Ós rud é go bhfuil 28 níos mó ná 0, ní uimhir phríomha í 35.
7. 7 Seiceáil go bhfuil Uimhir 2 príomha.
   • Ríomh (Freagra - Luach2)% Uimhir2
   • 99 – 2 % 97 = 0
   • Ó tharla gurb é 0 0, is dóichí gurb é 97 uimhir phríomha.
8. 8 Déan céimeanna 1 go 7 arís dhá uair eile ar a laghad.
   • Má fhaigheann tú 0 i gcéim 7:
     • Úsáid Uimhir1 dhifriúil mura bhfuil Uimhir 1 príomha.
     • Úsáid Uimhir1 eile má tá Uimhir 1 príomha. Sa chás seo, ba cheart duit 0 a fháil i gcéimeanna 6 agus 7.
     • Úsáid Brí1 agus Brí éagsúil 2.
   • Má fhaigheann tú 0 i gcéim 7 go seasta, is beag seans go mbeidh Uimhir 2 príomha.
   • D’fhéadfadh earráid a bheith mar thoradh ar chéimeanna 1 go 7 mura bhfuil Uimhir 1 príomha agus má tá Uimhir 2 ina roinnteoir ar Uimhir1. Oibríonn an modh a thuairiscítear i ngach cás nuair a bhíonn an dá uimhir príomha.
   • Is é an chúis is gá duit céimeanna 1 go 7 a athdhéanamh ná mar gheall i gcásanna áirithe, fiú mura bhfuil Uimhir 1 agus Uimhir 2 príomha, i gcéim 7 gheobhaidh tú 0 (d’uimhir amháin nó an dá uimhir). Is annamh a tharlaíonn sé seo.Roghnaigh Uimhir1 eile (ilchodach), agus mura bhfuil Uimhir 2 príomha, ansin ní bheidh Uimhir 2 cothrom le nialas i gcéim 7 (ach amháin an cás nuair a bhíonn Uimhir 1 ina roinnteoir ar Uimhir 2 - anseo beidh na príosúin cothrom le nialas i gcéim 7 i gcónaí).

Leideanna

• Príomhuimhreacha ó 168 go 1000: 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.
• Cé gur tástáil tedious é tástáil fórsa bruit agus tú ag obair le líon mór, tá sé éifeachtach go leor do líon beag. Fiú amháin i gcás líon mór, tosaigh trí thástáil a dhéanamh ar roinnteoirí beaga, agus ansin bog ar aghaidh chuig modhanna níos sofaisticiúla chun simplíocht uimhreacha a sheiceáil (mura bhfaightear roinnteoirí beaga).

Céard atá ag teastáil uait

• Páipéar, peann nó ríomhaire