Syllabus
1. Data representation, basic operations with numbers and polynomials, Karacuba's and extended Euclid's algorithm.
2. Modular representation, algorithms for Chinese Remainder Theorem. Fast Fourier transform, fast multiplication of polynomials.
3. Newton's method and fast division of polynomials.
4. Greatest common divisor: Primitive polynomials and Gauss' lemma, polynomial remainder sequences, modular algorithm.
Annotation
Required course for bachelor's program in Information security. The course contains description of algorithms used in computer systems for symbolic manipulation.
It begins with analysis of the simplest algebraic algorithms and shows how to use theoretic results for their improvement. Algorithms for polynomials over integers, rational numbers or finite fields are emphasized.