Proč je dobré míti...... prvočísla?
Michal Bulant
Brkomoni 2016, Zdobnice v Orlických horách
29.8. - 4.9.2016
Michal Bulant (Brkos 2016)
Motivace
Plán přednášky
O Mot
ivace
o Co je to vlastně prvočíslo? o Eulerova funkce cp
o Fermatova a Eulerova věta
■v
o Čínská zbytková věta
9 Teoretické základy
o Klasické testy s využitím kongruencí
Michal Bulant (Brkos 2016)
Proč je dobré mít i prvočísla 29.8. - 4.9.2016       2 / 52
Motivace
Zašifrovaná motivace
Zachytili jsme tajnou zprávu
C = 239675027941280548756812205343466895417790207923642 pro našeho nepřítele A, kterou bychom rádi dešifrovali.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
4 š ► < i ►     -š ^O^O 29.8. - 4.9.2016       3 / 52
Motivace
Zašifrovaná motivace
wgm
Zachytili jsme tajnou zprávu
C = 239675027941280548756812205343466895417790207923642
pro našeho nepřítele A, kterou bychom rádi dešifrovali. Jako každý jiný účastník víme, že A komunikuje prostřednictvím RSA a že veřejný klíč Va je tvořen čísly
n = 374144419156711146897884040346152783797331507019777
a
e = 240911337096020749615795248242245864391942105373709.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       3 / 52
Motivace
Zašifrovaná motivace
Zachytili jsme tajnou zprávu
C = 239675027941280548756812205343466895417790207923642
pro našeho nepřítele A, kterou bychom rádi dešifrovali. Jako každý jiný účastník víme, že A komunikuje prostřednictvím RSA a že veřejný klíč Va je tvořen čísly
n = 374144419156711146897884040346152783797331507019777
e = 240911337096020749615795248242245864391942105373709.
Jsme schopni s těmito údaji zprávu dešifrovat?
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       3 / 52
Motivace
Zašifrovaná motivace - RSA
Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) 9 každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý Sa
Michal Bulant (Brkos 2016)
Motivace
Zašifrovaná motivace - RSA
Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973)
9 každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a
o generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, (p(n) = (p — l)(q — 1) [n je veřejné, ale (p(n) nelze snadno spočítat ]
Michal Bulant (Brkos 2016)
Motivace
Zašifrovaná motivace - RSA
Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973)
9 každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a
o generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, (p(n) = (p — l)(q — 1) [n je veřejné, ale (p(n) nelze snadno spočítat ]
o zvolí veřejný klíč e a ověří, že (e, <p(n)) = 1
Michal Bulant (Brkos 2016)
Motivace
Zašifrovaná motivace - RSA
Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973)
9 každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a
o generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, (p(n) = (p — l)(q — 1) [n je veřejné, ale (p(n) nelze snadno spočítat ]
o zvolí veřejný klíč e a ověří, že (e, <p(n)) = 1
a např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e - d = 1 (mod ^(r?))
Michal Bulant (Brkos 2016)
Motivace
Zašifrovaná motivace - RSA
Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973)
9 každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a
o generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, (p(n) = (p — l)(q — 1) [n je veřejné, ale (p(n) nelze snadno spočítat ]
o zvolí veřejný klíč e a ověří, že (e, <p(n)) = 1
a např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod ^(r?))
a zašifrování numerického kódu zprávy M:
C = Ce{M) = Me   (mod n)
Michal Bulant (Brkos 2016)
Motivace
Zašifrovaná motivace - RSA
Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973)
9 každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a
o generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, (p(n) = (p — l)(q — 1) [n je veřejné, ale (p(n) nelze snadno spočítat ]
a zvolí veřejný klíč e a ověří, že (e, <p(n)) = 1
a např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod ^>(r?))
a zašifrování numerického kódu zprávy M:
C = Ce{M) = Me   (mod n) o dešifrování šifry C: 07" = Dd(C) = Cd (mod n)
Michal Bulant (Brkos 2016)
Proč je dobré mít i prvočísla 29.8. - 4.9.2016       4 / 52
Něco málo o prvočíslech
Plán přednášky
Q Něco málo o prvočíslech o Co je to vlastně prvočíslo? e Eulerova funkce cp
o Fermatova a Eulerova věta
■v
o Čínská zbytková věta
9 Teoretické základy
o Klasické testy s využitím kongruencí
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       5 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Prvočíslo
Definice
Přirozené číslo, které má právě 2 kladné dělitele, se nazývá prvočíslo
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       6 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Prvočíslo
Definice
Přirozené číslo, které má právě 2 kladné dělitele, se nazývá prvočíslo
Definice (alternativní)
Přirozené číslo n je prvočíslo, právě když pro libovolná a, b G Z platí
n
ab => n  a nebo n b.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       6 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Prvočíslo
Definice			
Přirozené číslo, které má právě 2 kladné dělitele, se nazývá prvočíslo.			
			
Definice (alternativní)	i		
Přirozené číslo n je prvoč n	slo, právě kc ab => n	Jyž pro libc a nebo n	>volná a, b G Z platí *•
Je vidět, že obě definice popisují totéž?
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       6 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Prvočíslo
Definice
Přirozené číslo, které má právě 2 kladné dělitele, se nazývá prvočíslo
Definice (alternativní)
Přirozené číslo n je prvočíslo, právě když pro libovolná a, b G Z platí
n
ab => n  a nebo n b.
Je vidět, že obě definice popisují totéž?
Věta (Základní věta aritmetiky)
Každé přirozené číslo se dá jednoznačně (až na pořadí) zapsat jako součin prvočísel.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       6 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Prvočíslo
Definice
Přirozené číslo, které má právě 2 kladné dělitele, se nazývá prvočíslo
Definice (alternativní)
Přirozené číslo n je prvočíslo, právě když pro libovolná a, b G Z platí
n
ab => n  a nebo n b.
Je vidět, že obě definice popisují totéž?
Věta (Základní věta aritmetiky)
Každé přirozené číslo se dá jednoznačně (až na pořadí) zapsat jako součin prvočísel.
Tuto zásadní větu uvádíme nyní, ale dokážeme později, až k to budeme mít prostředky!
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       6 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Předchozí tvrzení nejsou úplně zadarmo, navíc se ukazuje, že zdaleka neplatí při přirozeném rozšíření těchto definic do jiných číselných oborů kde umíme rozumným způsobem sčítat, násobit a krátit (tzv. obory integrity - např. Q, IR, Z[V2], Z[/], Z[^/^5] apod.)-
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Předchozí tvrzení nejsou úplně zadarmo, navíc se ukazuje, že zdaleka neplatí při přirozeném rozšíření těchto definic do jiných číselných oborů, kde umíme rozumným způsobem sčítat, násobit a krátit (tzv. obory integrity - např. Q, IR, Z[V2], Z[/], Z[^/^5] apod.).
Příklad
6 = 2 • 3 = (1 + V^Xl - V^Š)
Přitom zde selhává i zaměnitelnost obou definic prvočíselnosti, být nerozložitelný (ireducibilní) je obecně slabší vlastnost než být primitivní (alternativní definice) - v tomto příkladu je 2 nerozložitelná, ale přitom 2 | (1 +     5)(1 — y/—5), i když nedělí žádného z činitelů.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       7 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Předchozí tvrzení nejsou úplně zadarmo, navíc se ukazuje, že zdaleka neplatí při přirozeném rozšíření těchto definic do jiných číselných oborů, kde umíme rozumným způsobem sčítat, násobit a krátit (tzv. obory integrity - např. Q, IR, Z[V2], Z[/], Z[^/^5] apod.).
Příklad
6 = 2 • 3 = (1 + V^Xl - V^Š)
Přitom zde selhává i zaměnitelnost obou definic prvočíselnosti, být nerozložitelný (ireducibilní) je obecně slabší vlastnost než být primitivní (alternativní definice) - v tomto příkladu je 2 nerozložitelná, ale přitom 2 | (1 +     5)(1 — y/—5), i když nedělí žádného z činitelů.
V Z[/] žádné takové potíže nenastávají, zde je rozklad na prvočísla jednoznačný: 6 = — / • (1 + i)2 • 3.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       7 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
S pomocí programu SAGE, který budeme využívat, lze spočítat např. všechna prvočísla nebo všechna složená čísla v zadaném intervalu:
sage:   prime.range(10,50) 1
[11,   13,   17,   19,   23,   29,   31,   37,   41,   43,   47] 2
sage:   [n for n  in range(10,30)   if  not   is.prime(n 3 )]
[10,   12,   14,   15,   16,   18,   20,   21,   22,   24,   25,   26, 4 27, 28]
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       8 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Největší společný dělitel
To, že v případě celých čísel prvočísla splňují i alternativní definici, lze snadno dokázat pomocí pojmu největší společný dělitel.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Největší společný dělitel
To, že v případě celých čísel prvočísla splňují i alternativní definici, lze snadno dokázat pomocí pojmu největší společný dělitel.
Definice
Mějme celá čísla a, b. Libovolné celé číslo m takové, že m | a, m \ b se nazývá společný dělitel čísel a, b. Společný dělitel m > 0 čísel a, b, který je dělitelný libovolným společným dělitelem čísel a, b, se nazývá největší společný dělitel čísel a, b a značí se (a, b).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       9 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Největší společný dělitel
To, že v případě celých čísel prvočísla splňují i alternativní definici, lze snadno dokázat pomocí pojmu největší společný dělitel.
Definice
Mějme celá čísla a, b. Libovolné celé číslo m takové, že m | a, m \ b se nazývá společný dělitel čísel a, b. Společný dělitel m > 0 čísel a, b, který je dělitelný libovolným společným dělitelem čísel a, b, se nazývá největší společný dělitel čísel a, b a značí se (a, b). Analogicky se definuje nejmenší společný násobek [a, b].
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       9 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Největšího společného dělitele lze u malých čísel vyčíst z obrázku - viz http://wiki.sagemath.org/interact/number_theory.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       10 / 52
Něco málo o prvočíslech
Jak spočítat GCD?
Co je to vlastně prvočíslo?
Největšího společného dělitele lze jistě spočítat z rozkladu pokud tedy umíme daná čísla rozložit.
sage :   gcd(97  *   10~15 ,   19~20  * 97~2) 97
Ale co v případě, že chceme spočítat něco takového?
gcd(353684060262049920641282849809,\ 97000000000000000)
Michal Bulant (Brkos 2016)
4 □ ►   < [51 ►
Proč je dobré míti prvočísla
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Euklidův algoritmus
Ukazuje, že spočítat největšího společného dělitele je výpočetně daleko snazší než rozkládat čísla na prvočísla. Euklidův algoritmus je založen na větě o dělení se zbytkem (a v ní je rovněž skryt rozdíl např. mezi Z[/] a Zh/=5]).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       12 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Euklidův algoritmus
Ukazuje, že spočítat největšího společného dělitele je výpočetně daleko snazší než rozkládat čísla na prvočísla. Euklidův algoritmus je založen na větě o dělení se zbytkem (a v ní je rovněž skryt rozdíl např. mezi Z[/] a Zh/=5]).
Pro libovolně zvolená čísla a £ Z, m £ N existují jednoznačně určená čísla q £ Z, r £ {0,1,..., m — 1} tak, že a — qm + r.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       12 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Euklidův algoritmus
Ukazuje, že spočítat největšího společného dělitele je výpočetně daleko snazší než rozkládat čísla na prvočísla. Euklidův algoritmus je založen na větě o dělení se zbytkem (a v ní je rovněž skryt rozdíl např. mezi Z[i] a Zh/=5]).
Pro libovolně zvolená čísla a £ Z, m £ N existují jednoznačně určená čísla q £ Z, r £ {0,1,..., m — 1} tak, že a — qm + r.
Věta (Euklidův algoritmus)
Nechť ai, a^ jsou přirozená čísla. Pro každé n > 3, pro které an-\ ^ 0, označme an zbytek po dělení čísla an-2 číslem an-\. Pak po konečném počtu kroků dostaneme a k = 0 a platía/c-i — (ai, a?).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       12 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Z Euklidova algoritmu vyplývá jedno z nejužitečnějších tvrzení v elementární teorii čísel - tzv. Bezoutova věta.
Věta (Bezoutova)
Pro libovolná celá čísla a, b existuje jejich největší společný dělitel (a, b), pritom existují celá čísla k J tak, že (a, b) = ka + Ib.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       13 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Z Euklidova algoritmu vyplývá jedno z nejužitečnějších tvrzení v elementární teorii čísel - tzv. Bezoutova věta.
Věta (Bezoutova)
Pro libovolná celá čísla a, b existuje jejich největší společný dělitel (a, b), pritom existují celá čísla k J tak, že (a, b) = ka + Ib.
Příklad
O Rozhodněte, jestli je možné pomocí mincí o nominální hodnotě 5 a 7 Kč zaplatit (s vracením) jakoukoliv částku.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       13 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Z Euklidova algoritmu vyplývá jedno z nejužitečnějších tvrzení v elementární teorii čísel - tzv. Bezoutova věta.
Věta (Bezoutova)
Pro libovolná celá čísla a, b existuje jejich největší společný dělitel (a, b), pritom existují celá čísla k J tak, že (a, b) = ka + Ib.
Příklad
O Rozhodněte, jestli je možné pomocí mincí o nominální hodnotě 5 a 7 Kč zaplatit (s vracením) jakoukoliv částku.
O Bruče Willis a Samuel Jackson mají ve filmu Smrtonosná past 3 za úkol zlikvidovat bombu pomocí 4 galonů vody, přičemž k dispozici mají pouze nádoby na 3, resp. 5 galonů.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       13 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Z Euklidova algoritmu vyplývá jedno z nejužitečnějších tvrzení v elementární teorii čísel - tzv. Bezoutova věta.
Věta (Bezoutova)
Pro libovolná celá čísla a, b existuje jejich největší společný dělitel (a, b), pritom existují celá čísla k J tak, že (a, b) = ka + Ib.
Příklad
O Rozhodněte, jestli je možné pomocí mincí o nominální hodnotě 5 a 7 Kč zaplatit (s vracením) jakoukoliv částku.
O Bruče Willis a Samuel Jackson mají ve filmu Smrtonosná past 3 za úkol zlikvidovat bombu pomocí 4 galonů vody, přičemž k dispozici mají pouze nádoby na 3, resp. 5 galonů.
O Mezi největším společným dělitelem a nejmenším společným násobkem celých čísel a, b platí vztah |a • b\ — (a, b) • [a, b\.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       13 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Důležité důsledky
Jsou-li a, b nesoudělná celá čísla a platí-li a  b • c, pak nutně a
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. -
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Důležité důsledky			
			
	Věta		i
Jsou-li a, b nesoudělná celá čísla a		platí-li a  b • c, pak nutně a c.	j
			
	Věta		
Pokud je p prvočíslo, pak splňuje i		alternativní definici prvočísel n ost i.	
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       15 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Důležité důsledky
Jsou-li a, b nesoudělná celá čísla a platí-li a  b - c, pak nutně a
Pokud je p prvočíslo, pak splňuje i alternativní definici prvočíselnosti.
j
]
Důkaz základní věty aritmetiky
Teprve nyní jsme schopni základní větu aritmetiky (alespoň v náznaku) dokázat.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       15 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Příklad
Dobrou vlastností Euklidova algoritmu (i jeho rozšírení, které zároveň najde koeficienty do Bezoutovy rovnosti) je to, zeje velmi efektivní. Zatímco rozkládat čtyřciferná čísla na prvočísla na papíre většině z nás zabere asi dost času, spočítat největšího společného dělitele dvou takových čísel je daleko snazší. A podobně je na tom i počítač (i když s čísly podstatně většími - o několika stovkách cifer).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       16 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Příklad
Dobrou vlastností Euklidova algoritmu (i jeho rozšírení, které zároveň najde koeficienty do Bezoutovy rovnosti) je to, zeje velmi efektivní. Zatímco rozkládat čtyřciferná čísla na prvočísla na papíře většině z nás zabere asi dost času, spočítat největšího společného dělitele dvou takových čísel je daleko snazší. A podobně je na tom i počítač (i když s čísly podstatně většími - o několika stovkách cifer).
sage:   gcd(10~2016+1,19~1000-1) 1
sage: xgcd(42,27) (3,   2, -3)
i:
L
1! II
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       16 / 52
Něco málo o prvočíslech
Co je to vlastně prvočíslo?
Příklad
Dobrou vlastností Euklidova algoritmu (i jeho rozšírení, které zároveň najde koeficienty do Bezoutovy rovnosti) je to, zeje velmi efektivní. Zatímco rozkládat čtyřciferná čísla na prvočísla na papíře většině z nás zabere asi dost času, spočítat největšího společného dělitele dvou takových čísel je daleko snazší. A podobně je na tom i počítač (i když s čísly podstatně většími - o několika stovkách cifer).
sage:   gcd(10~2016+1,19~1000-1) 1
sage: xgcd(42,27) (3,   2, -3)
1! 21
2: y
Pro další úvahy si všimněme, že Sage umí velmi rychle odpovědět na otázku, jestli je nějaké číslo prvočíslo, přitom jej ale často neumí rozložit (a dokonce nezná ani žádného dělitele).
sage:   is_prime (10~2016 +1) Z
Proč je dobré míti prvočísla 29.8. - 4.9.2016       16 / 52
Michal Bulant (Brkos 2016)
Něco málo o prvočíslech
Eulerova funkce 4>
Eulerova funkce (p
Definice		1
Nechť n € N. Definujme	Eulerovu funkci <p předpisem	
(p(n) =	\{a e N;0 < a < n, (a,n) = 1}|	
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       17 / 52
Něco málo o prvočíslech
Eulerova funkce 4>
Eulerova funkce (p
Definice		1
Nechť n € N. Definujme	Eulerovu funkci <p předpisem	
(p(n) =	|{a e N;0 < a < n, (a, n) = 1}|	
Necht r? G N, jehož rozklad je tvaru n — p*1 • • • p*k. Pak
„(n) = n • (l - 1)
1-
Pk
Michal Bulant (Brkos 2016)
<  □  ►    < [f? ►    <  -E  ►    <  -Ž  ►        Š       'O Q, O
Proč je dobré míti prvočísla 29.8. - 4.9.2016       17 / 52
Něco málo o prvočíslech
Eulerova funkce cf>
Důkaz.
O Pomocí principu inkluze a exkluze na základě zjištění počtu čísel soudělných snv určitém intervalu.
□
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       18 / 52
Něco málo o prvočíslech
Eulerova funkce cf>
O Pomocí principu inkluze a exkluze na základě zjištění počtu čísel soudělných snv určitém intervalu.
O Tvrzení lze odvodit i jiným způsobem na základě poznatku (r?, atí) = 1 <^> (r?, a) = 1 A (r?, b) = 1, spolu se snadno odvoditelným výsledkem
<p(Pa) = pa - p*-1 = (p -1) ■ p*-1.
□
9
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       18 / 52
Kongruence - užitečná zkratka
Plán přednášky
o Co je to vlastně prvočíslo? o Eulerova funkce cp
Q Kongruence - užitečná zkratka • Fermatova a Eulerova věta o Čínská zbytková věta
9 Teoretické základy
o Klasické testy s využitím kongruencí
Michal Bulant (Brkos 2016)
Proč je dobré mít i prvočísla 29.8. - 4.9.2016       19 / 52
Kongruence - užitečná zkratka
Kongruence
Pojem kongruence byl zaveden Gaussem. Ačkoliv je to pojem velice jednoduchý, jeho důležitost a užitečnost v teorii čísel je nedocenitelná; projevuje se zejména ve stručných a přehledných zápisech některých i velmi komplikovaných úvah.
Definice
Jestliže dvě celá čísla a, b mají při dělení přirozeným číslem m týž zbytek r, kde 0 < r < m, nazývají se a, b kongruentnímodulo m, tj. a = b (mod m).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016
20 / 52
Kongruence - užitečná zkratka
Kongruence
Pojem kongruence byl zaveden Gaussem. Ačkoliv je to pojem velice jednoduchý, jeho důležitost a užitečnost v teorii čísel je nedocenitelná; projevuje se zejména ve stručných a přehledných zápisech některých i velmi komplikovaných úvah.
Definice
Jestliže dvě celá čísla a, b mají při dělení přirozeným číslem m týž zbytek r, kde 0 < r < m, nazývají se a, b kongruentnímodulo m, tj. a = b (mod m).
Lemma
Pro libovolná a, b G Z, m G N jsou následující podmínky ekvivalentní O 3 = b (mod m), Q a = b + mt   pro vhodné t G Q m  a — b.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       20 / 52
Kongruence - užitečná zkratka
Vlastnosti kongruencí
Vlastnosti
O Kongruence podle téhož modulu můžeme sčítat a násobit.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016
21 / 52
Kongruence - užitečná zkratka
Vlastnosti kongruencí
Vlastnosti
O Kongruence podle téhož modulu můžeme sčítat a násobit.
Q K libovolné straně kongruence můžeme přičíst jakýkoliv násobek modulu.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
<<□►  < [5 ►  < š ►  < -ž ►
29.8. - 4.9.2016
21 / 52
Vlastnosti kongruencí
O Kongruence podle téhož modulu můžeme sčítat a násobit.
Q K libovolné straně kongruence můžeme přičíst jakýkoliv násobek modulu.
O Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem.
Proč je dobré míti prvočísla
29.8. - 4.9.2016
21 / 52
Vlastnosti kongruencí
O Kongruence podle téhož modulu můžeme sčítat a násobit.
O K libovolné straně kongruence můžeme přičíst jakýkoliv násobek modulu.
O Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem.
O Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem.
Proč je dobré míti prvočísla
29.8. - 4.9.2016
21 / 52
Kongruence - užitečná zkratka
Vlastnosti kongruencí
Vlastnosti
O Kongruence podle téhož modulu můžeme sčítat a násobit.
O K libovolné straně kongruence můžeme přičíst jakýkoliv násobek modulu.
O Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem.
O Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem.
O Jestliže kongruence a = b platí podle různých modulů mi,..., m^, platí i podle modulu, kterým je nejmenší společný násobek [mi,..., rrik] těchto čísel.
Michal Bulant (Brkos 2016)
Proč je dobré mít i prvočísla 29.8. - 4.9.2016       21 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Některé důležité věty
Věta (Fermatova)
Je-li a nedělitelné prvočíslem p, pak p  ap   — 1, tj
ap~x = 1   (mod p).
Michal Bulant (Brkos 2016)
Proč je dobré mít i prvočísla 29.8. - 4.9.2016       22 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Některé důležité věty
Věta (Fermatova)	
Je-li a nedělitelné prvočíslem p, pak p ap~x = 1	aP'1 - 1, tj. [mod p).
Důkaz.
Lze dokázat poměrně snadno například matematickou indukcí (pro přirozená a, na celá se již rozšíří snadno) ekvivalentní tvrzení p | ap — a.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       22 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Některé důležité věty
Věta (Fermatova)	
Je-li a nedělitelné prvočíslem p, pak p ap~x = 1	aP'1 - 1, tj. [mod p).
Důkaz.
Lze dokázat poměrně snadno například matematickou indukcí (pro přirozená a, na celá se již rozšíří snadno) ekvivalentní tvrzení p | ap — a. Další možností je kombinatorický důkaz, kdy počet možných náhrdelníků o p špercích vybíraných z a druhů vyjde
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       22 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Některé důležité věty
Věta (Fermatova)	
Je-li a nedělitelné prvočíslem p, pak p ap~x = 1	aP'1 - 1, tj. [mod p).
Důkaz.
Lze dokázat poměrně snadno například matematickou indukcí (pro přirozená a, na celá se již rozšíří snadno) ekvivalentní tvrzení p | ap — a. Další možností je kombinatorický důkaz, kdy počet možných náhrdelníků o p špercích vybíraných z a druhů vyjde
.p _
+ a.
□
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       22 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Příklad (IMO 2005)
Uvažte posloupnost 3i,a2,... definovanou předpisem an = 2n + 3n + 6n-l   n = l,2,....
Určete všechna přirozená čísla, která jsou nesoudělná se všemi členy této posloupnosti.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       23 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Příklad (IMO 2005)
Uvažte posloupnost 3i,a2,... definovanou předpisem an = 2n + 3n + 6n-l   n = l,2,....
Určete všechna přirozená čísla, která jsou nesoudělná se všemi členy této posloupnosti.
Řešení			
Z Fermatovy věty vyplyne, že pro p > 3 platí p proto nevyhovuje jiné číslo než 1.	3P_2- Dále 2	3l,3	32.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       23 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Některé důležité věty II.
Věta (Eulerova)
Je-li a G 1j, m € N a (a, m) = 1, pak
a^m) = 1   (mod m).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       24 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Některé důležité věty II.
Věta (Eulerova)
Je-li a G Z, m € N a (a, m) = 1, pak
a^m) = 1   (mod m).
Věta (Wilsonova)
Přirozené číslo n je prvočíslo, právě když
(n- 1)! = -1   (mod n)
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       24 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Příklad
Pro každé n G N určete
(n! + l,(n + l)!).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       25 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Příklad
Pro každé n G N určete
(n! + l,(n + l)!).
Řešení
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       25 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Řešení lineárních kongruencí
Jak za chvíli uvidíme, důležité pro nás bude umět „dělit číslo b číslem modulo m", přesněji řešit kongruence tvaru
ax = b   (mod m)
se zadanými celými a, b, m £ N a neznámými celými x.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Řešení lineárních kongruencí
Jak za chvíli uvidíme, důležité pro nás bude umět „dělit číslo b číslem a modulo m", přesněji řešit kongruence tvaru
ax = b   (mod m)
se zadanými celými a, b, m £ N a neznámými celými x.
Výše uvedená kongruence s neznámou x má řešení, právě když (a, m) \ b. J
Poznámka
Nejdůležitejším případem je situace, kdy b — 1; v takovém případě lze řešení (jediné modulo m) nalézt pomocí Euklidova algoritmu a Bezoutovy věty.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       26 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
K motivačnímu příkladu - RSA
Připomeňme, že při inicializaci protokolu RSA si každý účastník volí veřejný klíč e a k němu dopočítává soukromý d tak, aby e • d = 1 (mod <p(n)).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       27 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
K motivačnímu příkladu - RSA
Připomeňme, že při inicializaci protokolu RSA si každý účastník volí veřejný klíč e a k němu dopočítává soukromý d tak, aby e • d = 1 (mod <p(n)). Z předchozího víme, že při znalosti e a <p(n) je zjištění d velmi jednoduché. Z postupu na dešifrování je vidět, že znalost d nám umožní přečíst libovolnou zprávu určenou jen uživateli s tímto soukromým klíčem.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       27 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
K motivačnímu příkladu - RSA
Připomeňme, že při inicializaci protokolu RSA si každý účastník volí veřejný klíč e a k němu dopočítává soukromý d tak, aby e • d = 1 (mod <p(n)). Z předchozího víme, že při znalosti e a <p(n) je zjištění d velmi jednoduché. Z postupu na dešifrování je vidět, že znalost d nám umožní přečíst libovolnou zprávu určenou jen uživateli s tímto soukromým klíčem. Bezpečnost RSA tedy závisí na tom, že nejsme schopni spočítat <p(n) ani při znalosti n, tedy rozložit n na prvočísla.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016
27 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Modulární výpočty
Zásadní pro praktické používání RSA (ale i dalších protokolů) je to, že jsme schopni velmi efektivně počítat „modulo m". Nejméně intuitivní (a přitom velmi podstatný) je fakt, že umíme velmi efektivně umocňovat modulo m, a to i na velmi vysoký exponent (uvědomme si, jak se zašifrovává a dešifrovává v RSA).
Michal Bulant (Brkos 2016)
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Modulární výpočty
Zásadní pro praktické používání RSA (ale i dalších protokolů) je to, že jsme schopni velmi efektivně počítat „modulo m". Nejméně intuitivní (a přitom velmi podstatný) je fakt, že umíme velmi efektivně umocňovat modulo m, a to i na velmi vysoký exponent (uvědomme si, jak se zašifrovává a dešifrovává v RSA).
Efektivita algoritmu umocňování je založena na tom, že se výsledná mocnina počítá postupně a kdykoliv je to možné, redukuje se výsledek modulo m.
Michal Bulant (Brkos 2016)
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Modulární výpočty
Zásadní pro praktické používání RSA (ale i dalších protokolů) je to, že jsme schopni velmi efektivně počítat „modulo m". Nejméně intuitivní (a přitom velmi podstatný) je fakt, že umíme velmi efektivně umocňovat modulo m, a to i na velmi vysoký exponent (uvědomme si, jak se zašifrovává a dešifrovává v RSA).
Efektivita algoritmu umocňování je založena na tom, že se výsledná mocnina počítá postupně a kdykoliv je to možné, redukuje se výsledek modulo m.
Stejně důležité (a asi ještě méně zřejmé) je to, že na rozdíl od modulárního umocňování je modulární logaritmování velmi časově náročné. Spousta praktických protokolů je založena na tom, že ani se znalostí g, b, m £ Z neumíme snadno určit pro které celé a platí
ga — b   (mod m).
Michal Bulant (Brkos 2016)
Proč je dobré mít i prvočísla 29.8. - 4.9.2016       28 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Příklad
Vypočtěme dvě poslední cifry dekadického zápisu čísla 7 tak, že určíme 791 (mod 100).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       29 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Příklad
Vypočtěme dvě poslední cifry dekadického zápisu čísla 7 tak, že určíme 791 (mod 100).
Protože (7,100) = 1, dostáváme z Eulerovy věty, že 7^100) = 740 = 1 (mod 100), odkud 791 = 740 • 740 • 711 (mod 100). Zbývá tedy určit 711 (mod 100).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       29 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Příklad
Vypočtěme dvě poslední cifry dekadického zápisu čísla 7 tak, že určíme 791 (mod 100).
Protože (7,100) = 1, dostáváme z Eulerovy věty, že 7^100) = 740 = 1 (mod 100), odkud 791 = 740 • 740 • 711 (mod 100). Zbývá tedy určit 711 (mod 100).
Zapišme exponent 11 ve dvojkové soustavě: 11 = (1011)2-Následně pro a = 7 určíme a2, a4, a8,... (mod 100) a spočítáme
a11 = aä • az • a = 1 • 49 • 7 = 43   (mod 100).
.8 _2__
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       29 / 52
Kongruence - užitečná zkratka
Fermatova a Eulerova věta
Příklad
Vypočtěme dvě poslední cifry dekadického zápisu čísla 791 tak, že určíme 791 (mod 100).
Protože (7,100) = 1, dostáváme z Eulerovy věty, že 7^100) = 740 = 1 (mod 100), odkud 791 = 740 - 740 - 711 (mod 100). Zbývá tedy určit 711 (mod 100).
Zapišme exponent 11 ve dvojkové soustavě: 11 = (1011)2-Následně pro a = 7 určíme a2, a4, a8,... (mod 100) a spočítáme
a11 = atí - a* • a = 1 - 49 • 7 = 43   (mod 100).
.8    .2    _ _
Všimněme si zejména, že vypočítat 791 by nám dalo podstatně větší práci (přitom většinu získaných číslic vůbec nepotřebujeme).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       29 / 52
Kongruence - užitečná zkratka			
	Čínská zbytková věta (CRT)		
	Ve čtvrtém století se čínský matematik Sun Ze (Sun které při dělení třemi dává zbytek 2, při dělení pěti z sedmi je zbytek opět 2.	Tsu) ptal na číslo, bytek 3 a při dělení	
	Řešení		
	Odpověď je (prý) ukryta v následující písni:		
Michal Bulant (Brkos 2016)
Proč je dobré mít i prvočísla 29.8. - 4.9.2016       30 / 52
Kongruence - užitečná zkratka
Čínská zbytková věta
Čínská zbytková věta (CRT)
Ve čtvrtém století se čínský matematik Sun Ze (Sun Tsu) ptal na číslo, které při dělení třemi dává zbytek 2, při dělení pěti zbytek 3 a při dělení sedmi je zbytek opět 2.
Řešení		1
Odpověď je (prý) ukryta	v následující písni: í£-3^ SunziGe 3Lffi & tZ-V-— 41	
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       30 / 52
Kongruence - užitečná zkratka
Čínská zbytková věta
V moderní terminologii nás tedy zajímá, které přirozené číslo x vyhovuje soustavě kongruencí
x = 2 (mod 3) x = 3 (mod 5) x = 2 (mod 7).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       31 / 52
Kongruence - užitečná zkratka
Čínská zbytková věta
Věta (Čínská zbytková věta)
Nechť /77i,,..., m ^ G N jsou po dvou nesoudělná, ai,..., a k £ Z. Pak platí: soustava
x = a\   (mod m\)
x = a/c   (mod m k) má jediné řešení modulo m = mi • rr?2 • • • m k.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
<□►   < [f? ►   < -E ►   < -ž ►      š     •O Q, O 29.8. - 4.9.2016       32 / 52
Kongruence - užitečná zkratka
Čínská zbytková věta
Věta (Čínská zbytková věta)
Nechť /77i,,..., nik G N jsou po dvou nesoudělná, ai,..., a^ G Z. Pak platí: soustava
x = a\   (mod m\)
x = a/c   (mod m^) má jediné řešení modulo m — m\ - m2 - - - m^.
Důkaz.
Označme nj = m/mj. Z předchozího vím, že kongruence ny • y = 1 (mod my) je řešitelná (a její řešení navíc umíme snadno určit pomocí Euklidova algoritmu). Označíme-li její řešení bj, pak je snadno vidět, že x = J2i bj3jnj je hledaným řešením soustavy.
□
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       32 / 52
Kongruence - užitečná zkratka
Čínská zbytková věta
Příklad
Řešme soustavu
x = 2 (mod 3) x = 3 (mod 5) x = 2 (mod 7).
Je možné využít postupu z důkazu nebo si uvědomit, že z vlastností kongruencí plyne ihned x = 2 (mod 21), x = 3 (mod 5) a dosazením x = 2 + 21/c, /e £ Z dostaneme kongruenci 2 + 21/c = 3 (mod 5), neboli k = l (mod 5), odkud x = 23 (mod 105).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016
33 / 52
Kongruence - užitečná zkratka
Čínská zbytková věta
Čínská zbytková věta nám umožní spoustu problémů a výpočtů zabývajících se velkými čísly paralelizovat (výpočet modulo složené m\ • rr?2 lze provést na jednom počítači modulo m\ a na druhém modulo rr?2 a oba výsledky pak zkombinovat).
Michal Bulant (Brkos 2016)
Kongruence - užitečná zkratka
Čínská zbytková věta
Čínská zbytková věta nám umožní spoustu problémů a výpočtů zabývajících se velkými čísly paralelizovat (výpočet modulo složené m\ • rr?2 lze provést na jednom počítači modulo m\ a na druhém modulo rr?2 a oba výsledky pak zkombinovat).
Příklad
Řešte kongruenci 23 941x = 915 (mod 3564)
]
Michal Bulant (Brkos 2016)
Kongruence - užitečná zkratka
Čínská zbytková věta
Čínská zbytková věta nám umožní spoustu problémů a výpočtů zabývajících se velkými čísly paralelizovat (výpočet modulo složené m\ • rr?2 lze provést na jednom počítači modulo m\ a na druhém modulo rr?2 a oba výsledky pak zkombinovat).
Příklad
Řešte kongruenci 23 941x = 915 (mod 3564)
]
Řešení
Rozložme 3564 = 22 • 34 • 11. Protože ani 2, ani 3, ani 11 nedělí číslo 23 941, platí (23 941,3564) = 1 a má tedy kongruence řešení.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       34 / 52
Kongruence - užitečná zkratka
Čínská zbytková věta
Čínská zbytková věta nám umožní spoustu problémů a výpočtů zabývajících se velkými čísly paralelizovat (výpočet modulo složené m\ • rr?2 lze provést na jednom počítači modulo m\ a na druhém modulo rr?2 a oba výsledky pak zkombinovat).
Příklad
Řešte kongruenci 23 941x = 915 (mod 3564)
Řešení
Rozložme 3564 = 22 • 34 • 11. Protože ani 2, ani 3, ani 11 nedělí číslo 23 941, platí (23 941,3564) = 1 a má tedy kongruence řešení. Ze základních vlastností kongruenci vyplývá, že x G Z je řešením dané kongruence, právě když je řešením soustavy
nod 22)
____i o4\
23941x =	915
23941x =	915
23941x =	915
]
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       34 / 52
Kongruence - užitečná zkratka
Čínská zbytková věta
Řešení (pokr.)	
Vyřešíme nyní každou	z kongruencí soustavy zvlášť a dostaneme
ekvivalentní soustavu	
	x =   3   (mod 4)
	x = -3   (mod 81)
	x = -4   (mod 11),
