Introduction to algorithmic number theory
Professor: Jean-Sebastien Coron.
The goal of the course is to give an introduction to algorithmic number theory.- Monday, September 28th, 2009: 9h45-11h15
Course: C programming.
TP: Computations in C. - Monday, September 28th, 2009: 11h30-13h00
Course: C programming. Euclid's algorithm
TP: Computations in C. - Monday, October 12th, 2009: 09h45-11h15
Course: C programming. Euclid's extended algorithm.
TP: Euclid's extended algorithm. - Monday, October 12th, 2009: 11h30-13:00
Course: Modular arithmetic. Chinese remainder theorem.
TP: implementation. - Monday, October 26th, 2009: 09h45-11h15
Course: Computing with large integers.
TP: Addition and multiplication of large integers. - Monday, October 26th, 2009: 11h30-13h00
Course: modular exponentiation
TP: implementation of modular exponentiation - Monday, November 9th, 2009: 9h45-11h15
Course: computing with large integers: division.
TP: modular computation. - Monday, November 9th, 2009: 11h30-13h00.
Course: Euler function and Fermat's little theorem.
TP: Euler function. - Monday, November 23rd, 2009: 9h45-11h15
Course: The RSA algorithm
TP: Implementation of RSA with small parameters. - Monday, November 23rd, 2009: 11h30-13h00
Course: Primality tests
TP: Implementation of Fermat's test and Rabin's test. - Monday, December 7th, 2009: 09h45-11h15
Course: Generators and discrete-log
TP: Implementation of Diffie-Hellman protocol. - Monday, December 7th, 2009: 11h30-13h00
Course: Polynomials
TP: Implementation. - Monday, December 14th, 2009: 11h30-13h00.
Course: Euclid's algorithm on polynomials
TP: Implementation.
Homework: big integer library and implementation of RSA.
This homework is due February 7th, 2010. It will make 50% of the final grade.
References:
- A Computational Introduction to Number Theory and Algebra, Victor Shoup.