Kontroleer of `n nommer `n priemgetal is

Priemgetalle is getalle wat slegs deelbaar is en word 1 - ander getalle genoem saamgestelde

conținut

Stappe
Metode 1probeer om te deel
Metode 2gebruik die klein fermatstelling
Metode 3gebruik die miller-rabin-toets
Metode 4gebruik die chinese rus
Wenke
Voorrade

getalle. As dit gaan om die toets of `n nommer `n priemgetal is, is daar verskeie opsies. Sommige van hierdie metodes is relatief eenvoudig, maar absoluut nie prakties vir groter getalle nie. Ander toetse wat dikwels gebruik word, is eintlik volledige algoritmes gebaseer op een waarskynlikheid wat soms verkeerd `n nommer as `n priemgetal oorweeg. Lees verder in stap 1 om te leer hoe om jouself te toets as jy te doen het met `n priemgetal.

stappe

Metode 1
Probeer om te deel

Om te verdeel is verreweg die maklikste manier om `n nommer te toets. Vir klein getalle is dit gewoonlik ook die vinnigste manier. Die toets is gebaseer op die definisie van `n priemgetal: `n nommer is `n priemgetal as dit slegs op sigself verdeelbaar is en 1.

Prent getiteld Kyk of `n nommers eerste stap 1 is

Stel n is die nommer wat jy wil toets. Verdeel die getal n met alle moontlike deelbare heelgetalle. Vir groter getalle soos n = 101, is dit uiters onprakties om met enige moontlike heelgetal minder as n te verdeel. Gelukkig is daar verskeie truuks om die aantal faktore wat getoets moet word, te verminder.

