Legendreův symbol
Nechť p je liché prvočíslo, a ∈ Z. Legendreův symbol (a
p )
(čti a vzhledem k p) definujeme takto:
(a
p ) =



0 jestliže p | a,
1 jestliže p a a kongruence x2 ≡ a (mod p) má řešení,
−1 jestliže p a a kongruence x2 ≡ a (mod p) nemá řešení.
Jestliže (a
p ) = 1, nazývá se a kvadratický zbytek modulo p, jestliže
(a
p ) = −1, nazývá se a kvadratický nezbytek modulo p.
Zřejmě platí
a, b ∈ Z, a ≡ b (mod p) ⇒ (a
p ) = (b
p ).
Proto můžeme definici ekvivalentně přepsat také takto:
(a
p ) =



0 jestliže [a]p = [0]p,
1 jestliže [a]p ∈ Z×
p je druhou mocninou v této grupě,
−1 jestliže [a]p ∈ Z×
p není druhou mocninou v této grupě.
Lemma 1. Nechť p je liché prvočíslo, a ∈ Z. Pak
(a
p ) ≡ a(p−1)/2
(mod p).
Důkaz. Případ p | a je zřejmý. Dále předpokládejme p a.
Protože grupa Z×
p je cyklická sudého řádu p − 1, jsou druhými
mocninami prvků právě mocniny generátoru se sudým exponentem.
Je zde tedy p−1
2 prvků, které jsou druhé mocniny, a p−1
2 prvků,
které nejsou druhé mocniny.
Každý prvek grupy Z×
p je kořenem polynomu xp−1 − 1 v tělese Zp.
Protože xp−1 − 1 = (x(p−1)/2 − 1)(x(p−1)/2 + 1), je každý z prvků
Z×
p kořenem alespoň jednoho z obou polynomů stupně p−1
2 .
Protože polynom nad tělesem nemůže mít víc kořenů, než je jeho
stupeň, má každý z obou polynomů x(p−1)/2 − 1, x(p−1)/2 + 1
právě p−1
2 kořenů.
Zřejmě každá sudá mocnina generátoru je kořenem polynomu
x(p−1)/2 − 1. Množina jeho kořenů se tedy skládá právě ze sudých
mocnin generátoru, zatímco liché tvoří množinu kořenů polynomu
x(p−1)/2 + 1. Odtud plyne dokazovaná kongruence.
Důsledek 1. Pro každé liché prvočíslo p platí (−1
p ) = (−1)(p−1)/2.
Důkaz. Podle lemma 1 je (−1
p ) ≡ (−1)(p−1)/2 (mod p). Na obou
stranách kongruence je ±1, jejich rozdíl je tedy −2, 0, nebo 2.
Ovšem p 2.
Důsledek 2. Pro každé liché prvočíslo p a každé a, b ∈ Z platí
(ab
p ) = (a
p )(b
p ).
Důkaz. Podle lemma 1 je
(ab
p ) ≡ (ab)(p−1)/2 = a(p−1)/2b(p−1)/2 ≡ (a
p )(b
p )(mod p).
Na obou stranách kongruence je opět ±1, proto rovnost.
Poznámka. Každé celé číslo je kongruentní modulo p s právě
jedním z čísel 0, ±1, ±2, . . . , ±p−1
2 .
Lemma 2. Nechť p je liché prvočíslo, a ∈ Z, p a. Pro každé
i = 1, . . . , p−1
2 nechť a · i ≡ (−1)ei · bi (mod p), kde ei ∈ {0, 1},
bi ∈ {1, . . . , p−1
2 }. Pak (a
p ) = (−1)e, kde e =
(p−1)/2
i=1 ei .
Důkaz. Víme, že {b1, . . . , b(p−1)/2} ⊆ {1, . . . , p−1
2 }. Ukažme
sporem, že zde platí rovnost. Jestliže zde není rovnost, existují
1 ≤ i < j ≤ p−1
2 tak, že bi = bj . Pak a · i ≡ ±a · j (mod p), což
vzhledem k p a dává i ≡ ±j (mod p), a to je spor. Vynásobením
kongruencí a(p−1)/2 · (p−1
2 )! ≡ (−1)e · (p−1
2 )!(mod p). Protože
p (p−1
2 )!, plyne odtud a(p−1)/2 ≡ (−1)e (mod p) a lemma 1 dává
(a
p ) ≡ (−1)e (mod p). Na obou stranách je ±1, proto rovnost.
Lemma 3. Nechť p je liché prvočíslo, a ∈ Z, p a. Pak
(a
p ) = (−1)
P(p−1)/2
i=1 [2ai
p
]
.
Důkaz. Platí ai
p = [ai
p ] + ai
p , a tedy a · i ≡ p · ai
p (mod p).
V lemma 2 je tedy ei = 0, právě když ai
p < 1
2. Odtud ei = [2 ai
p ].
Platí [2ai
p ] = [2[ai
p ] + 2 ai
p ] = 2[ai
p ] + [2 ai
p ] = 2[ai
p ] + ei . Proto
(−1)
[2ai
p
]
= (−1)ei . Lemma 2 dává dokazované.
Důsledek 3. Pro každé liché prvočíslo p platí (2
p ) = (−1)(p2−1)/8.
Důkaz. Pro 1 ≤ i ≤ p−1
2 platí 0 < 4i
p < 2, a tedy [4i
p ] ∈ {0, 1}.
Přitom [4i
p ] = 1 ⇔ 4i
p ≥ 1 ⇔ i ≥ p
4 ⇔ i > [p
4 ]. Proto
(p−1)/2
i=1 [4i
p ] = p−1
2 − [p
4 ].
Nechť p = 4k ± 1 pro k ∈ N. Pak p−1
2 = 2k + ±1−1
2 ,
[p
4 ] = k + [±1
4 ], a tedy p−1
2 − [p
4 ] = k.
Současně platí p2−1
8 = 16k2±8k
8 = 2k2 ± k.
Užitím lemma 3 dostáváme (2
p ) = (−1)
P(p−1)/2
i=1 [ 4i
p
]
= (−1)(p2−1)/8.
Lemma 4. Nechť p je liché prvočíslo, a ∈ Z, p a, 2 a. Pak
(a
p ) = (−1)
P(p−1)/2
i=1 [ai
p
]
.
Důkaz. Platí
(p−1)/2
i=1 i = p2−1
8 . Protože je a liché, je a+p
2 ∈ Z.
Užitím lemma 3 a důsledků 3 a 2 dostáváme (−1)
P(p−1)/2
i=1 [ ai
p
]
=
= (−1)
P(p−1)/2
i=1 [
(a+p)i
p
]−i
=
a+p
2
p · (2
p ) = (a+p
p ) = (a
p ).
Kvadratický zákon reciprocity
Věta 1. Pro lichá prvočísla p = q platí (q
p ) · (p
q ) = (−1)
p−1
2
·q−1
2 .
Důkaz. V kartézské soustavě souřadnic si představme obdélník,
jehož strany leží na osách a na přímkách x = p
2 , y = q
2 . Uvnitř
tohoto obdélníku leží právě p−1
2 · q−1
2 mřížových bodů (tedy bodů,
jejichž obě souřadnice jsou celá čísla).
Jeho úhlopříčka leží na přímce y = q
p x, žádný z mřížových bodů
uvnitř obdélníku neobsahuje a rozděluje obdélník na dva
trojúhelníky.
Pro pevně zvolené i ∈ {1, . . . , p−1
2 } je uvnitř „dolního trojúhelníku
právě [qi
p ] mřížových bodů s x-ovou souřadnicí i. Proto je
uvnitř „dolního trojúhelníku právě
(p−1)/2
i=1 [qi
p ] mřížových bodů.
Ze symetrie je uvnitř „horního trojúhelníku právě
(q−1)/2
i=1 [pi
q ]
mřížových bodů.
Dostali jsme p−1
2 · q−1
2 =
(p−1)/2
i=1 [qi
p ] +
(q−1)/2
i=1 [pi
q ].
Věta nyní plyne z lemma 4.
Jacobiho symbol
Pro usnadnění počítání Legendreova symbolu (a
p ) pro konkrétní
hodnoty a, p tento symbol nyní zobecníme.
Nechť b ∈ N je liché číslo, a ∈ Z. Je-li b = 1, klademe (a
b ) = 1.
Je-li b > 1, rozložíme b na součin prvočísel b = p1 · p2 . . . ps.
Jacobiho symbol (a
b ) pak definujeme rovností
(a
b ) = ( a
p1
) · ( a
p2
) . . . ( a
ps
).
Lemma 5. Jsou-li b, d ∈ N lichá čísla, a, c ∈ Z, pak
( ac
bd ) = (a
b )(c
d ).
Důkaz. Plyne z definice a důsledku 2.
Lemma 6. Jsou-li a, b ∈ N lichá čísla, pak
(−1)(a−1)/2(−1)(b−1)/2 = (−1)(ab−1)/2.
Důkaz. Máme dokázat a−1
2 + b−1
2 ≡ ab−1
2 (mod 2). Ekvivalentně
(a − 1) + (b − 1) ≡ ab − 1(mod 4), neboli 4 | (a − 1)(b − 1).
To však zřejmě platí.
Důsledek 4. Pro každé liché číslo b ∈ N platí (−1
b ) = (−1)(b−1)/2.
Důkaz. Plyne z definice, lemma 6 a důsledku 1 indukcí.
Lemma 7. Jsou-li a, b ∈ N lichá čísla, pak
(−1)(a2−1)/8(−1)(b2−1)/8 = (−1)(a2b2−1)/8.
Důkaz. Máme dokázat a2−1
8 + b2−1
8 ≡ a2b2−1
8 (mod 2).
Ekvivalentně (a2 − 1) + (b2 − 1) ≡ a2b2 − 1(mod 16), neboli
16 | (a2 − 1)(b2 − 1). Platí dokonce 64 | (a2 − 1)(b2 − 1).
Důsledek 5. Pro každé liché číslo b ∈ N platí (2
b ) = (−1)(b2−1)/8.
Důkaz. Plyne z definice, lemma 7 a důsledku 3 indukcí.
Věta 2. Pro lichá nesoudělná a, b ∈ N platí (b
a )·(a
b ) = (−1)
a−1
2
· b−1
2 .
Důkaz. Rozložme na součin prvočísel a = p1 · p2 . . . ps,
b = q1 · q2 . . . qt. Z lemma 5 a věty 1 plyne užitím lemma 6
(b
a ) · (a
b ) = s
i=1
t
j=1(pi
qj
) · (
qj
pi
) = s
i=1
t
j=1(−1)
pi −1
2
·
qj −1
2 =
= t
j=1
s
i=1(−1)
pi −1
2
qj −1
2
= t
j=1 (−1)
a−1
2
qj −1
2
=
= t
j=1(−1)
qj −1
2
a−1
2
= (−1)
b−1
2
a−1
2
= (−1)
a−1
2
· b−1
2 .
Zjednodušení vzorců
Větu 2 lze formulovat také jako rovnost
(a
b ) =
(b
a ) pro a ≡ 1 (mod 4) nebo b ≡ 1 (mod 4),
−(b
a ) pro a ≡ b ≡ 3 (mod 4),
která platí pro každá lichá čísla a, b ∈ N (i pro soudělná, kdy je na
obou stranách 0). Důsledky 4 a 5 lze formulovat takto:
(−1
b ) =
1 pro b ≡ 1 (mod 4),
−1 pro b ≡ 3 (mod 4),
(2
b ) =
1 pro b ≡ ±1 (mod 8),
−1 pro b ≡ ±3 (mod 8).
Výhoda výše uvedených rovností oproti původním je v tom, že je
vidět, že není nutné počítat hodnoty zlomků a−1
2 , b−1
2 a b2−1
8 .
Výpočet hodnoty Jacobiho, a tedy i Legendreova symbolu
Algoritmus (Jacobiho symbol). Pro daná a ∈ Z, b ∈ N, 2 b,
(a, b) = 1, algoritmus najde hodnotu Jacobiho symbolu (a
b ).
1. [Inicializace] Je-li a > 0, polož k ← 1. Je-li a < 0, polož
k ← (−1
b ), a ← −a.
2. [Jsi hotov?] Je-li b = 1, pak vytiskni k jako odpověď a skonči.
3. [Euklidovský krok] Polož r ← a mod b, u ← 0. Dokud je r sudé,
opakuj r ← r
2, u ← u + 1. Je-li u liché, polož k ← k · (2
b ).
4. [Zde je již r liché] Polož a ← b, b ← r. Jestliže platí
a ≡ b ≡ 3(mod 4), polož k ← −k. Jdi na 2.
Vzhledem k podobnosti s Euklidovým algoritmem víme, že se tento
algoritmus vždy zastaví a že je kvadratické časové náročnosti
(avšak s jinou O-konstantou než Euklidův algoritmus). Zbývá
dokázat, že dává správný výsledek. Ukažme, že vždy na začátku
kroku 3 je k · (a
b ) rovno hledané hodnotě Jacobiho symbolu. To
zřejmě platí, když jsme na začátku kroku 3 poprvé.
Důkaz správnosti algoritmu
Algoritmus (Jacobiho symbol). Pro daná a ∈ Z, b ∈ N, 2 b,
(a, b) = 1, algoritmus najde hodnotu Jacobiho symbolu (a
b ).
1. [Inicializace] Je-li a > 0, polož k ← 1. Je-li a < 0, polož
k ← (−1
b ), a ← −a.
2. [Jsi hotov?] Je-li b = 1, pak vytiskni k jako odpověď a skonči.
3. [Euklidovský krok] Polož r ← a mod b, u ← 0. Dokud je r sudé,
opakuj r ← r
2, u ← u + 1. Je-li u liché, polož k ← k · (2
b ).
4. [Zde je již r liché] Polož a ← b, b ← r. Jestliže platí
a ≡ b ≡ 3(mod 4), polož k ← −k. Jdi na 2.
Po provedení kroku 3 je nová hodnota r ≡ a(mod b), poté je
spočítáno r = r · 2−u, k = k · (2
b )u.
V kroku 4 je a = b, b = r , k = k · (−1)
a −1
2
· b −1
2 . Pak platí
k ·(a
b ) = k ·(−1)
a −1
2
·b −1
2 ·(a
b ) = k ·(−1)
b−1
2
· r −1
2 ·( b
r ) = k ·(r
b ) =
= k · (2
b )u · (r
b ) = k · (2ur
b ) = k · (r
b ) = k · (a
b ). Hodnota k · (a
b ) je
tedy na začátku kroku 3 skutečně stejná, jako byla minule.
Metoda kvadratického síta s více polynomy
Pro obecný kvadratický polynom Q(x) = Ax2 + 2Bx + C takový,
že A ∈ N, B, C ∈ Z, platí AQ(x) = (Ax + B)2 − (B2 − AC).
Pokud bude splněno N | B2 − AC, pro každé a ∈ Z dostaneme
kongruenci tvaru AQ(a) ≡ (Aa + B)2 (mod N).
Zvolíme délku 2M intervalu; protože chceme, aby maximum funkce
|Q(x)| na intervalu prosívání bylo co nejmenší, zvolíme interval
I = (−B
A − M, −B
A + M) a chceme Q(−B
A + M)
.
= −Q(−B
A ), tj.
A2M2 .
= 2(B2 − AC), tedy A
.
=
√
2(B2−AC)
M . Potom platí
max
x∈I
|Q(x)|
.
= |Q(−B
A )| = B2−AC
A
.
= M B2−AC
2 .
Protože toto číslo potřebujeme mít co nejmenší, ale současně má
být B2 − AC dělitelné číslem N, je vhodné volit A, B, C tak, aby
B2 − AC = N, kdy maximum |Q(x)| na I bude zhruba M N
2 .
Volba koeficientů polynomu Q(x) = Ax2
+ 2Bx + C
Nejdříve zvolíme délku prosívání M. Pak zvolíme A blízko
√
2N
M tak,
aby A bylo prvočíslo a N byl kvadratický zbytek modulo A.
Pak nalezneme B tak, aby B2 ≡ N (mod A).
Nakonec položíme C = B2−N
A . Pak tedy skutečně N = B2 − AC.
Dále pokračujeme stejně jako v metodě kvadratického síta – pro
každou mocninu pk prvočísla p menší než nějaká předem daná
hranice určíme kořen apk kongruence x2 ≡ N (mod pk), má-li tato
kongruence řešení (pro lichá p to znamená, že N je kvadratický
zbytek modulo p), ostatní prvočísla ignorujeme. Čísla apk
spočítáme pro všechny polynomy jen jednou a uschováme.
Protože AQ(x) = (Ax + B)2 − N, pak kořeny polynomu Q(x)
modulo pk vyhovují kongruenci Ax ≡ −B ± apk (mod pk).
V bázi faktorizace pak máme −1, 2, všechna lichá prvočísla p až
do zvolené hranice taková, že N je kvadratický zbytek modulo p, a
konečně pro každý použitý polynom Q(x) jeho koeficient A.
Vlastní algoritmus
Postupně prosíváme hodnoty jednoho polynomu Q(x) po druhém,
dokud nezískáme dostatek kongruencí pro Gaussovu eliminaci.
Protože malá prvočísla dělí hodně hodnot Q(x), trvá prosívání
malými prvočísly nejdéle, přičemž jejich logaritmus je malý.
Proto se v některých implementacích prosívání malými prvočísly
(řekněme menšími než 100) vynechává, jen je nutné zvýšit hranici,
používanou po skončení prosívání pro rozhodování, zda dotyčnou
hodnotu polynomu Q(x) budeme rozkládat nebo ne. Přitom
strategie je taková: raději zkusit rozkládat nerozložitelné Q(x), než
ztratit některé rozložitelné, a tedy nějakou užitečnou kongruenci.
Vzhledem k tomu, že získané kongruence je snadné kontrolovat, je
možné do generování kongruencí zapojit více lidí tak, že pomocí
e-mailu je jim distribuován program s daty, který nechají běžet ve
volném čase na svém počítači, a získané výsledky opět vracejí
e-mailem.
Příklad použití metody distribuovaného počítání
Metoda distribuovaného počítání e-maily s následnou kontrolou
vrácených výsledků byla s úspěchem použita při rozkládání
devátého Fermatova čísla N = 229
+ 1 v roce 1990 (toto N má
155 dekadických cifer).
A. K. Lenstra, H. W. Lenstra, M. S. Manasse a J. M. Pollard tímto
způsobem získali matici o 226 688 řádcích a 199 203 sloupcích. Po
„zahuštění této matice získali matici o 72 413 řádcích a 72 213
sloupcích. Gaussovou eliminací této matice pak získali kongruenci,
která jim určila netriviálního dělitele čísla N.
Nepoužili metodu kvadratického síta s více polynomy, ale metodu
síta v číselném tělese. Tato metoda je založena na výsledcích
algebraické teorie čísel, je tedy z námi studovaných metod
teoreticky nejnáročnější, a proto se jí budeme věnovat až do konce
semestru.