Primtallstest: Forskjell mellom sideversjoner

En '''primtalstest''' er en [[algoritme]] som avgjør hvorvidt et gitt [[heltall]] ''n'' er ettet [[primtall]], det vil si at det ikke er delbart med noe heltall foruten 1 og ''n'' (seg selv). Å avgjøre hvorvidt ett tall er et primtall er beregningsmessig betydelig enklere enn å [[Primtallsfaktorisering|faktorisere]] tallet. Dette skillet ligger til grunn for [[krypteringsalgoritme]]r som [[RSA]].

De snabbasteraskeste primtalstestenprimtallstestene förfor storastore taltall ärer [[probabilistiskprobabilistiske algoritmalgoritmer|probabilistiskaprobabilistiske]], vilkethvilket innebärinnebærer attat taltall som avgörsavgjøres varaå sammansattavære garanteratsammansatte integarantert ärikke primaer primtall, men attat sammansatta[[Sammensatt taltall|sammensatte felaktigttall]] kan utpekasfeilaktig utpekes som primaprimtall. SådanaSlike metoder dugerer inteikke förpassende attfor matematisktå bevisabevise attat taltall ärer primaprimtall, men ärer fullt tillräckligaut förbrukbare nästanfor allanesten praktiskaalle tillämpningarpraktiske eftersomtilnærminger sannolikhetenettersom försannsynligheten felaktigafor svarfeil kaner görasastronomisk astronomisktlav. låg,Eksempelvis exempelvislavere lägreenn änsannsynligheten sannolikhetenfor förat att beräkningens utgångberegningsresultatet skulle havært påverkatspåvirket av [[kosmisk strålningstråling]] som stört kretsarnaforstyrrer idatamaskinens datornkretskort.<ref>Donald Knuth, ''The Art of Computer Programming'' vol 2, s. 395</ref>

DetDen enklasteenkleste ochog snabbasteraskeste probabilistiskaprobalistiske primtalstestetprimtallstesten ärer [[Fermats primtalstest]], som dessvärredessverre gergir felfeil svar tämligenganske oftaofte ochog därmeddermed måstemå kompletteraskomplementeres med någonen noe mer robust metodmetode. StandardtestetStandardtesten i ärdag idager [[Miller-Rabins test]], exempelviseksempelvis använtanvendt av mångamange [[datoralgebrasystemalgebrasystem]], varsimplementert tillförlitligheti kandatamaskiner, justerassom tillkan godtyckligjusteres nivåtil genomet attakseptabelt väljanivå rättgjennom uppsättningå primtal somvelge "vittnen" för attrette ''nprimtallsvitner'' är ett primtal. Om ''k'' stycken små primtalprimtall väljsvelges som vittnenvitne, ärer sannolikhetensannsynligheten förfor attat Miller-Rabin-testettesten targir felfeil högsthøyst (1/4)^{&minus;−''k''}, ochog troligtvisantageligvis mycketmye mindre i praktikenpraksis. GenomGjennom attå väljavelge specifikaspesifikke, välstuderadevelstuderte uppsättningaroppsetninger talav primtall kan Miller-Rabin-testettesten görasgjøres fullständigtfullstendig säkertsikker förfor allalle taltall mindre änenn 10¹⁶, ochog ärer dåda mycketmye snabbareraskere änenn trial division. Miller-Rabins test ärer en förbättringforbedring av [[Solovay-Strassens test]].

DeterministiskaDeterministiske testtester kan rigoröstrigorøst bevisabevise attat ett taltall ärer primt, men ärer isom regel långsammarelangsommere änen probabilistiskaprobabilistiske metoder. Det mest användaanvendte deterministiskadeterministiske testettesten ärer [[ECPP]] som använderanvender [[elliptiskaelliptiske kurvorkurver]]. Metoden gergir inteikke barabare svaret primt/sammansattsammensatt, utanmen returnerarreturnerer ävenogså ett formelltformelt bevis vars riktighet kanuten verifierasat utanhele attberegningen upprepamå helaramses beräkningenopp.

Den optimalaoptimale [[tidskomplexitettidskompleksitet]]en förfor primtalstestprimtallstest ärer ett välstuderatvelstudert teoretisktteoretisk problem. UpptäcktenOppdagelsen av [[AKS-algoritmen]] i år 2002 innebärinnebar attat deterministiskadeterministiske primtalsbevisprimtallsbevis bevisligenbeviselig ärer möjligamulige i [[polynomiell tid]]. ECPPMan harantar ävenat sedanECPP tidigare förmodats hahar tidskomplexitetentidskompleksiteten

vilkethvilket ärer en polynomiell tid, men dettadette har liksomsom förfor fleraflere andraandre primtalstestprimtallstester ännuikke inteblitt bevisatsbevist rigoröstrigorøst.

FörFor taltall på specillaspesielle former ärer det iblandi möjligtblant attmulig genomföraå deterministiskagjennomføre primtalstestdeterministiske betydligtprimtalstester snabbare än för tal ibetydelig allmänhetraskere. DettaDette gällergjelder framförspesielt allt taltall ''n'' förfor vilkahvilket ''n''&minus;1−1 eller ''n''+1 har en enkel [[faktorisering]]. Det främstafremste exempleteksempelet ärer [[mersennetalmersennetall]], taltall som ärer ett mindre änenn en [[tvåpotenstopotens]], förfor vilkahvilke [[Lucas-Lehmers test]] kan användasanvendes. Lucas-Lehmers test har använtsblitt anvendt förfor attå hittafinne de störstastørste kändakjente primtalenprimtall, som har överover 9 miljonermillioner siffrorsiffer.

[[Kategori:TalteoriTallteori]]