RSA

Matematisk baggrund

Primtal

Et primtal er et tal der kun kan divideres med sig selv og 1.

Eksempler

9 er ikke et primtal for det kan divideres med 3

7 er et primtal

21 er ikke et primtal det kan divideres med 3 og 7

23 er et primtal

De første primtal

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.

Primtalsopløsning

Ethvert helt tal større end 1 som ikke er et primtal kan beskrives som produktet af flere primtal.

fx.

45 = 5 * 9 = 5 * 3 * 3

6936 = 2 x 2 x 2 x 3 x 17 = 2³ x 3 x 17

1200 = 2 x 2 x 2 x 2 x 3 x 5 = 2⁴ x 3 x 5

317 er et primtal og kan kun divideres med sig selv eller 1. Derfor kan 317 ikke beskrives som et produkt af primtal.

Indbyrdes primiske

To tal som ikke er primtal siges at være indbyrdes primiske hvis de ikke har en fælles faktor.

6 og 37 er indbyrdes primiske

6 og 27 er ikke, da 3 går op i begge tal.