Teorie čísel

Přednášky:

Dělitelnost na N a Z, největší společný dělitel, Euklidův algoritmus
Kanonický rozklad
Množina prvočísel – základní poznatky o rozložení na číselné ose
Prvočíselná funkce, Čebyševovy nerovnosti, prvočíselná věta a Bertrandův postulát
Asymptotická hustota množiny
Relace kongruence na Z
Lineární kongruence
Operace na Zn
Eulerova funkce
Fermatova – Eulerova věta
Miller-Rabinův test prvočíselnosti
RSA algoritmus

Cvičení:

Procvičování vlastností dělitelnosti na N a Z a Euklidova algoritmu
Souvislost kanonického rozkladu s největším společným dělitelem a nejmenším společným násobkem
Výskyt prvočísel v aritmetických posloupnostech a g-adické zápisy čísel
Eratosthenovo síto
Určování asymptotických hustot množin, asymptotická hustota množiny prvočísel
Vlastnosti relace kongruence
Řešení lineárních kongruencí
Těleso Zp, Wilsonova věta
Určení hodnoty Eulerovy funkce
Příklady na Fermatův test prvočíselnosti a Carmichaelovy čísla
Příklady na Miller-Rabinův test prvočíselnosti
Procvičování RSA algoritmu