Quadratische Ergänzung: Die abc-Formel Sei p ≥ 3 eine ungerade

Quadratische Ergänzung: Die a-b-c-Formel
Sei p ≥ 3 eine ungerade Primzahl. Betrachte die quadratische Gleichung
ax2 + bx + c ≡ 0
mod p
mit ggT(a, p) = 1, d.h. a ∈ Up . Es ist dann auch ggT(4a, p) = 1, d.h.
4a ∈ Up . Wenn man die Gleichung mit 4a multipliziert, dann bekommt man
4a2 x2 + 4abx + 4ac ≡ (2ax + b)2 + 4ac − b2 ≡ 0
mod p,
also
y2 ≡ ∆
mod p,
wobei y = 2ax + b und ∆ = b2 − 4ac (Diskriminante). Die Lösungsformel
(a-b-c-Formel) aus der Schule lautet deswegen
√
−b ± b2 − 4ac
x1/2 ≡
mod p.
2a
Beachten Sie: Die Quadratwurzeln werden in Z/pZ genommen und wir
1
schreiben 2a
statt (2a)−1 in Up . Die Quadratwurzeln in Up kann man mit
dem diskreten Logarithmus berechnen. Schneller geht das mit dem TonelliShanks-Algorithmus (siehe Buch) oder dem Cipolla-Algorithmus.
1

Download Report