Hoe te weten of een cijfer priem is

De priemgetallen zijn alleen deelbaar tussen zichzelf en 1. Aan de andere kant worden alle andere cijfers samengestelde getallen genoemd. Er zijn veel methoden om te weten of een getal priemgetal is, maar er is altijd een zekere foutenmarge. Er zijn ook nauwkeurige maar zeer langzame tests om grote aantallen te analyseren, evenals andere veel snellere, maar ze kunnen valse resultaten geven. In dit artikel ziet u enkele opties om een priemgetal te detecteren op basis van de grootte.

stappen

Inhoud

Stappen
Deel 1
Deel 2
Deel 3
Tips
Dingen die je nodig hebt

Deel 1

Gebruik verschillende tests om een priemgetal te detecteren

Let op: in alle formules, n is het nummer waarvan u de primaliteit wilt bewijzen.

Titel afbeelding Check of a Number Is Prime Step 1

Gebruik de verdeling door voorzichtig te zijn. verdelen n tussen elk priemgetal van 2 tot de plafondfunctie ( ${ displaystyle { sqrt {n}}}$ ).

Titel afbeelding Check if a Number Is Prime Step 2

Voer de kleine stelling van Fermat uit. Waarschuwing: u kunt vals-positieven krijgen, zelfs voor alle waarden van a.

Wijs een volledige waarde toe aan een dusdanige dat 2 ≤ a ≤ n - 1.

Als a (mod n) = a (mod n), dan is "n" waarschijnlijk een priemgetal. Als hieraan niet wordt voldaan, is "n" geen priemgetal.

Doe hetzelfde met verschillende waarden van om er zeker van te zijn dat het echt neef is.

Titel afbeelding Check of a Number Is Prime Step 3

Voert de Miller-Rabin-primaliteitstest uit. Waarschuwing: je zou valse positieven kunnen krijgen, maar het gebeurt zelden in meerdere waarden van a.

