Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MML0007	Computational Algebra	

Semester	Hours: C+S+L	Category	Status	
4	2+2+0	speciality	optional	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
SACAREA Christian	Ph.D.	Lect.	Algebra	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
An introduction to Computational Algebra by a survey of applications of algebraic algorithms in Cryptography, Coding Theory, and Conceptual Knowledge Processing and Representation.

•	To present the main methods and applications of modern algebra in Crzptography, Coding Theory, and Conceptual Knowledge Processing and Representation.
•	Prime generating algorithms and primality testing methods 
•	To present the state of the art factorization methods 
•	Diffie-Hellman key exchange, discrete logarithms
•	To present main tools from Coding Theory 
•	Applications of the methods of Conceptual Knowledge Processing 

IV. Course contents
1. Notions of algorithm complexity. The big O notation. Complexity classes. 
2. Congruence relations and congruence classes. The Euclid algorithm, the Euler’s function, the Chinese remainder theorem, public key encryption algorithms: RSA, ElGamal. Digital signatures, algorithms. 
3. Primality testing. Quadratic residues, Legendre and Jacobi symbol. 
4. Encoding and decoding devices. Linear codes, cyclic codes, Reed-Muller codes. Polynomial factoring algorithms with applications in the construction of decoding devices. 
5. Conceptual Knowledge Processing methods, attribute exploration, applications. Conceptual navigation in databases. 	

V. Bibliography
1.	S. Crivei, A. Mărcuş, C. Săcărea, C. Szanto, Computational Algebra with applications to cryptography and coding theory, Efes 2006.
2.	W. Bosma, A. van der Porten, Computational Algebra and Number Theory, Kluwer 1995. 
3.	D. Bressoud, S. Wagon, A Course in Computational Number Theory, Springer-Verlag 2000. 
4.	H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 2000.
5.	H. Cohen, A.M. Cuypers, H. Sterk, Some Tapas of Computer Algebra, Springer-Verlag,  1999. 
6.	R. Crandall, C. Pomerance, Prime Numbers. A Computational Perspective, Springer-Verlag, 2001.
7.	K. Ireland, M. Rosen, A Classical Introduction to Number Theory, Springer-Verlag, 1990.
8.	N. Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag, 1994.
9.	R. Lidl, G. Pilz, Applied Abstract Algebra, Springer-Verlag, 1998.
10.	H.S. Wilf, Algorithmes et complexite, Masson, Paris, 1989.
11.	B. Ganter, R. Wille, Formal Concept Analysis, Springer 2000.	

VI. Thematic of didactic activities per weeks
1.	An introduction to Computational Algebra  (1 lecture + 1 exercise class)
•	What is Computational Algebra?
•	Applications: computer graphics, optimization, cryptography, coding theory 
•	Introduction in cryptography. Monoalphabetic substitution cipher. 

2.	From classical cryptography to public key cryptography (1 + 1)
•	Polyalphabetic ciphers
•	The ENIGMA machine
•	Problems occurring when using encryption machines 
•	Key exchange
•	Diffie – Hellman method
•	Discrete logarithms problem

3.	From public key cryptography to algorithm complexity (1 + 1)
•	Public key cryptography
•	One way functions. Computational problems 
•	RSA
•	Security of RSA
•	Examples

4.	Algorithm complexity (1 + 1)
•	Computational aspects
•	Computation complexity
•	Algorithms efficiency
•	Examples: fractals
•	Running times. Examples
•	Big O notation
•	Complexity classes.

5.	Prime numbers  (1 + 1)
•	Prime numbers.
•	Prime numbers mysteries
•	Computing primes
•	Prime distribution
•	Mersenne numbers
•	Primality tests: sieve of Erathostenes, sieve of Atkins

     6.  Primality tests (1 + 1)
•	Fermat probable primes
•	Fermat primality testing
•	Carmichael numbers
•	Euler pseudoprimes
•	Euler Jacobi pseudoprimes
•	Solovay-Strassen test

7.	Primality tests (1  + 1)
•	Miller-Rabin test
•	Strong pseudoprimes
•	Lucas-Lehmer test
•	Agraval-Kayal-Saxena-Lenstra test

8.	Factoring  (1 + 1)
•	Attacks against RSA
•	Evolution of factorization
•	Pollard rho
•	Pollard p-1
•	Williams p+1
•	Fermat

9.	Factoring algorithms (1 + 1)
•	The factor base method
•	The continued fractions method
•	The quadratic sieve method

10.	Discrete logarithms (1 + 1)
•	Diffie-Hellman key exchange
•	ElGamal algorithm
•	Discrete logarithms problem
•	Baby step-giant step algorithm

11.	Coding theory (2 + 2)
•	Examples
•	Linear codes
•	Cyclic codes
•	The dual of a code
•	Reed-Muller codes
•	Polynomial factorization methods

12.	Conceptual Knowledge Processing (2 + 2)
•	Concept hierarchies
•	Knowledge representation
•	Graphical representation of conceptual hierarchies 
•	Formal Concept Analysis
•	Stem base finding algorithm, next closure algorithm
•	Attribute exploration

VII. Didactic methods used
Lecture, presentation, projects, exercises, individual study	

VIII. Assessment
To the end of the semester, the students have to write a project, consisting of practical implementation of the algorithms discussed in the course, as well as solving a concrete Computational Algebra problem. The final grade is the grade of this project. 	

IX. Additional references
A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997.
B. Schneier, Applied Cryptography, John Wiley & Sons, New York, 1996.	

Dean                                                                                      Chair head,
Prof. Dr. Leon Tambulea                                                    Conf. Dr. Simion Breaz

	Date,							Course responsible,
March 3, 2009						Lect. SACAREA Christian, Ph.D.