Etwas Zahlentheoretie

• Beobachtung: wenn n = p ^. q für große (z. b. $\approx$ 10¹⁰⁰) Primzahlen p, q, dann kann man p, q aus n allein praktisch nicht bestimmen.
• (Kleiner) Satz von Fermat/Euler: für ggT(x, n) = 1 gilt gilt x^$\phi$(n) $\equiv$ 1 mod n.

  wobei $\phi$(n) = | F(n)| mit F(n) = {y | 0 < y < n, ggT(y, n) = 1}

  (alle Zahlen in {1, 2, n - 1}, die zu n teilerfremd sind)

• Folgerung: wenn a $\equiv$ 1 mod$\phi$(n), dann x^a $\equiv$ x(mod n). (Entschlüsselung)
• man kann $\phi$(n) aber nur bestimmen, wenn man p, q kennt: $\phi$(n) = $\phi$(p)$\phi$(q) = (p - 1)(q - 1).