Hoe om te weet of `n nommer prima is

Die priemgetalle is slegs verdeelbaar tussen hulle en 1. Aan die ander kant word alle ander saamgestelde getalle genoem. Daar is baie metodes om te weet of `n nommer prima is, maar daar is altyd `n sekere foutmarge. Daar is ook presiese maar baie stadige toetse om groot getalle sowel as baie vinniger te analiseer, maar hulle kan vals resultate gee. In hierdie artikel sal jy `n paar opsies sien om `n priemgetal op grond van die grootte daarvan op te spoor.

stappe

conținut

Stappe
Deel 1
Deel 2
Deel 3
Wenke
Dinge wat jy nodig het

Deel 1

Gebruik verskillende toetse om `n priemgetal op te spoor

wel: in alle formules, n is die nommer wie se primaliteit jy wil bewys.

Prent getiteld Kyk of `n nommers eerste stap 1 is

Gebruik die afdeling deur voorlopig. verdeel n tussen elke priemgetal van 2 na die plafonfunksie ( ${ displaystyle { sqrt {n}}}$ ).

Prent getiteld Kyk of `n nommers eerste stap 2 is

Voer Fermat se stelling uit. Waarskuwing: jy kan valse positiewe kry, selfs vir alle waardes van a.

Ken `n hele waarde toe aan `n sodanig dat 2 ≤ a ≤ n - 1.

As `n (mod n) = a (mod n), dan is "n" waarskynlik `n priemgetal. As dit nie nagekom word nie, is "n" nie `n priem nie.

Doen dieselfde met verskillende waardes van om seker te maak dis regtig niggie.

Prent getiteld Kyk of `n nommer die eerste stap is

Voer die Miller-Rabin-primaltoets uit. Waarskuwing: jy kan valse positiewe kry, maar dit gebeur selde in verskeie waardes van a.

Vind die waardes van "s" en "d" op so `n manier dat

{ displaystyle n-1 = 2 ^ {s} * d}

Ken `n hele waarde toe aan `n sodanig dat 2 ≤ a ≤ n - 1.

As a = +1 (mod n) of -1 (mod n), dan is "n" waarskynlik `n priemgetal. Gaan nou na die toetsuitslag - anders gaan jy na die volgende stap.

Verhoog die antwoord kwadraat (

{ displaystyle a ^ {2d}}

). As dit gelyk is aan +1 (mod n) of -1 (mod n), gaan na die toetsresultaat. Andersins, herhaal (

{ displaystyle a ^ {4d}}

ens.) tot

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

Uitslag van die toets: Indien "n" die toets slaag, wys verskillende waardes van a om sy primaliteit te waarborg.

Deel 2

Verstaan die toetse om priemgetalle op te spoor

Prent getiteld Kyk of `n nommers eerste stap 4 is

Verstaan die metode van verdeling deur poging. Volgens die definisie van primaliteit, n is slegs `n priem as dit nie ewe verdeel kan word tussen heelgetalle soos 2 of meer nie. Die formule pa spaar jou tyd deur onnodige toetse te verwyder (bv. Na toets 3 is dit nie nodig om dieselfde te doen met 9 nie).
Die funksie plafon (x) ronde x na die naaste heelgetal ≥ x.

Prent getiteld Kyk of `n nommer is Prime Step 5

Dit sluit modulêre rekenkunde in. Operasie "x mod y" (afkorting van "module") beteken "split" x "tussen" en "en vind die oorskot." Met ander woorde, in modulêre rekenkunde, die getalle terug na nul nadat hulle `n sekere bekende waarde as die "module". `n Klok tel in module 12 (dit gaan van 10 tot 11 en 12) en keer dan terug na 1.

Baie sakrekenaars sluit `n "mod" -knoppie in, maar kyk na die laaste gedeelte van hierdie afdeling om uit te vind hoe om dit met die hand op te los vir groot getalle.

