Výpočet "odmocnin" modulo prvočíslo p splňující p = 3 (mod 4)
(Jaroslav Seděnka)
Zadání. Necht p je prvočíslo splňující p = 3 (mod 4). Buď m G Zp pevně dané. Najděte k G Zp splňující k2 = m (mod p).
Řešení: Využijeme vlastnosti, kterou mají všechny druhé mocniny (mod p), a tou je kon-gruence
m(p-i)/2 = 1   (mod p)
Tuto kongruenci dokážeme posléze jako Lemma 1. Hned vidíme
m(p+iy2 = m^p_1^2m = m   (mod p)
(Všimněte si, že p je z předpokladů liché, takže (p — l)/2 a (p + l)/2 jsou celá čísla; v opačném případě bychom na ně vůbec nemohli umocňovat!)
Ovšem dokonce i (p + l)/4 je celé číslo, proto můžeme spočíst k! =
m(p+i)/4 (mod p) a takové
číslo bude splňovat (k')2 = (m(p+1)/4)2 = m^p+1^4)'2 = m^p+1^2 = m (mod p). Našli jsme tedy hledanou druhou odmocninu.
Lemma 1. Nechi; p = 3 (mod 4) je prvočíslo, m G Zp je libovolné. Pak platí
(p-i)/2     I 1       pokud existuje k G Zp splňující k2 = m   (mod p) 1—1 jinak
Důkaz. Buď £ libovolný primitivní kořen (mod p), pak £ splňuje rovnici (£(p-i)/2 + !)(c(p-i)/2 _ x) = cp-i _ x = q   (mod p)
(Zejména CP_1 = 1 (mod p)5 protože </?(p) = p — 1.)
Přitom £ generuje celé Zp\{0}, takže £(p-1)/2 ^ 1 (mod p), musí být £(p-1)/2 = —1 (mod p). Když si napíšeme m = Qa, máme
m(p-l)/2 = (s«)(p-l)/2 = (s(p-l)/2^a = (_^a     (mod ^
Pro a sudé je Qal2 odmocninou z m = (a, pro a liché taková odmocnina neexistuje:.
□