Zoek de waarden van "s" en "d" op zo`n manier dat

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

Wijs een volledige waarde toe aan een dusdanige dat 2 ≤ a ≤ n - 1.

Als a = +1 (mod n) of -1 (mod n), dan is "n" waarschijnlijk een priemgetal. Ga nu naar het testresultaat - ga anders door naar de volgende stap.

Verhoog het antwoord in het kwadraat (

{ displaystyle a ^ {2d}}

). Als dit gelijk is aan +1 (mod n) of -1 (mod n), ga dan naar het testresultaat. Anders herhaal (

{ displaystyle a ^ {4d}}

etc.) tot

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

Resultaat van de test: als "n" slaagt voor de test, wijst u verschillende waarden toe aan a om zijn primaliteit te garanderen.

Deel 2

Begrijp de tests om priemgetallen te detecteren

Titel afbeelding Check if a Number Is Prime Step 4

Begrijp de methode van deling door een poging. Volgens de definitie van primaliteit, n is alleen een priemgetal als het niet gelijk verdeeld kan worden over hele getallen zoals 2 of meer. De formule van de vader bespaart je tijd door onnodige tests weg te gooien (bijv. Na het testen van 3, is het niet nodig om hetzelfde te doen met 9).
Het functieplafond (x) rondt x af tot het dichtstbijzijnde gehele getal ≥ x.

Titel afbeelding Check of a Number Is Prime Step 5

Het omvat modulaire rekenkunde. De bewerking "x mod y" (afkorting voor "module") betekent "delen" x "tussen" en "en vindt het residu." Met andere woorden, in modulair rekenen gaan de getallen terug naar nul na het bereiken van een bepaalde bekende waarde als de "module". Een klok telt in module 12 (dat wil zeggen, het gaat van 10 naar 11 en naar 12) en keert dan terug naar 1.

Veel rekenmachines bevatten een "mod" -knop, maar kijk in het laatste deel van dit gedeelte hoe u dit met de hand kunt oplossen voor grote aantallen.

Titel afbeelding Check if a Number Is Prime Step 6

Houd rekening met de problemen met de kleine stelling van Fermat. Alle getallen die niet aan deze test voldoen, zijn samengesteld (geen neven en nichten), maar helaas zijn degenen die wel slagen, alleen waarschijnlijk neven en nichten. Als je veilig valse positieven wilt vermijden, kijk n in een lijst met "Carmichael-nummers" (die deze test de hele tijd doorgeven) en "Fermat pseudoprimos" (die deze test alleen doorstaan voor sommige waarden van a).

Titel afbeelding Check of a Number Is Prime Step 7

Gebruik waar nodig de Miller-Rabin-primaliteitstest. Hoewel het moeilijk is om met de hand te spelen, wordt deze test meestal gedaan met software. Het duurt niet lang en heeft weinig vals-positieven in vergelijking met de methode van Fermat. Een samengestelde nummer geeft nooit een vals positief voor meer dan ¼ van de waarden van a. Als u meerdere waarden kiest van om willekeurig te slagen en deze test te doorstaan, kun je bijna alle zekerheid hebben dat n is een neef

Titel afbeelding Check of a Number Is Prime Step 8

Voer modulaire rekenkunde uit om grote aantallen te analyseren. Als je geen rekenmachine hebt met de "mod" -functie of als degene die je hebt niet zulke hoge getallen kan representeren, gebruik dan de eigenschappen van de exponenten en de modulaire rekenkunde om het proces te vergemakkelijken. In dit geval zullen we als voorbeeld gebruiken

{ displaystyle 3 ^ {50}}

mod 50:

Herschrijf de expressie met meer beheersbare exponenten:

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

mod 50 (misschien moet je het nog meer ontleden als je de berekening met de hand gaat doen).

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

mod 50 =

{ displaystyle (3 ^ {25}}

mod 50

{ displaystyle * 3 ^ {25}}

mod 50) mod 50 (dit is een eigenschap van modulaire 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 de Chinese stelling van de rest

Titel afbeelding Check of a Number Is Prime Step 9

Kies twee nummers Een van hen zou geen neef moeten zijn, terwijl de ander degene zou moeten zijn die je moet analyseren om zijn primaliteit te ontdekken.

"Primo1" = 35
primo2 = 97

Titel afbeelding Check of a Number Is Prime Step 10

Kies twee gegevenspunten die groter zijn dan nul en kleiner zijn dan respectievelijk primo1 en primo2. Ze kunnen niet hetzelfde zijn.

dato1 = 1

dato2 = 2

Titel afbeelding Check of a Number Is Prime Step 11

Bereken de multiplicatieve inverse (IM) van de getallen primo1 en primo2.

Bereken de IM:

IM1 = primo2 ^ -1 mod primo1

IM2 = primo1 ^ -1 mod primo2

Alleen in het geval van priemgetallen (u krijgt een nummer voor samengestelde nummers, maar dit is niet uw IM):

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

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

Bijvoorbeeld:

IM1 = (97 ^ 33)% 35

IM2 = (35 ^ 95)% 97

Titel afbeelding Check of a Number Is Prime Step 12

Maak voor elke IM een binaire conversietabel totdat u de log2 van de module bereikt.

Voor 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

Voert binaire omzetting 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

Voor 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 binaire omzetting 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

Titel afbeelding Check of a Number Is Prime Step 13

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

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

Antwoord = (2619 + 4270)% 3395

Antwoord = 99

Titel afbeelding Check of a Number Is Prime Step 14

Controleer of "primo1" geen priemgetal is.

Bereken (antwoord - gegevens1)% primo1.

99 -1% 35 = 28.

Omdat 28 groter is dan 0, betekent dit dat 35 geen priemgetal is.

Titel afbeelding Check of a Number Prime is Stap 15

Controleer of primo2 een priemgetal is.

Bereken (antwoord - gegevens2)% primo2

99 - 2% 97 = 0

Omdat 0 gelijk is aan 0, betekent dit dat 97 waarschijnlijk een priemgetal is.

Titel afbeelding Check of a Number Prime is Stap 16

Herhaal stap 1 tot en met 7 nog minstens twee keer.

Als je in stap 7 een 0 krijgt:

Gebruik een andere "primo1", waarbij primo1 geen priemgetal is.

Gebruik een andere primo1, waarbij primo1 geen reëel getal is. In dit geval moeten stappen 6 en 7 gelijk zijn aan 0.

Gebruik verschillende gegevenspunten voor data1 en data2.

Als stap 7 altijd 0 als resultaat geeft, is er een zeer grote kans dat primo2 een priemgetal is.

In sommige gevallen kunnen stappen 1 tot en met 7 mislukken als het eerste getal niet prime is en het tweede een factor is van het samengestelde nummer "primo1". Het werkt in alle gevallen waarin beide nummers prime zijn.

De reden waarom stap 1 tot en met 7 worden herhaald, is omdat er enkele situaties zijn waarin, zelfs als primo1 en primo2 zijn samengesteld, stap 7 nog steeds resulteert in 0, voor één of voor beide getallen. Deze omstandigheden zijn echter zeldzaam. Bij het converteren primo1 in een ander samengesteld getal als primo2 niet priem, zal zeker nul in stap 7. Behalve in het geval dat "primo1" is een factor primo2 zal priemgetallen altijd gelijk aan nul Stap 7

tips

De 168 priemgetallen van minder dan 1000 zijn de 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
Hoewel de voorlopige delingsmethode langzamer is dan de andere geavanceerde methoden die specifiek zijn voor grote getallen, is deze nog steeds erg efficiënt voor kleine getallen. Zelfs om te weten of grote aantallen neven zijn of niet, is het niet ongebruikelijk om eerst de kleine factoren te controleren voordat een meer geavanceerde methode wordt gebruikt in het geval dat deze factoren niet worden gevonden.

Dingen die je nodig hebt

rekenhulpmiddelen: potlood, papier of een computer

Meer weergeven ... (5)

Delen op sociale netwerken:

Verwant