Prent getiteld Kyk of `n nommers eerste stap 6 is

Hou die probleme met Fermat se stelling in gedagte. Al die nommers wat nie hierdie toets slaag nie, word saamgestel (nie niggies nie), maar ongelukkig is diegene wat pas, net geslaag waarskynlik niggies. As jy vals positiewe wil voorkom, moet jy kyk N in `n lys van "Carmichael getalle" (wat hierdie toets al die tyd om te slaag) en "pseudoprimos de Fermat" (wat hierdie toets slaag net vir sekere waardes a).

Prent getiteld Kyk of `n nommers eerste stap 7 is

Gebruik die Miller-Rabin-primaltoets wanneer dit toepaslik is. Alhoewel dit kompleks is om met die hand te doen, word hierdie toets gewoonlik deur sagteware gedoen. Dit duur nie lank nie en het min vals positiewe teenoor Fermat se metode. `N Verbindingsnommer gee nooit vals positief vir meer as ¼ van die waardes van a. As jy verskeie waardes van Om ewekansig te slaag en hierdie toets te slaag, kan jy byna al die versekering hê dat n is `n neef

Prent getiteld Kyk of `n nommer is Prime Step 8

Voer modulêre rekenkunde uit om groot getalle te analiseer. As jy nie `n sakrekenaar met die "mod" funksie het nie of as die een wat jy het nie sulke hoë getalle kan verteenwoordig nie, gebruik die eienskappe van die eksponente en die modulêre rekenkunde om die proses te vergemaklik. In hierdie geval sal ons as voorbeeld gebruik

{ displaystyle 3 ^ {50}}

mod 50:

Herskryf die uitdrukking met meer hanteerbare eksponente:

{ displaystyle (3 ^ {25} * 3 ^ {25})}

mod 50 (miskien moet jy dit selfs meer ontbind as jy die berekening met die hand doen).

{ displaystyle (3 ^ {25} * 3 ^ {25})}

mod 50 =

{ displaystyle (3 ^ {25}}

mod 50

{ displaystyle * 3 ^ {25}}

mod 50) mod 50 (dit is `n eienskap van modulêre vermenigvuldiging).

{ 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}

Deel 3

Gebruik die Chinese stelling van die res

Prent getiteld Kyk of `n nommers eerste stap 9 is

Kies twee getalle Een van hulle behoort nie `n neef te wees nie, terwyl die ander die een moet wees wat jy moet analiseer om sy primaliteit op te spoor.

"Primo1" = 35
primo2 = 97

Prent getiteld Kyk of `n nommers eerste stap 10 is

Kies twee datapunte wat groter as nul en kleiner is as onderskeidelik primo1 en primo2. Hulle kan nie dieselfde wees nie.

datum1 = 1

datum2 = 2

Prent getiteld Kyk of `n nommers eerste stap 11 is

Bereken die vermenigvuldigende inverse (IM) van die nommers primo1 en primo2.

Bereken die IM:

IM1 = primo2 ^ -1 mod primo1

IM2 = primo1 ^ -1 mod primo2