jejímž řešením je x =	-1137 (mod 3564).
Michal Bulant (Brkos 2016)
Kongruence - užitečná zkratka
Čínská zbytková věta
Příklad (IMO 1989)	
Pro která n £ N existuje N £ N tak, že žádné z čísel	
l + A/,2 + A/, ...,n + N	
není mocninou prvočísla.	
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
<□►  < S ►  < -E ►  < -ž ►     š     •O Q, O 29.8. - 4.9.2016       36 / 52
Kongruence - užitečná zkratka
Čínská zbytková věta
Příklad (IMO 1989)
Pro která n £ N existuje N £ N tak, že žádné z čísel
l + A/,2 + A/, ...,n + N
není mocninou prvočísla
Rešení
O Pro dané r? položíme N = ((r? + l)!)2 + 1 a ukážeme, že splňuje zadání.
Q Buďte pi, p2,..., P2n různá prvočísla. Díky CRT existuje N £ N tak, že A/ = —1 (mod P1P2), A/ = —2 (mod P3P4),..., A/ = —r? (mod P2n-iP2n)- Takové A/ ale splňuje zadání.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       36 / 52
Jak poznat prvočísla?
Plán přednášky
o
o Co je to vlastně prvočíslo? o Eulerova funkce cp
o Fermatova a Eulerova věta o Čínská zbytková věta
Q Jak poznat prvočísla? 9 Teoretické základy o Klasické testy s využitím kongruencí
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       37 / 52
Jak poznat prvočísla?
Eratosthenovo síto
Známá metoda, která poskytuje postup, jak nalézt dokonce všechna prvočísla až do jisté hranice.
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Eratosthenovo síto
Známá metoda, která poskytuje postup, jak nalézt dokonce všechna prvočísla až do jisté hranice.
Její jediný, zato však zásadní, problém je časová náročnost - pro zjištění prvočísel až do velikosti N potřebujeme znát prvočísla až do velikosti \/~Ň, což je obvykle příliš mnoho.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       38 / 52
Jak poznat prvočísla?
Teoretické základy
Řád čísla modulo, primitivní kořen
Definice
Řádem čísla a modulo m, kde (a, m) = 1, nazveme nejmenší přirozené číslo r takové, že ar = 1 (mod m).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       39 / 52
Jak poznat prvočísla?
Teoretické základy
Řád čísla modulo, primitivní kořen
Definice
Řádem čísla a modulo m, kde (a, m) = 1, nazveme nejmenší přirozené číslo r takové, že ar = 1 (mod m).
a r | (p(m);
9 modulo prvočíslo p existuje právě (p(p — 1) čísel řádu <p(p) — p — 1 modulo p (menších než p), jde o takzvané primitivní kořeny.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       39 / 52
Jak poznat prvočísla?
Teoretické základy
Kvadratické (ne)zbytky
Definice
Buď p prvočíslo. Číslo a splňující (a, p) = 1 nazveme kvadratickým zbytkem modulo p, jestliže existuje x takové, že x2 = a (mod p), v opačném případě jde o kvadratický nezbytek. Píšeme (a/p) = 1, resp (a/p) = —1 (Legendreův symbol). Dále pro p | a píšeme (a/p) = 0.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016
40 / 52
Jak poznat prvočísla?
Teoretické základy
Kvadratické (ne)zbytky
Definice
Buď p prvočíslo. Číslo a splňující (a, p) = 1 nazveme kvadratickým zbytkem modulo p, jestliže existuje x takové, že x2 = a (mod p), v opačném případě jde o kvadratický nezbytek. Píšeme (a/p) = 1, resp. (a/p) = —1 (Legendreův symbol). Dále pro p | a píšeme (a/p) = 0.
p-i
a (a/p) = a 2   (mod p). a pro a = b (mod p) platí (a/p) = (b/p) • (a • b/p) = (a/p) • (Ď/p).
p-1
PZ-1
a (-1/p) = (-l)^r, (2/p) = (-1)", (p/q) = (q/p) • (-1)^
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       40 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Klasické testy s využitím kongruencí
Wilsonova věta dává sice nutnou i postačující podmínku prvočísel nosti, bohužel nikdo na světě dosud neumít rychle vypočítat faktoriál modulo velké číslo. Proto využijeme ostatní věty, které sice dávají pouze nutnou podmínku prvočísel nosti (Je-li p prvočíslo, pak ...).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016
•f) <\ ry 41 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Klasické testy s využitím kongruencí
Wilsonova věta dává sice nutnou i postačující podmínku prvočísel nosti, bohužel nikdo na světě dosud neumít rychle vypočítat faktoriál modulo velké číslo. Proto využijeme ostatní věty, které sice dávají pouze nutnou podmínku prvočísel nosti (Je-li p prvočíslo, pak ...).
Takovým testem je např. klasický Fermatův test plynoucí ze stejnojmenné věty.
Fermatův test
Existuje-li pro dané N nějaké a ^ 0 (mod N) takové, že aN 1 ^ 1 (mod A/), pak N není prvočíslo.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       41 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Fermatův test není ideální
Bohužel nemusí být pro dané složené N snadné najít a takové, že Fermatův test odhalí složenost A/; pro některá výjimečná N dokonce jediná taková a jsou soudělná s A/, jejich nalezení je tedy ekvivalentní s rozkladem N na prvočísla.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       42 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Fermatův test není ideální
Bohužel nemusí být pro dané složené N snadné najít a takové, že Fermatův test odhalí složenost A/; pro některá výjimečná N dokonce jediná taková a jsou soudělná s A/, jejich nalezení je tedy ekvivalentní s rozkladem N na prvočísla.
Skutečně existují taková nehezká (nebo extrémně hezká?) složená čísla A/, která splňují, že pro libovolné a nesoudělné s N platí aN~ľ = 1 (mod N). Taková čísla se nazývají Carmichaelova, nejmenší z nich je 561 = 3-11-17 (Dokažte) a teprve v roce 1992 se podařilo dokázat, že jich je dokonce nekonečně mnoho.
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Fermatův test není ideální
Bohužel nemusí být pro dané složené N snadné najít a takové, že Fermatův test odhalí složenost A/; pro některá výjimečná N dokonce jediná taková a jsou soudělná s A/, jejich nalezení je tedy ekvivalentní s rozkladem N na prvočísla.
Skutečně existují taková nehezká (nebo extrémně hezká?) složená čísla A/, která splňují, že pro libovolné a nesoudělné s N platí aN~ľ = 1 (mod N). Taková čísla se nazývají Carmichaelova, nejmenší z nich je 561 = 3-11-17 (Dokažte) a teprve v roce 1992 se podařilo dokázat, že jich je dokonce nekonečně mnoho.
Fermatův test lze zlepšit s využitím kvadratických zbytků na Eulerův test
N-l
a 2 = (a/N) (mod A/), ale výše zmíněný problém se zcela neodstraní ani tímto vylepšením.
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Fermatův test není ideální
Bohužel nemusí být pro dané složené N snadné najít a takové, že Fermatův test odhalí složenost A/; pro některá výjimečná N dokonce jediná taková a jsou soudělná s A/, jejich nalezení je tedy ekvivalentní s rozkladem N na prvočísla.
Skutečně existují taková nehezká (nebo extrémně hezká?) složená čísla A/, která splňují, že pro libovolné a nesoudělné s N platí aN~ľ = 1 (mod N). Taková čísla se nazývají Carmichaelova, nejmenší z nich je 561 = 3-11-17 (Dokažte) a teprve v roce 1992 se podařilo dokázat, že jich je dokonce nekonečně mnoho.
Fermatův test lze zlepšit s využitím kvadratických zbytků na Eulerův test
N-l
a 2 = (a/N) (mod A/), ale výše zmíněný problém se zcela neodstraní ani tímto vylepšením.
V praxi se často používají další vylepšení, zejména tzv. Rabin-Millerův t$§t.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       42 / 52
Jak poznat prvočísla?
SSQI    Klasické testy s využitím kongruencí
Různé typy pseudoprvočisel
< □ ►
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočí
sl;
29.8. - 4.9.2016       43 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Carmichaelova čísla
Věta (Korseltovo kritérium)
Složené číslo je Carmichaelovým číslem, právě když je nedělitelné čtvercem (square-free) a pro všechna prvočísla p dělící n platí p — 1 | n — 1.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       44 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Carmichaelova čísla
Věta (Korseltovo kritérium)	1
Složené číslo je Carmichaelovým číslem, právě když je nedě (square-free) a pro všechna prvočísla p dělící n platí p — 1	litelné čtvercem n-1. 1
	
Příklad	1
Dokažte, že čísla 2465 a 2821 jsou Carmichaelova. j	
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       44 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Rabin-Millerův test na složenost
Necht p je liché prvočíslo. Pišme p — 1 = 2ŕ • q, kde t je přirozené číslo a q
je liché. Pak pro každé celé číslo a nedělitelné p buď platí aq = 1
(mod p) nebo existuje e £ {0,1,..., t — 1} splňující= — 1  (mod p).
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Rabin-Millerův test na složenost
Necht p je liché prvočíslo. Pišme p — 1 = 2ŕ • q, kde t je přirozené číslo a q
je liché. Pak pro každé celé číslo a nedělitelné p buď platí aq = 1
(mod p) nebo existuje e £ {0,1,..., t — 1} splňující= — 1  (mod p).
Lze ukázat, že pro lichá složená čísla N v roli prvočísla p v přec h ozí větě splňuje uvedenou podmínku nejvýše ^ z čísel a (najdeme-li tedy a, které podmínku nesplňuje, našli jsme tzv. svědka složenosti).
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Rabin-Millerův test na složenost
Necht p je liché prvočíslo. Pišme p — 1 = 2ŕ • q, kde t je přirozené číslo a q
je liché. Pak pro každé celé číslo a nedělitelné p buď platí aq = 1
(mod p) nebo existuje e £ {0,1,..., t — 1} splňující= — 1  (mod p).
Lze ukázat, že pro lichá složená čísla N v roli prvočísla p v přec h ozí větě splňuje uvedenou podmínku nejvýše ^ z čísel a (najdeme-li tedy a, které podmínku nesplňuje, našli jsme tzv. svědka složenosti).
Příklad
Pomocí SAGE dokážeme, že Carmichaelova čísla 2465 i 2821 jsou složená (díky bázi a = 2).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       45 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Rabin-Millerův test na složenost
Necht p je liché prvočíslo. Pišme p — 1 = 2ŕ • q, kde t je přirozené číslo a q
je liché. Pak pro každé celé číslo a nedělitelné p buď platí aq = 1
(mod p) nebo existuje e £ {0,1,..., t — 1} splňující a^q = — 1  (mod p).
Lze ukázat, že pro lichá složená čísla N v roli prvočísla p v přec h ozí větě splňuje uvedenou podmínku nejvýše ^ z čísel a (najdeme-li tedy a, které podmínku nesplňuje, našli jsme tzv. svědka složenosti).
Příklad
Pomocí SAGE dokážeme, že Carmichaelova čísla 2465 i 2821 jsou složená (díky bázi a = 2).
Složené číslo n, které není tímto testem odhaleno pomocí báze a se nazývá silné pseudoprvočíslo v bázi a. Např. 2047 je silné pseudoprvočíslo vzhledem k bázi 2, 121 vzhledem k bázi 3, . ..
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       45 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Test prvočíselnosti
Ukázali jsme si, jak je možné odhalit složená čísla. Co ale s těmi, která tento test za složená neoznačí? Jsou to prvočísla nebo čísla složená. K ověření toho slouží (časově daleko náročnější) testy na prvočíselnost.
Lucas-Lehmer
Pokud pro libovolný prvočíselný dělitel q čísla N — 1 existuje a tak, že
aN 1 = 1 (mod A/), a     ^ 1 (mod A/), pak je N prvočíslo.
A/-1
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       46 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Test prvočíselnosti
Ukázali jsme si, jak je možné odhalit složená čísla. Co ale s těmi, která tento test za složená neoznačí? Jsou to prvočísla nebo čísla složená. K ověření toho slouží (časově daleko náročnější) testy na prvočíselnost.
Lucas-Lehmer
Pokud pro libovolný prvočíselný dělitel q čísla N — 1 existuje a tak, že
aN 1 = 1 (mod A/), a     ^ 1 (mod A/), pak je N prvočíslo.
A/-1
Důkaz.
Stačí dokázat, že N — 1 dělí <p(N). Pokud ne, tak existuje prvočíslo q a r £ N tak, že qr dělí N — 1, ale ne <p(N). Rád e prvku a dělí N — 1 (první podmínka) a nedělí (A/ — l)/q (druhá podmínka), proto qr dělí e. Navíc e dělí ^(A/), tedy i qr dělí ^(A/), spor. □
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016       46 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
AKS - nedávná indická bomba
Předchozí test má tu nevýhodu, zeje třeba umět kompletně rozložit N —1 na prvočísla. To je snadné třeba u Fermatových čísel, ale obvykle je to obtížné. Proto je užitečné mít k dispozici variantu tohoto testu, která kompletní faktorizaci nepožaduje - viz např. test Pocklingtona a Lehmera.
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
AKS - nedávná indická bomba
Předchozí test má tu nevýhodu, zeje třeba umět kompletně rozložit N —1 na prvočísla. To je snadné třeba u Fermatových čísel, ale obvykle je to obtížné. Proto je užitečné mít k dispozici variantu tohoto testu, která kompletní faktorizaci nepožaduje - viz např. test Pocklingtona a Lehmera.
Veškeré předchozí testy (alespoň teoreticky) strčili do kapsy v roce 2002 indičtí matematici 3 Agrawal, Kayal a Saxena, kteří Fermatův test aplikovali v (jen o málo) složitější algebraické situaci a odvodili z něj test, který je polynomiální časové složitosti (do té doby se vůbec nevědělo, jakou složitost tohoto problému očekávat).
nebo tedy spíše informatici
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016
AI j 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Výměna klíčů
Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ - 1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj náhrada jednorázových klíčů, kurýrů s kufríky, ...).
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla
29.8. - 4.9.2016
48 / 52
Výměna klíčů
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ - 1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýrů s kufříky, ...).
o Dohoda stran na modulu m a primitivním kořenu g (veřejné)
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Výměna klíčů
Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ - 1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýrů s kufříky, ...).
o Dohoda stran na modulu m a primitivním kořenu g (veřejné) a Alice vybere náhodné a a pošle ga (mod m)
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Výměna klíčů
Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ - 1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýrů s kufříky, ...).
o Dohoda stran na modulu m a primitivním kořenu g (veřejné) a Alice vybere náhodné a a pošle ga (mod m) 9 Bob vybere náhodné b a pošle gb (mod m)
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Výměna klíčů
Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ - 1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýrů s kufříky, ...).
o Dohoda stran na modulu m a primitivním kořenu g (veřejné)
a Alice vybere náhodné a a pošle ga (mod m)
9 Bob vybere náhodné b a pošle gb (mod m)
o Společným klíčem pro komunikaci je gab (mod m).
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Dokončení motivačního příkladu RSA
Protože jsme schopni (díky počítači) rozložit n, jsme schopni zprávu dešifrovat:
0=239675027941280548756812205343466895417790207923642 n=374144419156711146897884040346152783797331507019777 e=240911337096020749615795248242245864391942105373709
bezout = xgcd(e, euler_phi(n))
d = Integer(mod(bezout[1], euler_phi(n)))  ; d
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       49 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Odtud umocněním
M=Mod(C,n)~d
dostaneme
M = 6988806982737769788478698689836976.
Ještě kvůli zobrazení upravme
L=list(reversed(M.lift().digits(100)))
L = [69,88,80,69,82,73,77,69,78,84,78,69,86,89,83,69,76]
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Celkem tak dostáváme
import string
S=string.joinfields(map(chr, L), "")
EXPERIMENTNEVYSEL.
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Několik úloh na závěr k přemýšlení
O Zjistěte, jak rozložit n = p • q, znáte-li (p(n)
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       52 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Několik úloh na závěr k přemýšlení
O Zjistěte, jak rozložit n = p • q, znáte-li (p(n)
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       52 / 52
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Několik úloh na závěr k přemýšlení
O Zjistěte, jak rozložit n = p • q, znáte-li (p(n)
Příklad
Rozložte n = 31615577110997599711, víte-li, že (p(n) = 31615577098574867424.
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Několik úloh na závěr k přemýšlení
O Zjistěte, jak rozložit n = p • q, znáte-li (p(n)
Příklad
Rozložte n = 31615577110997599711, víte-li, že (p(n) = 31615577098574867424.
O Navrhněte způsob, jak rozložit n = p • q, víte-li, že p a q jsou podobně velká prvočísla.
Michal Bulant (Brkos 2016)
Jak poznat prvočísla?
Klasické testy s využitím kongruencí
Několik úloh na závěr k přemýšlení
O Zjistěte, jak rozložit n = p • q, znáte-li (p(n)
Příklad
Rozložte n = 31615577110997599711, víte-li, že tp(n) = 31615577098574867424.
O Navrhněte způsob, jak rozložit n = p • q, víte-li, že p a q jsou podobně velká prvočísla.
O Navrhněte způsob, jak rozložit n, pokud zjistíte k veřejnému klíči odpovídající soukromý klíč d.
Michal Bulant (Brkos 2016)
Klasické testy s využitím kongruencí		
Několik úloh na závěr k přemýšlení		
O Zjistěte, jak rozložit n = p • q, znáte-li <p(n).		
■ Příklad		
Rozložte n = 31615577110997599711, víte-li, že tp(n) = 31615577098574867424.		
O Navrhněte způsob, jak rozložit n = p • q, víte-li, že p a q jsou podobně velká prvočísla. O Navrhněte způsob, jak rozložit n, pokud zjistíte k veřejnému klíči odpovídající soukromý klíč d. Q Kvůli rychlosti šifrování bývá někdy doporučováno použít malý veřejný klíč e. Ukažte, že pokud si zvolí e = 3 tři lidé, kterým posíláme tutéž zprávu M, může útočník, který komunikaci		
odposlouchává, zprávu snadno rozšifrovat.
Michal Bulant (Brkos 2016)
Proč je dobré míti prvočísla 29.8. - 4.9.2016       52 / 52