Název: AKS test prvočíselnosti a jeho varianty
Překlad názvu: AKS primality test and its variants
Autoři: Ondo, Tomáš ; Žemlička, Jan (vedoucí práce) ; Pavlů, Jiří (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2023
Jazyk: slo
Abstrakt: [eng] [cze]
In this thesis, the first polynomial deterministic primality test named AKS algori- thm is described. The thesis is focused on the time complexity of the algorithm. Several drawbacks which make this algorithm unsuitable for generating large prime numbers are described. Improvements derived from empirical data are summed up. These improve- ments are not proven, so they do not yield a deterministic test. The thesis continues with a comparison of the runtime of concrete implementations. The thesis also contains a variant of the AKS test, the Bernstein variant, which has a better time complexity. The execution of these algorithms is shown in examples. 1 V tejto práci je opísaný prvý polynomiálny deterministický test prvočíselnosti s ná- zvom AKS algoritmus. Dôraz je kladený hlavne na jeho časovú náročnosť. Sú opísané jeho nedostatky, ktoré neumožňujú jeho použitie pri generovaní veľkých prvočísel. Sú tu zhrnuté navrhnuté zrýchlenia, ktoré pochádzajú z empirických výsledkov. Tieto zrýchle- nia nie sú dokázané, a preto nedávajú deterministický test. Práca pokračuje porovnaním reálneho času výpočtu na konkrétnych implementáciách. Práca ďalej obsahuje variant tohto algoritmu, a to Bernsteinov variant, ktorý má lepšiu asymptotickú časovú nároč- nosť. Chod týchto algoritmov je ukázaný na príkladoch. 1
Klíčová slova: AKS algoritmus|test prvočíselnosti|časová náročnosť; AKS algorithm|primality test|time complexity

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/182562

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-532252


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce