Testování prvočíselnosti v polynomiálním čase

• Název práce v češtině: Testování prvočíselnosti v polynomiálním čase
• Název v anglickém jazyce: Polynomial time primality testing
• Klíčová slova: AKS algoritmus, prvočísla, časová složitost
• Klíčová slova anglicky: AKS algorithm, prime numbers, time complexity
• Akademický rok vypsání: 2019/2020
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 27.07.2019
• Datum zadání: 17.10.2019
• Datum potvrzení stud. oddělením: 21.11.2019
• Datum a čas obhajoby: 22.09.2020 09:00
• Datum odevzdání elektronické podoby: 28.07.2020
• Datum odevzdání tištěné podoby: 28.07.2020
• Datum proběhlé obhajoby: 22.09.2020
• Oponenti: Mgr. Martin Čech, Ph.D.

Zásady pro vypracování

Cílem práce bude kompletní matematický popis deterministického algoritmu s polynomiální časovou složitostí testujícího prvočíselnost, který roku 2002 zveřejnili Manindra Agrawal, Neeraj Kayal a Nitin Saxena [1]. Kromě původního AKS testu se student může zabývat rovněž jeho variantou [2] nebo na příkladech výpočtů ilustrovat meze jeho praktického použití.

Seznam odborné literatury

[1] Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Annals of Mathematics, 160 (2004), 781–793.

[2] Bernstein, D.J: Proving Primality in Essentially Quartic Random Time, Mathematics of Computation Vol. 76, No. 257 (Jan., 2007), 389-403.

[3] Dietzfelbinger, M.: Primality testing in polynomial time. From randomized algorithms to “PRIMES is in P”. Lecture Notes in Computer Science 3000, Springer Berlin 2004.