Nu skal vi se på hvordan man kan undersøge om et stort tal m er et primtal.
Den hårde og langsomme metode
Hvis tallet m ikke er et primtal, så findes der et helt tal, større end 1 og mindre end m, som går op i m. Det med at finde de tal som går op i et andet tal kaldes for faktorisering. Det kan være meget svært at faktorisere store tal. Det er i bund og grund den kendsgerning der giver sikkerheden i RSA kryptering.
Som eksempel kan vi tage tallet 987654321. Er det et primtal? Ikke let at svare på. Vi kan prøve at undersøge om 2 går op i tallet. Nej, det gør det ikke, for tallet er ikke et lige tal. Går 3 op i tallet? Vi kan jo dividere tallet 987654321 med 3. Det giver 329218107. Dermed er tallet 987654321 ikke et primtal, for 3 går jo op i det
\(987654321/2 = 493827160.5\) \(987654321/3 = 329218107\)
Men hvad med tallet 9876543211. Det er ikke det samme tal som før. Er det et primtal? Hverken 2 eller 3 går op i det:
\(9876543211/2 = 4938271605.5\) \(9876543211/3 = 3292181070.3333333\)
Faktisk er tallet et primtal. Så havde vi prøvet at dividere det store tal 9876543211 med de første mange hele tal; 2, 3, 4, 5, 6, 7, 8, .., så ville ingen af divisionerne gå op.
Skal man derfor undersøge om et stort tal er et primtal, så er det ikke fornuftigt at begynde fra bunden af, og så se om 2 går op i tallet, om 3 går op i tallet, ….
Vi skal se på Fermats primtalstest, og senere Miller-Rabins primtalstest.