Testování prvočíselnosti
| Název práce v češtině: | Testování prvočíselnosti |
|---|---|
| Název v anglickém jazyce: | Primality testing |
| Akademický rok vypsání: | 2006/2007 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | doc. RNDr. Martin Klazar, Dr. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 18.10.2006 |
| Datum zadání: | 18.10.2006 |
| Zásady pro vypracování |
| Student vypracuje přehled algoritmů pro testování a dokazování prvočíselnosti, zejména tzv. AKS testu, s důrazem na
matematické teorémy, o něž se tyto algoritmy opírají. Podá též přehled jejich časové složitosti a pokusí se zlepšit složitost AKS testu. |
| Seznam odborné literatury |
| [1] M. Agrawal, N. Kayal and N. Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004) 781-793.
[2] R. Crandall and C. Pomerance, Prime Numbers. A Computational Perspective. Second Edition, Springer, Berlin, 2006. [3] L. Kučera, Kombinatorické algoritmy, SNTL, Praha, 1983. Popř. další časopisecká literatura. |
| Předběžná náplň práce |
| Student vypracuje přehled algoritmů pro testování a dokazování prvočíselnosti, zejména tzv. AKS testu, s důrazem na matematické teorémy, o něž se tyto algoritmy opírají. Podá též přehled jejich výpočetní složitosti a pokusí se zlepšit složitost AKS testu. |
| Předběžná náplň práce v anglickém jazyce |
| The task of the student is to produce a survey of algorithms for primality testing and primality proving, including the AKS test,
with emphasize on the underlying mathematics. Also, (s)he will survey computational complexity of these algorithms and will attempt to improve the computational complexity of the AKS test. |