Universitatea "Babeş-Bolyai" din Cluj-Napoca

Facultatea de Matematică şi Informatică
FISA DISCIPLINEI

Algebră computaţională şi teoria numerelor Computational algebra and number theory
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Sectia
MA027
5
2+1+0
5
optionala
Matematică-Informatică
(Mathematics-Computer Science)
Cadre didactice indrumatoare Teaching Staff in Charge
Prof. Dr. MARCUŞ Andrei, marcus@math.ubbcluj.ro
Obiective Aims
Prezentarea unor algoritmi fundamentali cu aplicatii in teoria numerelor. Discutia complexitatii acestor algoritmi. Accentul va fi pus pe teste de primalitate si algoritmi de factorizare.
We present several fundamental algorithms with applications to number theory. We discuss the complexity of these algorithms.The main stress will be on primality tests and factorization of integers.
Continut
I. Congruente si clase de resturi
1. Complexitatea algoritmilor, notatia O
2. Algoritmul lui Euclid
3. Congruente ( Teorema lui Euler, Teorema lui Fermat, Teorema Chineza a resturilor, Rezolvarea congruentelor si sistemelor de congruente de gradul intii
4. Grupul (U(Zn);) Radacini primitive si indici. Rezolvarea congruentelor binome
5. Resturi patratice. Simbolul lui Legendre
II. Teste de primalitate si factorizare
1. Metode elementare. Numere pseudoprime
2. Metoda Monte-Carlo
3. Metoda Fermat
4. Metoda fractiilor continue
5. Metoda sitei patratice si metoda lui Pollard
III. Polinoame peste corpuri finite
1. Corpuri finite Logaritmul discret
2. Polinoame ireductibile
3. Factorizarea polinoamelor. Algoritmul lui Berlekamp
IV. Alti algoritmi
1. Adunarea rapida
2. Transformarea Fourier rapida
3. Baze Gröbner. Algoritmul lui Buchberger
4. Generatorr si relatii in grupuri. Algoritmul Todd-Coxeter
5. Algoritmul LLL
Bibliografie
1. N. Koblitz - A Course in Number Theory and Cryptography, Springer-Verlag 1994
2. K. Ireland, M. Rosen - A Classical Introduction to Number Theory, Springer-Verlag 1990
3. D. Bressoud, S. Wagon - A Course in Computational Number Theory, Springer-Verlag 2000
4. D. Knuth - A számítógép programozás müvészete, Müszaki Könyvkiadó, Budapest
5. T. H. Cormen, Ch. Leiserson, R. R. Rivest - Algoritmusok, Müszaki könyvkiadó, Budapest
6. M. Schönert et al, GAP - Groups, Algorithms and Programming, RWTH Aachen 1995.
Evaluare Assessment
Examen.
Exam.