Slegs in die geval van priemgetalle (jy sal `n nommer vir saamgestelde getalle kry, maar dit sal nie jou IM wees nie):

IM1 = (primo2 ^ (primo1-2))% primo1

IM2 = (primo1 ^ (primo2-2))% primo2

Byvoorbeeld:

IM1 = (97 ^ 33)% 35

IM2 = (35 ^ 95)% 97

Prent getiteld Kyk of `n nommers eerste stap 12 is

Skep `n binêre omskakelingstabel vir elke IM totdat jy die module se log2 bereik.

Vir IM1:

F (1) = primo2% primo1 = 97% 35 = 27

F (2) = F (1) * F (1)% primo1 = 27 * 27% 35 = 29

F (4) = F (2) * F (2)% primo1 = 29 * 29% 35 = 1

F (8) = F (4) * F (4)% primo1 = 1 * 1% 35 = 1

F (16) = F (8) * F (8)% primo1 = 1 * 1% 35 = 1

F (32) = F (16) * F (16)% primo1 = 1 * 1% 35 = 1

Voer binêre omskakeling van primo1 - 2 uit

35 -2 = 33 (10001) basis 2

IMI1 = F (33) = F (32) * F (1) mod 35

IM1 = F (33) = 1 * 27 mod 35

IM1 = 27

Vir IM2:

F (1) = primo1% primo2 = 35% 97 = 35

F (2) = F (1) * F (1)% primo2 = 35 * 35 mod 97 = 61

F (4) = F (2) * F (2)% primo2 = 61 * 61 mod 97 = 35

F (8) = F (4) * F (4)% primo2 = 35 * 35 mod 97 = 61

F (16) = F (8) * F (8)% primo2 = 61 * 61 mod 97 = 35

F (32) = F (16) * F (16)% primo2 = 35 * 35 mod 97 = 61

F (64) = F (32) * F (32)% primo2 = 61 * 61 mod 97 = 35

F (128) = F (64) * F (64)% primo2 = 35 * 35 mod 97 = 61

Voer binêre omskakeling van primo2 - 2 uit

97 - 2 = 95 = (1011111) basis 2

IM2 = (((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97 )

IM2 = ((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)

IM2 = 61

Prent getiteld Kyk of `n nommers eerste stap 13 is

Bereken (data1 * primo2 * IM1 + data2 * primo1 * IM2)% (primo1 * primo2).

Antwoord = (1 * 97 * 27 +2 * 35 * 61)% (97 * 35)

Antwoord = (2619 + 4270)% 3395

Antwoord = 99

Prent getiteld Kyk of `n nommers eerste stap 14 is

Verifieer dat "primo1" nie `n priemgetal is nie.

Bereken (antwoord - data1)% primo1.

99 -1% 35 = 28.

Aangesien 28 groter as 0 is, beteken dit dat 35 nie `n priemgetal is nie.

Prent getiteld Kyk of `n nommers eerste stap 15 is

Kyk of primo2 `n priemgetal is.

Bereken (antwoord - data2)% primo2

99 - 2% 97 = 0

Aangesien 0 gelyk is aan 0, beteken dit dat 97 waarskynlik `n priemgetal is.

Prent getiteld Kyk of `n nommers eerste stap 16 is

Herhaal stap 1 tot 7 ten minste twee keer.

As jy in stap 7 `n 0 kry:

Gebruik `n ander "primo1", waar primo1 nie `n priemgetal is nie.

Gebruik `n ander primo1, waar primo1 nie `n regte nommer is nie. In hierdie geval moet stappe 6 en 7 gelyk wees aan 0.

Gebruik verskillende data punte vir data1 en data2.

As stap 7 altyd 0 gee, is daar `n baie groot waarskynlikheid dat primo2 `n priemgetal is.

In sommige gevalle kan stappe 1 tot 7 misluk indien die eerste nommer nie eerste is nie en die tweede is `n faktor van die saamgestelde getal "primo1". Dit werk in alle gevalle waar albei getalle prima is.

Die rede is dat die stappe 1 herhaal elke 7 is, want daar is `n paar geleenthede wat alhoewel primo1 en primo2 is verbindings, stap 7 nog lei tot 0, óf vir die een of vir beide getalle. Hierdie omstandighede is egter skaars. Wanneer die omskakeling primo1 in `n ander saamgestelde getal, indien primo2 is nie eerste, dit sal beslis nul in stap 7. Behalwe in die geval waar "primo1" is `n faktor primo2, sal priemgetalle altyd gelyk wees aan nul Stap 7

wenke

Die 168 priemgetalle minder as 1000 is die volgende: 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
Alhoewel die voorlopige verdelingsmetode stadiger is as die ander gesofistikeerde metodes wat spesifiek is vir groot getalle, is dit steeds baie doeltreffend vir klein getalle. Insluitende die vraag of `n groot aantal is prima of nie, dit is nie ongewoon om eers die klein faktore voor die gebruik van `n meer gevorderde metode in die geval dat die faktore gevind word.

Dinge wat jy nodig het

berekening gereedskap: potlood, papier of `n rekenaar

Wys meer ... (5)

Deel op sosiale netwerke:

Verwante