M8190 Number Theoretic Algorithms

Faculty of Science
Spring 2008 - for the purpose of the accreditation
Extent and Intensity
2/0/0. 2 credit(s) (fasci plus compl plus > 4). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Radan Kučera, DSc. (lecturer)
Guaranteed by
prof. RNDr. Radan Kučera, DSc.
Department of Mathematics and Statistics – Departments – Faculty of Science
Contact Person: prof. RNDr. Radan Kučera, DSc.
Prerequisites
Algebra II or Algebra 2
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
The aim of the lecture is to show that results of number theory can help to factorize a given large positive integer into the product of prime numbers. The importance of this task grows up because of applications in coding theory.
Syllabus
  • (1) Compositeness tests: Fermat test, Carmichael numbers, Rabin-Miller test. (2) Primality tests: the Poclington-Lehmer n-1 test, the elliptic curve test. (3) Factoring: Lehmann's method, Pollard's $\rho$ method, Pollard's p-1 method, the continued fraction method, the elliptic curve method, the quadratic sieve method.
Literature
  • COHEN, Henri. A Course in Computational Algebraic Number Theory. Springer-Verlag, 1993, 534 pp. Graduate Texts in Mathematics 138. ISBN 3-540-55640-0. info
Language of instruction
Czech
Further Comments
The course is taught once in two years.
The course is taught: every week.
Teacher's information
ftp://www.math.muni.cz/pub/math/people/Kucera/lectures/atc.ps
The course is also listed under the following terms Spring 2004, Spring 2006, Spring 2008, Spring 2010, Spring 2012, spring 2012 - acreditation, Spring 2014, Spring 2016, spring 2018, Spring 2020, autumn 2021, Autumn 2023.