General
Information  Announcements  Course Objectives  Course Topics  Lectures
 Practical
Works  Required Text and Materials
 Class Requirements  Exams
Sorin Iftene
Office: C904
Email: siftene@info.uaic.ro
Tel: (0232) 201531
Course
– Friday, 8:0010:00, in C112
April 3 – Homework 3
has been posted in Google Classroom
March 15: A
dedicated Google Classroom Account has been created – please contact me for
login info
March 12: The Classes are suspended during March
1331

Homework 1 can be
sent by email to siftene2013@gmail.com
tomorrow (March 13) or next week (submissions more than one week late will not
be accepted)

Homework 2 will
be presented after the classes are resumed (any question regarding this
homework can be sent by email to siftene2013@gmail.com)

Homework 2 
Addition chains can be generated using any method described in the course on Exponentiation
Techniques (see below)  any question
regarding this topic can be sent by email to siftene2013@gmail.com
March 9: Homework 2 has been
posted (Due: March 30,31, April 2, 3)
February 17: Homework 1 has been
posted (Due: March 913)
This course will focus on designing
efficient algorithms (and providing complexity analysis) for the most important
problems from number theory, with major applications in coding theory and
cryptography.
 Representations of
Integers and Polynomials
 Basic Operations
(addition, subtraction, multiplication, division, (extended) gcd, inverse,
Chinese remainder theorem)
 Exponentiation and
Multiexponentiation
 Primality
Testing (Probabilistic Primality
Testing, Primality Testing for Numbers of
a Special Form, AKS primality test (including detecting perfect powers))
 Computing the Order
of an Element and Generating Primitive Roots (and Elements of a Certain Order)
 Computing Discrete
Logarithms
 Factoring Integers
 Factoring
Polynomials and Tests for and Constructing Irreducible Polynomials
 Solving Equations
over Finite Fields (including computing square roots)
 The Arithmetic of
Elliptic Curves
1. Course
Overview.
Representations of Integers and
Polynomials (February 21)
References
 Section 1 of [3]
2. Basic Operations (I) (addition,
subtraction, multiplication, squaring, division) (February
28)
References
 Sections 1.2, 1.3
of [4]
Supplementary
Reading  P. L. Montgomery. Five,
Six, and SevenTerm KaratsubaLike Formulae.
3. Basic Operations (II) ((extended)
gcd, Chinese remainder theorem, Hensel’s lifting lemma) (March 6)
References
Sections 1.6, 2.7 of [4]
4.
Exponentiation Techniques (March 13)  any
question regarding this topic can be sent by email to siftene2013@gmail.com
References

Section 7 of [3]

Examples are available here
A dedicated Google Classroom Account has been created – please
contact me for login info
Homework
1 (Posted on February 17, Due: March 913)
Homework
2 (Posted on March 9, Due: March 30,31, April
2, 3)
Homework 3 has been
posted in Google Classroom
Class participation: Students are expected to come prepared and
actively participate in the courses and practical works.
The course grade will be determined
as follows:
presentation of homeworks (during practical works):
50%
midterm exam: 25%
final exam: 25%
(You have to collect at least 50% points from
the practical works and at least 50% points from each exam)
 midterm exam – TBA
 midterm reevaluation exam – TBA
 final exam – TBA
 final
reevaluation exam – TBA