ads2_2022/protocol/woche13.md

Vorlesungswoche 13 (27. Juni – 3. Juli 2022)

Agenda

• ein wenig Algebra:
  • modulare Arithmetik
  • zyklische (Unter)gruppen; Anwendung ф(n) := ord((ℤ/nℤ)ˣ).
  • der kleine Fermat: a^ф(n) ≡ 1 mod n.
• Euklid:
  • Rekursives Ausrechnen von d := ggT(a,b).
  • Extrahieren der Koeffizienten für die Gleichung d = xa + yb.
  • Anwendung auf Sonderfall d = 1 für Inversion modulo n.
• Pollard-Rho
  • Was liefert der Algorithmus?
  • Was garantiert das?
  • Referenzen:
    • Algorithmus im Kurs (exp-Abstände), siehe:
      http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap33.htm
    • Andere Variante (lineare Abstände), siehe:
      https://link.springer.com/article/10.1007/BF01933667 und
      https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/theorems-on-factorization-and-primality-testing/6762E84DBD34AEF13E6B1D1A8334A989

Nächste Woche/n

• Wiederholung zur Klausurvorbereitung