Prent getiteld Kyk of `n nommers eerste stap 2 is

Bepaal of n even is. Alle ewe getalle is ten volle deelbaar met 2. Daarom, as n ewe is, kan jy dit sê n is `n saamgestelde getal (en dus nie `n priemgetal nie). Om vinnig vas te stel of `n getal gelyk is, moet jy net die laaste syfer aandag gee. As die laaste syfer `n 2, 4, 6, 8 of 0 is, dan is die getal ewe en dus nie prima nie.

Die enigste uitsondering op hierdie reël is die nommer 2 self, wat, omdat dit self en 1 verdeelbaar is, ook `n priemgetal is. 2 is die enigste ewe hoofgetal.

Prent getiteld Kyk of `n nommer die eerste stap is

deel n met enige getal tussen 2 en n-1. Omdat `n priemgetal geen ander faktore as homself het nie en 1 en omdat faktore van heelgetalle kleiner is as hul produk, sal die deelbaarheid van `n heelgetal kleiner as n en groter as 2 bepaal of n `n priemgetal is. Ons begin na 2 omdat ewe getalle (veelvoude van 2) nie priemgetalle kan wees nie. Dit is ver van `n doeltreffende manier om te toets, soos u hieronder sal sien.

Byvoorbeeld, as ons hierdie metode wil gebruik om te toets of 11 eerste of nie is, moet ons 11 by 3, 4, 5, 6, 7, 8, 9 en 10 verdeel, elke keer op soek na `n heelgetalle antwoord sonder rus. Aangesien nie een van hierdie nommers volledig ooreenstem met 11 nie, kan ons sê dat 11 een is eerste nommer.

Prent getiteld Kyk of `n nommers eerste stap 4 is

Om tyd te bespaar, toets jy net op sqrt (n), afgerond. Om `n getal n te toets deur al die nommers tussen 2 en n-1 te kontroleer, kan baie tyd duur. As ons byvoorbeeld wil bepaal of 103 met hierdie metode `n priemgetal is, moet ons met 3, 4, 5, 6, 7 ... ens. Verdeel tot 102! Gelukkig is dit nie nodig om hierdie manier te toets nie. In die praktyk is dit slegs nodig om te toets deur die faktore tussen 2 en die vierkantswortel van n. As die vierkantswortel van n nie `n getal is nie, draai dit na die naaste heelgetal en toets aan hierdie nommer. Kyk hieronder vir `n verduideliking:

Kom ons ondersoek die faktore van 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 en 100 × 1. Let daarop dat na 10 × 10 die faktore dieselfde is soos dit vir 10 × 10, net omgedraai. In die algemeen kan ons die faktore van n groter as sqrt (n) ignoreer omdat hulle bloot `n voortsetting van faktore kleiner as sqrt (n) is.

Kom ons probeer `n voorbeeld. As n = 37, hoef ons nie alle getalle van 3 tot 36 te toets om te bepaal of n `n priemgetal is nie. In plaas daarvan moet ons net die getalle tussen 2 en sqrt (37) (afgerond) sien.

sqrt (37) = 6.08 - ons gaan dit tot 7 rond.

37 is nie heeltemal deelbaar met 3, 4, 5, 6 en 7 nie en ons kan dus met selfvertroue sê dat dit een is eerste nommer is.

Prent getiteld Kyk of `n nommer is Prime Step 5

Om nog meer tyd te bespaar, gebruik ons slegs primêre faktore. Dit is moontlik om die proses van toetsing te maak deur selfs korter te deel deur nie die faktore insluit wat nie primes is nie. Per definisie kan elke saamgestelde getal uitgedruk word as die produk van twee of meer priemgetalle. Dus verdeel die getal n deur `n saamgestelde getal is oorbodig - dit is gelykstaande aan die verdeling van verskeie tye deur primes. Dus, ons kan die lys van moontlike faktore verder beperk tot slegs primêre getalle kleiner as sqrt (n).

Dit beteken dat al die faktore, sowel as die faktore wat veelvoude van priemgetalle is, oorgeslaan kan word.

Byvoorbeeld, laat ons probeer om te bepaal of 103 `n eerste nommer is of nie. Die vierkantswortel van 103 is 11 (afgerond). Die priemgetalle tussen 2 en 11 is 3, 5, 7 en 11. 4, 6, 8 en 10 is ewe en 9 is `n veelvoud van 3, `n priemgetal, sodat ons dit kan oorskiet. Deur dit te doen, het ons ons lys van moontlike faktore tot net 4 getalle verminder!

103 is nie ten volle deelbaar met 3, 5, 7 of 11 nie, dus weet ons nou dat 103 a eerste nommer is.

Metode 2
Gebruik die klein Fermatstelling

In 1640 het die Franse wiskundige Pierre de Fermat vir die eerste keer `n stelling geponeerd (welke nou na hom vernoem is) wat baie behulpsaam kan wees by die bepaling of `n getal wel of nie `n priemgetal is. Tegnies gesproke, Fermat se toets is daarop gemik om seker te maak dat `n nommer in plaas van `n priemgetal saamgestel word. Dit is omdat die toets met "absolute sekerheid" kan wys dat `n getal saamgestel is, maar slegs een "waarskynlikheid" of `n nommer `n priemgetal is. Fermat se klein stelling is nuttig in situasies waar poging om te verdeel, nie prakties is nie en wanneer daar `n lys van getalle is wat uitsonderings op die stelling is.

Prent getiteld Kyk of `n nommer is Prime Step 6

Gestel dit n Die nommer is om te toets. U gebruik hierdie toets om te bepaal of `n gegewe getal n `n priemgetal is. Maar, soos hierbo aangedui, kan hierdie stelling soms sekere saamgestelde foutiewe getalle as `n primêre nommer identifiseer. Dit is belangrik om dit in ag te neem en jou antwoord te kontroleer, iets wat hieronder verduidelik word.

Prent getiteld Kyk of `n nommers eerste stap 7 is

Kies `n heelgetal a tussen 2 en n-1 (insluitend). Die presiese heelgetal wat u kies, is nie belangrik nie. Omdat die parameters vir `n 2 en n-1 insluit, kan jy dit ook gebruik.

`N Voorbeeld: Is 100 `n priemgetal of nie. Gestel ons neem 3 as `n toetswaarde - dit is tussen 2 en n-1, dus dit voldoen.

Prent getiteld Kyk of `n nommer is Prime Step 8

Bereken aⁿ (mod n). Die uitwerking van hierdie uitdrukking vereis `n bietjie kennis van `n wiskundige stelsel genoem modulêre wiskunde. In modulêre wiskunde, nommers terug na nul wanneer hulle `n sekere waarde bereik, ook genoem die modulus. U kan dit as `n horlosie dink: op die ou end sal die klokhand terug skiet na 1 uur na 12 uur, nie tot 13 uur nie. Die modulus word aangetoon as (mod n). So in hierdie stap bereken jy aⁿ met `n modulus van n.

Nog `n metode is om a te berekenⁿ, en verdeel dit dan deur n, waarna jy die res as jou antwoord gebruik. Gespesialiseerde sakrekenaars met `n modulus funksie kan baie nuttig wees wanneer groot getalle verdeel word omdat hulle die res van `n afdeling dadelik kan bereken.

As ons so `n sakrekenaar in ons voorbeeld gebruik, kan ons sien dat 3¹⁰⁰/ 100 het `n restant van 1. Dus, 3¹⁰⁰ (mod 100) 1.

Prent getiteld Kyk of `n nommers eerste stap 9 is

As ons dit met die hand bereken, dan gebruik ons die eksponent as `n kort notasie. As jy nie `n sakrekenaar met `n modulusfunksie het nie, gebruik die notasie met `n eksponent om die prosedure vir die bepaling van die res makliker te maak. Sien hieronder:

In ons voorbeeld bereken ons 3¹⁰⁰ met `n modulus van 100. 3¹⁰⁰ is `n baie groot getal - 515,377,520,732,011,331,036,461,129,765,621,272,702,107,522,001 - so groot dat dit baie moeilik is om mee te werk. Eerder as om die 48-syfer-antwoord vir 3 te gebruik¹⁰⁰, ons kan dit beter as `n eksponent opmerk, so (((((((3²) * 3)²)²)²) * 3)²)². Onthou dat die eksponent van `n eksponent gebruik word om die eksponente te vermenigvuldig (x^y)^z = x^yz).

