Original title:
AKS test prvočíselnosti a jeho varianty
Translated title:
AKS primality test and its variants
Authors:
Ondo, Tomáš ; Žemlička, Jan (advisor) ; Pavlů, Jiří (referee) Document type: Bachelor's theses
Year:
2023
Language:
slo Abstract:
[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. 1V 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
Keywords:
AKS algorithm|primality test|time complexity; AKS algoritmus|test prvočíselnosti|časová náročnosť
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/182562