View Larger Map
- Christian Mauduit (Université de la Méditerranée,Luminy - France)
- Francesco Pappalardi (Università Roma Tre - Italy)
- Igor Shparlinski (Macquarie University, Sydney - Australia)
- Kanhaiya Jha (Kathmandu University - Nepal) Local Organizer
PROGRAM WITH SILLABI:
- FIRST PART (MISE A NIVEAU)
- Francesco Pappalardi
Algorithmic introduction to Number Theory
Note: The course will consist of six lectures; each
paragraph in the syllabus below corresponds to the
content of one lecture.
- The Euclidean Algorithm for computing GCD; applications to Modular
Arithmetic. Other algorithms for computing GCD. The Fundamental
Theorem of Arithmetic; applications.
- Algorithms for fast modular exponentiation. The Chinese Reminder
Theorem. The notion of pseudo prime and Fermat's Little Theorem.
- The Euler function. Euler Theorem. Existence of primitive roots.
Algorithms for computing primitive roots.
- Quadratic residues and the quadratic reciprocity.
- Fast algorithms for computing Legendre's symbols. The notion
of Euler pseudo prime.
- Lucas Sequences and their divisibility properties.
- A Course in
Computational Number Theory,
David Bressoud and Stan Wagon,
- Kalyan Chakraborty (HarishChandra Research Institute)
Introduction to basic Cryptography
- RSA: The basic algorithm. Connection with factoring, Textbook RSA.
- Basic algorithms for primality testing and factoring: Solovay-Strassen
and Miller-Rabin tests. The Pollard rho method and other simple
- Discrete Logarithms: The general DL problem. The Diffie Hellman Key
exchange protocol, ElGamal, Massey-Omura.
- Algorithms for computing DL: Shanks Algorithm, Polhig Hellman
Algorithm, Index Calculation.
- Digital Signatures: The basic problem and various examples (RSA,
- Corrado Falcolini (Roma Tre) Wolfram Mathematica Laboratory
- Introduction to the use of the software Mathematica: integer numbers,
lists, 2D plots, sequences and patterns, simple programs.
Problems and issues: special sequences, factorization, GCD algorithms.
- More on Mathematica: numbers and precision, functions, recursion,
visualization. Problem and issues: modular powers, pseudoprimes, Euler's phi
function, prime numbers.
- More on Mathematica: special functions in Number Theory, PrimePi,
LogIntegral, Zeta, large size computations.
Problem and issues: pi function, logarithmic integral, Gilbreath's
conjecture, Riemann zeta function.
- Problems and issues: applications to Cryptography, continued
fractions, Lucas sequences, prime testing.
- A Course in Computational Number Theory, David Bressoud and Stan Wagon,
- Roberto Ferretti (Roma Tre) Selected Numerical Methods
- Numerical solution of scalar equations
General theoretical framework. Existence of solution and bisection algorithm. Fixed point methods. The Newton method and its modifications.
- Polynomial interpolation General theoretical framework. The Lagrange polynomial. Convergence of the interpolating polynomial and practical strategies of implementation.
- Exercises Implementation of the algorithms in a high-level scientific environment (MATLAB, Mathematica,...)
- Michel Waldschmidt (Paris) Finite Fields
- Background: group theory, ring theory, field theory, arithmetic.
Gauss fields, Cyclotomic polynomials.
- Finite fields: existence, unicity, structure, explicit construction.
Frobenius automorphisms. Galois's Theory of finite fields.
Introduction to error correcting codes.
- Course Notes
- Dummit, D. S. and Foote, R. M. - Abstract Algebra, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 1998. §14.3: Finite Fields, pp. 499-505.
- Lang, S. - Algebra, 3rd Ed.
- Lidl, R. and Niederreiter, H. - Introduction to Finite Fields and their Applications. Cambridge University Press; 2 edition (August 26, 1994)
- (On the internet:) Shoup, V. - A Computational Introduction to Number Theory and Algebra (Version 2) second print editon, Fall 2008
- SECOND PART
- Pierre Arnoux (Luminy) Primality Testing and Factoring Algorithms
- Introduction: prime numbers and factorization.
Elementary results; the sieve of Eratosthenes. Practical importance of primality testing and factoring algorithms.
- Primality testing. The various properties of algorithms: running time, determinism.
Some classical algorithms: Fermat (pseudo-primes and Carmichael numbers), Rabin-Miller, Solovay-Strassen.
The AKS algorithm and its variants.
- Factoring algorithms. Classical algorithms: trial division, Fermat, Euler, continued fraction.
Modern algorithms: Pollard's rho method, Dixon's algorithm, Lenstra elliptic curve factorisation, sieve algorithms.
Quantum algorithm: Shor's algorithm.
- Shigeru Kanemitsu (Fukuoka) The Riemann zeta function
We shall give some rudiments of the theory of the Riemann zeta-and allied zeta-functions. We start from the special values of the Riemann zeta-function
at negative integer arguments using the Abel mean and the polylogaritm function. In deriving the closed form, we will learn the Eulerian polynomials and
Sitrking numbers. Then we learn some historical facts proved stated by Euler and proved by Landau concerning the functional equation satsified by the
Riemann zeta and allied functions.
Thereby we learn the Hurwitz-Lecrh zeta-function. This setting will be generalized in a colossal one in terms of he Forx H-fnction.
Alos, the Euler product is introduced which distinguished the Riemann zeta from other ones which do not have them. We shall also mention some relatonship
with the RSA cryptosystem.
- Christian Mauduit (Luminy) Pseudorandom Sequences and Cryptography
- Stream ciphers and cryptography.
- What is a pseudorandom sequences ?
- Measures of pseudorandomness.
- Applications of number theory to the construction of pseudorandom sequences.
- D. Knuth, The art of computer programming, vol. 2.
- A. Menezes, P. van Oorschot and S. Vanstone, Handbook of applied cryptography.
- Jorge Jimenez Urroz (Universitad Politecnica de Catalunya) Elliptic Curves in Cryptography
- INTRODUCTION: Weierstrass Equations, The Group Law, The j-Invariant,
Elliptic Curves in Characteristic 2, Endomorphisms, Singular Curves, Elliptic Curves mod n
- TORSION POINTS: Division Polynomials, The Weil Pairing.
- Elliptic Curves over Finite Fields: The Frobenius Endomorphism, Determining the Group Order, Schoof's Algorithm
- The Discrete Logarithm Problem: The Index Calculus, Attacks with Pairings
- Elliptic Curve Cryptography: The Basic Setup, Diffie-Hellman Key Exchange, Massey-Omura Encryption, ElGamal Public Key Encryption, ElGamal Digital Signatures, The Digital Signature Algorithm, ECIES
- Other Applications: Factoring Using Elliptic Curves, Primality Testing
- Course Notes
- Lawrence C. Washington Elliptic Curves: Number Theory and Cryptography, Second Edition
Series: Discrete Mathematics and Its Applications Volume: 50, CRC 2008
- Kanhaiya Jha (KU, Nepal) Division Algorithm and Fixed Point
- R.P. Pant (Kumaon University) Number Theory and fixed point
REGISTRATION AND FINANCIAL SUPPORT:
Last update: July 19th 2010