Zwei Zahlen sind relativ prim zueinander, wenn sie keinen gemeinsamen Teiler besitzen außer 1. Will man z.B. feststellen, ob 14 und 15 relativ prim zueinander sind, zerlegt man beide in Ihre Primfaktoren:

14 = 2 × 7
15 = 3 × 5

Beide Zahlen sind also relativ prim. Man kann auch sagen: Der größte gemeinsame Teiler ist 1. Anders sieht es aus bei 70 und 165:

70 = 2 × 5× 7
165 = 3 × 5 × 11

Der gemeinsame Faktor lautet 5. Die Zahlen sind nicht relativ prim.

Zurück zu RSA.

(c) Autor und Copyright Wolf Hosbach