Nou kan ons die res bepaal. Begin deur die oplossing van ((((((((3²) * 3)²)²)²) * 3)²)² by die binneste stel hakies en werk verder, waar jy elke stap met 100 verdeel. Sodra ons die res gevind het, gebruik ons dit vir die volgende stap in plaas van as die werklike antwoord. Sien hieronder:

((((((((9) * 3)²)²)²) * 3)²)² - 9/100 het geen rus nie, so ons kan voortgaan.

((((((27)²)²)²) * 3)²)² - 27/100 het geen rus nie, so ons kan voortgaan.

(((((729)²)²) * 3)²)² - 729/100 = 7 R 29. Ons restant is 29. Ons gaan voort met die volgende stap, en nie met 729 nie.

((((29²=841)²) * 3)²)² - 841/100 = 8 R 41. Ons gebruik ons res 41 weer in die volgende stap.

(((41² = 1681) * 3)²)² - 1681/100 = 16 R 81. Ons gebruik ons res 81 in die volgende stap.

((81 * 3 = 243)²)² - 243/100 = 2 R 43. Ons gebruik ons oorblywende 43 in die volgende stap.

(43² = 1849)² - 1849/100 = 18 R 49. Ons gebruik ons oorblywende 49 in die volgende stap.

49² = 2401 - 2401/100 = 24 R 1. ons finale res is 1. Met ander woorde, 3¹⁰⁰ (mod 100) = 1. Let daarop dat dit dieselfde antwoord is as wat ons in die vorige stap bereken het!

Prent getiteld Kyk of `n nommers eerste stap 10 is

Kontroleer of nie aⁿ (mod n) = a (mod n). Indien nie, dan is n saamgestel. Indien waar, dan n Waarskynlik, (maar nie seker nie) `n priemgetal. Herhaling van die toets met verskillende waardes vir `n kan die uitkoms veiliger maak, maar daar is skaars saamgestelde getalle wat voldoen aan Fermat se stelling vir alle waardes van a. Dit word die Carmichaelgetalle genoem - die kleinste van hierdie getalle is 561.

In ons voorbeeld, 3¹⁰⁰ (mod 100) = 1 en 3 (mod 100) = 3. 1 ≠ 3, dus ons kan sê dat 100 `n saamgestelde getal is.

Gebruik die Carmichael nommers om seker te wees van jou uitkoms. Om te weet watter getalle die Carmichael-volgorde ontmoet voordat jy aangaan, kan jy baie bekommer oor of `n nommer `n priemgetal is al dan nie. Oor die algemeen is Carmichael getalle die produk van afsonderlike primes, waarby vir al die priemgetalle geld dat as p `n deler is van n, dat ook p-1 `n deler is van n-1. Die aanlyn lys van Carmichael-nommers kan baie nuttig wees om, met behulp van Fermat se klein stelling, te bepaal of `n nommer `n priemgetal is.

Metode 3
Gebruik die Miller-Rabin-toets

Die Miller-Rabin-toets werk op dieselfde manier as Fermat se klein stelling, maar gaan beter af met afwykende getalle soos Carmichael-nommers.

Prent getiteld Kyk of `n nommers eerste stap 12 is

Stel n is `n vreemde getal wat ons op primaliteit wil toets. Soos in die bogenoemde metodes, is n die veranderlike wat ons die primaliteit van.

Prent getiteld Kyk of `n nommers eerste stap 13 is

druk n-1 af in die vorm 2^s × d waarby d is vreemd. Die getal n is `n priemgetal as dit vreemd is. So n - 1 moet dan ewe wees. Omdat n - 1 selfs is, kan dit geskryf word as `n krag van 2 keer `n vreemde getal. Dus, 4 = 2² × 1-80 = 2⁴ × 5- en so aan.

Veronderstel ons wil bepaal of n = 321 `n priemgetal is. 321 - 1 = 320, wat ons kan uitdruk as 2⁶ × 5.

In hierdie geval is n = 321 `n geskikte getal. Die bepaling van n - 1 vir n = 371 kan `n groot waarde vir d vereis, wat die proses in `n later stadium moeiliker maak. 371 - 1 = 370 = 2¹ × 185

Prent getiteld Kyk of `n nommers eerste stap 14 is

Kies `n ewekansige nommer a tussen 2 en n-1. Die presiese nommer wat u kies, is irrelevant - net dat dit kleiner as n en groter as 1 moet wees.

In ons voorbeeld met n = 321, kies ons a = 100.

Prent getiteld Kyk of `n nommers eerste stap 15 is

Bereken a^d (mod n). as a^d = 1 of -1 (mod n), dan slaag n die Miller-Rabin toets en is waarskynlik `n priemgetal. Soos met die Kleinvaste stelling, kan hierdie toets nie die primaliteit van `n getal met absolute sekerheid bepaal nie, maar vereis addisionele toetse.

In ons voorbeeld met n = 321, a^d (mod n) = 100⁵ (mod 321). 100⁵ = 10,000,000,000 (mod 321) = 313. Ons gebruik `n spesiale sakrekenaar, of die verkorte metode met `n eksponent soos vroeër beskryf, om die res van 100 te vind⁵/ 321.

Omdat ons nie 1 of -1 gekry het nie, kan ons nie met sekerheid sê dat n `n priemgetal is nie. Maar daar is meer om te doen - lees verder.

Prent getiteld Kyk of `n nommers eerste stap 16 is

Omdat die resultaat nie gelyk is aan 1 of -1 nie, bereken a^2d, a^4d, ... en so aan, tot en met a²^s-1d. Bereken a tot die krag van d keer, tot 2^s-1. As een van hierdie gelyk is aan 1 of -1 (mod n), dan slaag n die Miller-Rabin toets en is waarskynlik `n eerste. As jy vasgestel het dat n die toets bevredig, kyk dan jou antwoord (sien die stap hieronder). As n nie aan een van hierdie toetse voldoen nie, dan is dit een saamgestel getal.

As `n herinnering, in ons voorbeeld is die waarde van a gelyk aan 100, die waarde van s is 6 en van d 5. Ons gaan voort om te toets soos hieronder aangedui:

100^{2d = 10} = 1 × 10²⁰.

1 × 10²⁰ (mod 321) = 64. 64 ≠ ` 1 of -1. Hou stil.

100^{4d = 20} = 1 × 10⁴⁰.

1 × 10⁴⁰ (mod 321) = 244. 244 ≠ 1 of -1.

Ons kan op hierdie punt stop. s - 1 = 6 - 1 = 5. Ons het nou 4d = 2² behaal, en daar is geen magte van 2 keer d onder 5d nie. Omdat geen van ons berekeninge `n 1 of -1 antwoord gegee het nie, kan ons sê dat n = 321 a saamgestel getal is.

Prent getiteld Kyk of `n nommers eerste stap 17 is

as n voldoen aan die Miller-Rabin toets, herhaal dit vir die ander waardes van a. As jy gevind dat die waarde van n wel eens `n priemgetal kan wees, probeer dan weer met `n ander, arbitrêre waarde vir a om die uitkoms van die toets te bevestig. As n eintlik `n priemgetal is, dan sal dit klop vir elke waarde van a. As n `n saamgestel getal is, dan sal die mislukking vir driekwart van die waardes van a. Hiermee het jy meer sekerheid as met die Klein stelling van Fermat, waarby bepaalde saamgestelde getalle (die Carmichael getalle) die toets deurstaan het vir elke waarde van a.

Metode 4
Gebruik die Chinese rus

Prent getiteld Kyk of `n nommers eerste stap is 18

Kies twee getalle. Een van die getalle is nie `n priemgetal nie en die tweede is die getal wat vir primaliteit getoets word.

"Toetsnommer1" = 35
Toetsnommer2 = 97

Prent getiteld Kyk of `n nommer is eerste stap 19

Kies twee data punte groter as nul en kleiner as Toets nommer1 en Toets nommer2, onderskeidelik. Hulle kan nie gelyk wees aan mekaar nie.

Data1 = 1

Data2 = 2

Prent getiteld Kyk of `n nommers eerste stap 20 is

Bereken die MMI (Wiskundige Vermenigvuldigingsinverse) vir Toetsnommer1 en Toetsnommer2

Bereken die MMI

MMI1 = Toetsnommer2 ^ -1 Mod Toetsnommer1

MMI2 = Toetsnommer1 ^ -1 Mod Toets nommer2

Slegs vir priemgetalle (daar sal `n oplossing wees vir nie-priemgetalle, maar dit is nie die MMI nie):

MMI1 = (Toetsnommer2 ^ (Toetsnommer1-2))% Toetsnommer1

MMI2 = (Toetsnommer1 ^ (Toetsnommer-2))% Toetsnommer2

dus:

MMI1 = (97 ^ 33)% 35

MMI2 = (35 ^ 95)% 97

Prent getiteld Kyk of `n nommers eerste stap 21 is

Skep `n binêre tabel vir elke MMI tot by Log2 van die modulus

Vir die MMI1

F (1) = Toetsnommer2% Toetsnommer1 = 97% 35 = 27

F (2) = F (1) * F (1)% Toets nommer1 = 27 * 27% 35 = 29

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

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

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

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

Bereken die binêre logaritme van Toets nommer1 - 2

35 -2 = 33 (10001) basis 2

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

MMI1 = F (33) = 1 * 27 Mod 35

MMI1 = 27

Vir MMI2

F (1) = Toetsnommer1% Toetsnommer2 = 35% 97 = 35

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

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

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

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

F (32) = F (16) * F (16)% Toets nommer 2 = 35 * 35 mod 97 = 61

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

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

Bereken die binêre logaritme van Toets nommer2 - 2

97 - 2 = 95 = (1011111) basis 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

Prent getiteld Kyk of `n nommer is eerste stap 22

Bereken (Data1 * Toetsnommer2 * MMI1 + Data2 * Toetsnommer1 * MMI2)% (Toetsnommer1 * Toetsnommer)

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

Antwoord = (2619 + 4270)% 3395

Antwoord = 99

Prent getiteld Kyk of `n nommer is Prime Step 23

Kyk of "Toetsnommer1" is nie `n eerste nommer nie

Bereken (Antwoord - Data1)% Toetsnommer1

99 -1% 35 = 28

Omdat 28 groter as 0 is, is 35 nie `n priemgetal nie

Prent getiteld. Kontroleer of `n nommer die eerste stap is

Kontroleer dat Toetsnommer2 `n priemgetal is

Bereken (Antwoord - Data2)% Toetsnommer2

99 - 2% 97 = 0

Omdat 0 0 is, is 97 `n potensiële primitiewe getal

Prent getiteld Kyk of `n nommer is Prime Step 25

Herhaal stap 1 tot 7 ten minste twee keer.

As stap 7 gelyk is 0:

Gebruik `n ander "Toetsnommer1" indien toets nommer1 nie `n priemgetal is nie.

Gebruik `n ander toetsnommer1 waar `n toetsnommer1 eintlik `n priemgetal is. In hierdie geval is stappe 6 en 7 gelyk aan 0.

Gebruik verskillende data punte vir data1 en data2.

As stap 7 altyd gelyk is aan 0, is die waarskynlikheid dat nommer2 `n priemgetal is, baie hoog.

Stappe 1 tot 7 is onakkuraat in sekere gevalle wanneer die eerste getal nie `n priemgetal is nie en die tweede is `n primêre faktor van die niepromgetal "Toetsnommer1". Dit werk in alle scenario`s waarvan albei getalle primes is.

Die rede is dat die stappe 1 tot en met 7 herhaal word, is omdat daar `n paar scenario`s is waarby, selfs as Testgetal1 geen priemgetal is en Testgetal2 geen priemgetal, een van beide getalle van stap 7 nog steeds nul is. Hierdie omstandighede is skaars. Deur die verandering van Testgetal1 in `n ander nie-priemgetal, as Testgetal2 geen priemgetal is, sal Testgetal2 nie meer gelyk is aan nul, in stap 7. Met die uitsondering van die geval waarby "Toetsnommer1" is `n faktor van Toets nommer2, primes sal altyd nul wees in stap 7.

wenke

Die 168 primes onder die 1000 is: 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
As jy probeer om te verdeel, stadiger is as die meer gesofistikeerde metodes, is dit steeds doeltreffend vir kleiner getalle. Selfs wanneer groter getalle getoets word, is dit nie ongewoon om eers die klein getalle te kontroleer voordat hulle oorskakel na die meer gevorderde metodes nie.