09. maj 2003 - 10:59Der er
22 kommentarer og 1 løsning
Primtal checker.
Ok så er jeg her igen, fyren med det matematiske tendenser.
Jeg sad og kedede mig en dag, så jeg beslutte mig for at skrive en funktion der kunne checke om et tal er et primtal den ser sådan her ud:
int IsPrime(int tal) { if(tal < 2){return 0;} int i = tal - 1;
while(tal%i != 0) i--;
if(i > 1) return 0; else return 1;
}
Simpel, nej? Den er simpel og den virker, men den er også LANGSOM, især ved store tal, så mit spørgsmål er er der ikke en mere elegant og strømlinet måde at checke om et tal er et primtal?
Ser gerne kode eksembler og rent matematiske forlkaringer.
hvis du skal have en primtalschecker der virker 100% så er der vist ikke andre måder at gøre det på, der er ikke nogen matematisk mmodel over primtal så vidt jeg ved
Jeg har ikke nogen referencer til detailjerede forklaring. Jeg har vist nogle bøger og noter liggende rundt omkring.
Men er det primtal, der skal bruges til kryptering, vil man ikke gøre det på denne måde, altså: vælge et stort tal, og set om det nu tilfældigvis skulle være et primtal. Chancen er ikke så stor, så man skal prøve mange.
I stedet for konstruerer man sig et primtal, noget i retning af: vælg et lille primtal, fx 7. Konstruer, et tilfældigt tal, der er noget større, og med garanti et primtal. Og bliv så ved til det er stort nok. Og de skal være store til kryptering.
Faktisk kan man sjældent bevise at de store tal der benyttes til kryptering rent faktisk er primtal, men man kan bevise at sandsynligheden for at de ikke er er meget meget lille.
sandsynlighed for at noget er et primtal (hvis man ellers synes man kan sige det på den måde) brugte man i gamle dage. Det du'r ikke mere, når man nu kan konstruerede tal, der med garanti er primtal.
Jeg tror nu ikke du får noget ud at se koden til sådan en stump program - med eller uden kommentarer.
Du skal forstå matematikken først. Den er lidt halvgammel (med mindre der er kommet en ny), men du kan med fordel læse i Bruce Schneier: Applied Cryptography
Hrm, ok tak jeg vil kigge efter den bog, jeg ved ikke hvem der skal ha' point..Arne_v er den eneste der hjar smidt et svar så moolah'en må gå til ham.
Synes godt om
Ny brugerNybegynder
Din løsning...
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
