Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate
SUBJECT

Code	Subject	
MML0007	Computational Algebra	

Section	Semester	Hours: C+S+L	Category	Type	
Computer Science - in Romanian
Computer Science - in English	4	2+2+0	speciality	optional	

Teaching Staff in Charge	Lect. SACAREA Cristian, Ph.D., csacarea@math.ubbcluj.ro
Lect. SZANTO Csaba Lehel, Ph.D., szanto@math.ubbcluj.ro	
Aims	An introduction to Computational Algebra by a survey of applications of algebraic algorithms in Cryptography, Coding Theory and Conceptual Knowledge Processing and Representation.	
Content	1. Notions of algorithms complexity. The O notation, classes of complexity.
2. Congruences and residue classes. Euclid's algorithm, Euler's function, Chinese remainder theorem, quadratic residues, Legendre's symbol. 
3. Primality tests. Fermat, Solovay-Strassen and Miller-Rabin primality tests, deterministic tests.
4. Factorization methods. Elementary methods, Rho method, factor bases method, continued fractions method, quadratic sieve method. Applications to Cryptography.
5. Polynomials over finite fields. Finite fields, discret logarithm, irreducible polynomials, Berlekamp's algorithm of polynomial factorization. Applications to Cryptography.
6. Other algorithms. Fast addition, fast Fourier transform.	
Bibliography	1. W. Bosma, A. van der Porten, Computational Algebra and Number Theory, Kluwer 1995. 
2. D. Bressoud, S. Wagon, A Course in Computational Number Theory, Springer-Verlag 2000. 
3. H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 2000.
3. H. Cohen, A.M. Cuypers, H. Sterk, Some Tapas of Computer Algebra, Springer-Verlag,  1999. 
4. R. Crandall, C. Pomerance, Prime Numbers. A Computational Perspective, Springer-Verlag, 2001.
5. K. Ireland, M. Rosen, A Classical Introduction to Number Theory, Springer-Verlag, 1990.
6. N. Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag, 1994.
7. R. Lidl, G. Pilz, Applied Abstract Algebra, Springer-Verlag, 1998.
8. A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997.
9. B. Schneier, Applied Cryptography, John Wiley & Sons, New York, 1996.
10. H.S. Wilf, Algorithmes et complexite, Masson, Paris, 1989.	
Assessment	Exam.