Computational Number Theory

Spring 2020

 

 

 

General Information | Announcements | Course Objectives | Course Topics | Lectures | Practical Works | Required Text and Materials | Class Requirements | Exams

 

 

General Information

Instructor

Sorin Iftene

           Office: C904

           E-mail: siftene@info.uaic.ro

           Tel: (0232) 201531

          

Class Time and Location

          Course – Friday, 8:00-10:00, in C112

                                       

 

 

Announcements

 

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 13-31

-       Homework 1 can be sent by e-mail 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 e-mail 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 e-mail 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 9-13)

 

 

Course Objectives

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.

 

 

 

Course Topics

-      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

 

 

Lectures

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 Seven-Term Karatsuba-Like Formulae. IEEE Transactions on Computers, vol. 54, no. 3, pp. 362-369, 2005

 

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 e-mail 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

Practical Works

 

Homework 1 (Posted on February 17, Due: March 9-13)

Homework 2 (Posted on March 9, Due: March 30,31, April 2, 3)

Homework 3 has been posted in Google Classroom

 

 

 

 

 

 

 

Required Text and Materials

 

[1] Abhijit Das. Computational Number Theory. CRC Press, 2013

[2] Hans Riesel. Prime Numbers and Computer Methods for Factorization (2nd Edition). Birkhäuser,  2012

[3] F. L. Ţiplea et al. MpNT: A Multi-Precision Number Theory Package. Number Theoretical Algorithms (I). TR03-02, Faculty of Computer Science, “Al. I. Cuza” University,  2003

[4] R. P. Brent, P. Zimmermann. Modern Computer Arithmetic. Cambridge University Press, 2010

[5] relevant conference or journal articles (will be gradually announced)

 

 

Class Requirements

 

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)

 

 

Exams

 - midterm exam  –  TBA

- midterm re-evaluation exam  –  TBA

 - final exam  –  TBA

 - final re-evaluation exam  –  TBA