Přednáška uvádí do některých důležitých pojmů teorie čísel. Zaměření na testy prvočíselnosti a metody faktorizace vyplývá z toho, že se v ní rovněž popisuje kryptosystém RSA.
Poslední úprava: T_KA (17.05.2003)
An introduction to fundamental concepts of number theory.
Focuses on primality testing and methods of integer factorization in connection with
RSA cryptosystem.
Literatura
Poslední úprava: T_KA (23.05.2003)
Borevič, Šafarevič: Number Theory, Academic Press 1966;
Riesel: Prime numbers and computer methods for factorization, Birkhäuser 1985;
Cohen: A course in computational algebraic number theory, Springer-Verlag 1993.
Sylabus -
Poslední úprava: T_KA (23.05.2003)
Číselné vlastnosti s algebraickou interpretací (Eulerova funkce, primitivní prvky, Gaussova celá čísla a čtverce). Kvadratická residua a zákon reciprocity. Kryptosystém RSA. Hledání prvočísel (prvočísla speciálního tvaru, hustota výskytu, Bertrandův postulát). Jednoduché testy složených čísel (Carmichaelova čísla, test Solovaye a Strassena, Rabin-Millerův test). Nástin dalších metod používaných pro testy prvočíselnosti a pro faktorizaci. Řetězové zlomky. Diofantické rovnosti.
Poslední úprava: T_KA (21.05.2004)
Properties of integers with algebraic interpretation (Euler function, primitive elements, Gauss integers and squares). Quadratic residues and reciprocity law. RSA cryptosystem. Searching for prime numbers (prime numbers of special type, density of primes, Bertrand postulate). Simple composite-number tests (Carmichael numbers, Solovay-Strassen test, Rabin-Miller test). An outline of other methods used for primality testing and factorization. Continued fractions. Diophantine equations.