Hledání netriviálního dělitele pomocí eliptických křivek
Mějme opět dáno složené přirozené číslo N, které chceme rozložit.
Je přirozené předpokládat, že (N, 6) = 1. Zvolme a, b ∈ Z tak, aby
(4a3 + 27b2, N) = 1. Pak rovnice
y2
z = x3
+ axz2
+ bz3
nám určuje „eliptickou křivku (E, O) nad ZN, přičemž
O = [0, 1, 0] ∈ P2(ZN). Nechť p je nějaké (neznámé) prvočíslo
dělící N. Předchozí rovnicí je zadána eliptická křivka (Ep, Op),
přičemž Op = [0, 1, 0] ∈ P2(Fp).
Připomeňme, že (Ep, +) je komutativní grupa a podle Hasseovy
věty platí |Ep| = p + 1 − ap, kde celé číslo ap splňuje |ap| < 2
√
p.
Na množině E máme definovánu částečnou operaci +, přičemž
kdykoli známe nějaké body P = [α1, β1, 1], Q = [α2, β2, 1] ∈ E
takové, že P + Q není definováno, snadno najdeme netriviálního
dělitele čísla N.
Navíc existuje částečný homomorfismus fp : E → Ep takový, že
jestliže je pro P, Q ∈ E definováno P + Q, pak platí
fp(P + Q) = fp(P) + fp(Q).
Lenstrova metoda eliptických křivek
Představme si, že známe nějaký bod P = [α, β, 1] ∈ E a že |Ep| je
B-hladké pro nějaké nepříliš velké přirozené číslo B.
Označme LB nejmenší společný násobek čísel 1, 2, . . . , B.
Pak ovšem |Ep| | LB a platí tedy LB · fp(P) = Op.
Předpokládejme, že je definováno LB · P (přitom si při provádění
algoritmu budeme přát samozřejmě opak).
Pak musí pro LB · P = [α , β , γ ] platit p | α , p | β − 1, p | γ .
Protože naše vzorce pro sčítání bodů ve třetí složce dávají vždy 0
nebo 1, musí platit LB · P = O. To ale znamená, že
LB · fq(P) = Oq pro každé prvočíslo q | N.
Přitom budeme LB · P počítat postupně „donásobováním
jednotlivými prvočísly z rozkladu LB, a tedy každý mezivýsledek
musí mít ve třetí složce buď 0 nebo 1.
Protože donásobování prvočísly dělícími LB provádíme podle
velikosti od nejmenších k největším, pokud je LB · P definováno,
musí být největší prvočíslo dělící řád rq bodu fq(P) v grupě (Eq, +)
pro všechna prvočísla q|N stejné.
To je ale značně nepravděpodobné.
Lenstrova metoda eliptických křivek - volba parametrů
Proto lze čekat, že pokud pro zvolené nepříliš velké přirozené číslo
B platí, že |Ep| je B-hladké pro nějaké prvočíslo p dělící N,
s velkou pravděpodobností najdeme zmíněným postupem
netriviálního dělitele čísla N.
Problémem zůstává, že pro zvolené číslo B nemusí |Ep| být
B-hladké pro žádné prvočíslo p dělící N, což objevíme až poté, co
spočítáme LB · P. V tomto případě zvolíme jiná a, b a celý postup
znovu zopakujeme.
Zbývá vyjasnit několik věcí: jak volit a, b, jak najít P ∈ E a jak
zvolit přirozené číslo B.
Nelze zvolit a, b náhodně a bod P najít jako nějaké řešení
kongruence y2 ≡ x3 + ax + b (mod N), tj. pro zvolené x nalézt y.
Protože N není prvočíslo, řešit kvadratickou kongruenci modulo N
je příliš obtížné (ze znalosti všech řešení takové kongruence
bychom snadno spočítali netriviálního dělitele čísla N).
Proto zvolíme jiný postup: položíme b = 1, P = [0, 1, 1] a volíme
pouze a. Jistě potom P ∈ E.
Lenstrova metoda eliptických křivek - volba parametrů
Otázkou zůstává jak volit B. Protože pro menší p je také menší
|Ep|, vzhledem k tomu, že menší čísla jsou s větší pravděpodobností
B-hladká než velká, je metoda citlivá spíše na velikost p než na
velikost N. Proto je nutno zvolit B tak velké, jak velká prvočísla
jsme ještě ochotni hledat (nebo lépe, kolik času jsme ochotni
hledání věnovat). Analýza pomocí odhadu pravděpodobnosti toho,
že číslo jisté velikosti je B-hladké, ukazuje, že pro hledání prvočísel
do velikosti v je vhodné volit B tak, aby ln B
.
= 1
2 ln v ln ln v.
Speciálně tedy, pro hledání prvočísel menších než 1020 je vhodnou
hodnotou B = 12 000 (přičemž očekáváme, že bude potřeba projít
zhruba 12 000 eliptických křivek, než najdeme p).
Podobně jako u Pollardovy p − 1 metody je vhodné i zde doplnit
druhé stadium spočívající v tom, že předpokládáme, že |Ep| je
B1-hladký násobek prvočísla menšího než B2. Toto druhé stadium
je zcela analogické jako u Pollardovy metody, proto si uvedeme
algoritmus jen pro první stadium.
Algoritmus (Lenstrova metoda el. křivek, 1. stadium). Dáno
složené N nesoudělné s 6 a hranice B, hledáme netriviálního
dělitele N. Máme tabulku p[1], p[2], . . . , p[k] všech prvočísel ≤ B.
1. [Inicializace] Polož a ← 0.
2. [Inicializace křivky] Označme (E, O) křivku danou rovnicí
y2z = x3 + axz2 + z3, kde O = [0, 1, 0]. Polož P = [0, 1, 1],
i ← 0.
3. [Další prvočíslo] Polož i ← i + 1. Je-li i > k, polož a ← a + 1 a
jdi na 2. Jinak polož q ← p[i], r ← q, ← [B
q ], R ← P.
4. [Násob bod na křivce] Dokud r ≤ , opakuj r ← q · r. Pak zkus
spočítat P ← r · P na křivce (E, O). Pokud se to nepodařilo (tj.
v průběhu výpočtu byl objeven nenulový prvek okruhu ZN, který
není invertibilní), vytiskni získaného netriviálního dělitele N a
skonči. Jinak (tj. P byl vypočten), je-li P = O, jdi na 3.
5. [Počítej znovu] Dokud nebude R = O, opakovaně zkoušej
spočítat R ← q · R (pokud se to nepodaří, vytiskni získaného
netriviálního dělitele N a skonči). Nakonec polož a ← a + 1 a
jdi na 2.
Dobré aproximace reálných čísel
Definice. Pro libovolné reálné číslo α nechť α značí necelou část
čísla α, to znamená α − α ∈ Z a 0 ≤ α < 1.
Pro celou část [α] reálného čísla α tedy platí [α] = α − α .
Definice. Pro libovolné reálné číslo α nechť α je vzdálenost α od
nejbližšího celého čísla, tj.
α = min{|α − n|; n ∈ Z}.
Definice. Nechť θ ∈ R, p ∈ Z, q ∈ N, přičemž (p, q) = 1.
Racionální číslo p
q se nazývá dobrá aproximace čísla θ, jestliže
qθ = |qθ − p| a pro všechna q ∈ N, q < q platí q θ > qθ .
Příklad. Platí π
.
= 0.141593, 2π
.
= 0.283185,
3π
.
= 0.424778, 4π
.
= 0.433629, 5π
.
= 0.292037,
6π
.
= 0.150444, 7π
.
= 0.008851, 8π
.
= 0.132741,
9π
.
= 0.274334. Proto jsou 3 a 22
7 dobré aproximace čísla π.
Další dobrá aproximace 333
106 pochází z 106π
.
= 0.008821.
Věta 1. Nechť θ ∈ R, Q ∈ R, Q > 1. Pak existuje q ∈ N, q < Q
s vlastností qθ ≤ 1
Q . Jestliže navíc θ /∈ Q anebo Q /∈ N, existuje
q ∈ N tak, že q < Q, qθ < 1
Q .
Důkaz. Nejprve budeme předpokládat Q ∈ N. Uvažme Q + 1 čísel
0, 1, θ , 2θ , . . . , (Q − 1)θ a rozdělme je do Q intervalů
[0, 1
Q ), [ 1
Q , 2
Q ), . . . , [Q−1
Q , 1]. Z Dirichletova principu plyne, že
alespoň jeden interval obsahuje aspoň dvě čísla, tedy existují
r1, r2, s1, s2 ∈ Z taková, že 0 ≤ r1 < r2 < Q s vlastností
|(r1θ − s1) − (r2θ − s2)| ≤ 1
Q . Položme q = r2 − r1, pak qθ ≤ 1
Q .
Jestliže Q /∈ N, plyne věta z platnosti věty pro [Q] + 1.
Poznámka. Ukážeme si, že z předchozí věty plyne, že pro libovolné
θ ∈ R − Q existuje nekonečně mnoho q ∈ N splňujících
q · qθ < 1. (1)
Ve skutečnosti je možné dokonce dokázat více: číslo 1 na pravé
straně může být nahrazeno číslem 1√
5
. Toto silnější tvrzení však
nebudeme dokazovat.
Konstrukce posloupnosti dobrých aproximací čísla θ
Zvolme pevně θ ∈ R − Q. Sestrojme indukcí posloupnost všech
dobrých aproximací čísla θ. Jistě q1 = 1 dává dobrou aproximaci p1
q1
čísla θ spolu s nějakým p1 ∈ Z a platí |q1θ − p1| = θ < 1
2.
Protože 2θ /∈ Z, je touto rovností p1 určeno jednoznačně. Zřejmě
(q1, p1) = 1.
Předpokládejme, že pro nějaké n ∈ N máme dobrou aproximaci pn
qn
čísla θ. Protože θ /∈ Q, je qnθ = 0 a věta 1 s Q = qnθ −1
zaručuje existenci q ∈ N, které splňuje qθ < qnθ . Nechť qn+1
je nejmenší q s touto vlastností a pn+1 ∈ Z je určeno podmínkou
qn+1θ = |qn+1θ − pn+1|. Je tedy qn+1θ < qnθ a pro
všechna pro všechna q ∈ N, q < qn+1 platí qθ ≥ qnθ ; je tedy
pn+1
qn+1
dobrá aproximace čísla θ. Protože pn
qn
je také dobrá aproximace
čísla θ, platí qn+1 > qn. Kdyby t = (qn+1, pn+1) > 1, pak by
p = pn+1
t ∈ Z, q = qn+1
t ∈ N, q < qn+1, přitom
qn+1θ = |qn+1θ − pn+1| = t|q θ − p | ≥ t q θ > q θ ,
což by byl spor s definicí qn+1. Je tedy (qn+1, pn+1) = 1.
Vlastnosti posloupnosti dobrých aproximací čísla θ
Dostali jsme posloupnost přirozených čísel
1 = q1 < q2 < q3 < . . . (2)
a celých čísel p1, p2, p3, . . . splňujících (pn, qn) = 1 a
qnθ = |qnθ − pn|, (3)
qn+1θ < qnθ , (4)
qθ ≥ qnθ pro všechna q ∈ N, q < qn+1. (5)
Z věty 1 pro Q = qn+1 dostaneme existenci q ∈ N, q < qn+1,
takového, že qθ ≤ 1
qn+1
. Podle (5) platí
qn qnθ < qn+1 qnθ ≤ 1. (6)
Kdyby čísla qn+1θ − pn+1 a qnθ − pn měla stejná znaménka, pro
p = pn+1 − pn, 0 < q = qn+1 − qn < qn+1, bychom dostali
|q θ − p | < |qnθ − pn| = qnθ , což by byl spor s (5). Proto
(qnθ − pn)(qn+1θ − pn+1) < 0. (7)
Lemma 1. {pn
qn
; n ∈ N} je množina všech dobrých aproximací a
platí limn→∞
pn
qn
= θ.
Důkaz. První část plyne z konstrukce, druhá z (6), neboť
|θ − pn
qn
| < 1
q2
n
.
Lemma 2. qn+1pn − qnpn+1 = ±1.
Důkaz. Levá strana je celé číslo a platí
qn+1pn − qnpn+1 = qn(qn+1θ − pn+1) − qn+1(qnθ − pn), (8)
odkud spolu s (3), (4), (6) a (7) plyne
0 < qn qn+1θ +qn+1 qnθ = |qn+1pn−qnpn+1| < 2qn+1 qnθ ≤ 2.
Důsledek. Číslo qn+1pn − qnpn+1 má opačné znaménko než
qnθ − pn a platí qn+1pn − qnpn+1 = −(qnpn−1 − qn−1pn).
Důkaz. Plyne z (8) s přihlédnutím k (3), (4) a qn+1 > qn, druhá
část z (7) a lemmatu 2.
Lemma 3. Pro libovolné n ≥ 2 existuje an ∈ N tak, že
qn+1 = anqn + qn−1, (9)
pn+1 = anpn + pn−1, (10)
|qn−1θ − pn−1| = an|qnθ − pn| + |qn+1θ − pn+1|. (11)
Důkaz. Z důsledku dostáváme pn(qn+1 − qn−1) = qn(pn+1 − pn−1).
Protože (qn, pn) = 1, plyne odtud existence celého čísla an
s vlastností qn+1 − qn−1 = anqn, pn+1 − pn−1 = anpn. Protože
qn+1 > qn−1, je an > 0. Konečně, (11) plyne z (9) a (10) díky (7).
Poznámka. Z (11) pro každé n ≥ 2 plyne
an = |qn−1θ−pn−1|
|qnθ−pn| = qn−1θ
qnθ . (12)
Známe-li tedy p1, p2, q1, q2 a θ, můžeme pomocí (12), (9) a (10)
dopočítat všechny dobré aproximace iracionálního čísla θ.
Pro θ ∈ Q, 2θ /∈ Z, probíhá celý proces stejně až do okamžiku, kdy
qnθ = 0, tj. pn
qn
= θ, kdy se proces konstrukce dobrých
aproximací zastaví. Pro θ ∈ Q − 1
2Z tedy dostáváme konečně
mnoho dobrých aproximací, z nichž poslední je rovna θ.
Věta. Nechť θ ∈ R, 2θ /∈ Z. Generujme rekurentně celá čísla pn,
qn, an; nejprve položme
p0 = 1, q0 = 0,
p1 = [θ], q1 = 1.
Pro každé n ∈ N takové, že qnθ = pn, pokračujme
an = |qn−1θ−pn−1|
|qnθ−pn|
pn+1 = anpn + pn−1,
qn+1 = anqn + qn−1.
Pak všechny dobré aproximace čísla θ jsou právě získaná čísla pn
qn
pro n ≥ 1, je-li a1 > 1, resp. pro n ≥ 2, je-li a1 = 1. Navíc platí
(−1)n
(qnθ − pn) ≤ 0, (13)
qn+1pn − qnpn+1 = (−1)n
. (14)
Ve studijním textu je uveden důkaz této věty i její použití pro
důkaz Lehmannovy věty.