CIMPA School of Number Theory in Cryptography and Its Applications
School of Science, Kathmandu University, Dhulikhel, Nepal
July 19^th - July 31^th, 2010

The School in also supported by the
The Abdus Salam International Center for Theoretical Physics
and by the
International Mathematical Union

ORGANIZING COMMITTEE:

• 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)
  1. TBA Algorithmic introduction to Number Theory
     Syllabus:
     Note: The course will consist of six lectures; each paragraph in the syllabus below corresponds to the content of one lecture.

     1. The Euclidean Algorithm for computing GCD; applications to Modular Arithmetic. Other algorithms for computing GCD. The Fundamental Theorem of Arithmetic; applications.
     2. Algorithms for fast modular exponentiation. The Chinese Reminder Theorem. The notion of pseudo prime and Fermat's Little Theorem.
     3. The Euler function. Euler Theorem. Existence of primitive roots. Algorithms for computing primitive roots.
     4. Quadratic residues and the quadratic reciprocity.
     5. Fast algorithms for computing Legendre's symbols. The notion of Euler pseudo prime.
     6. Lucas Sequences and their divisibility properties.

     Reference book:

     • A Course in Computational Number Theory, David Bressoud and Stan Wagon, Springer 2000

     
     
     

     Kalyan Chakraborty (HarishChandra Research Institute) Introduction to basic Cryptography

     Syllabus:
     

     1. RSA: The basic algorithm. Connection with factoring, Textbook RSA.
     2. Basic algorithms for primality testing and factoring: Solovay-Strassen and Miller-Rabin tests. The Pollard rho method and other simple factoring algorithms.
     3. Discrete Logarithms: The general DL problem. The Diffie Hellman Key exchange protocol, ElGamal, Massey-Omura.
     4. Algorithms for computing DL: Shanks Algorithm, Polhig Hellman Algorithm, Index Calculation.
     5. Digital Signatures: The basic problem and various examples (RSA, ElGamal, ...)

     
     
     

     Corrado Falcolini (Roma Tre) Wolfram Mathematica Laboratory

     Syllabus:

     1. 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.
     2. More on Mathematica: numbers and precision, functions, recursion, visualization. Problem and issues: modular powers, pseudoprimes, Euler's phi function, prime numbers.
     3. 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.
     4. Problems and issues: applications to Cryptography, continued fractions, Lucas sequences, prime testing.

     Reference book:

     • A Course in Computational Number Theory, David Bressoud and Stan Wagon, Springer 2000

     
     
     

     Roberto Ferretti (Roma Tre) Selected Numerical Methods

     Syllabus:

     1. Numerical solution of scalar equations General theoretical framework. Existence of solution and bisection algorithm. Fixed point methods. The Newton method and its modifications.
     2. Polynomial interpolation General theoretical framework. The Lagrange polynomial. Convergence of the interpolating polynomial and practical strategies of implementation.
     3. Exercises Implementation of the algorithms in a high-level scientific environment (MATLAB, Mathematica,...)

     
     
     

     Elisabetta Scoppola (Roma Tre) Introduction to Probability

     Syllabus:

     1. History: Classical Cryptography (Substitution Cipher, Affine Cipher, Vigenère Cipher, Hill Cipher, Permutation Cipher , Stream Cipher), Cryptoanalysis.
     2. Shannon's Theory: Elementary probability Theory, Perfect Secrecy, Entropy (Huffman Encoding), Product Cryptosystems.
     3. Advanced Encryption Standard.

     • References: Cryptography, Theory and Practice. Douglas R. Stinson. Chapman & Hall/CRC 2005 (third edition).

     
     
     

     Michel Waldschmidt (Paris) Finite Fields

     Syllabus:

     1. History: Gauss fields, Fields with p elements with p prime.
     2. Finite fields: existence, unicity, structure, explicit construction. Frobenius automorphisms. Galois's Theory of finite fields. Algorithms for polynomials over finite fields. Elliptic curves over finite fields: a basic introduction. Connexions with cryptography and error correcting codes.

     References:

     • 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
  1. Pierre Arnoux (Luminy) Primality Testing and Factoring Algorithms
     Syllabus:

     1. Introduction: prime numbers and factorization. Elementary results; the sieve of Eratosthenes. Practical importance of primality testing and factoring algorithms.
     2. 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.
     3. 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

     Syllabus: 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.
     
     
     

     Florian Luca (UNAM Morelia) Smooth numbers and their applications

     Syllabus:

     1. Introduction to the theory of smooth numbers. Definitions, examples, counting very smooth numbers via estimating the number of lattice points inside certain polytopes.
     2. The Dickman ρ-function. The Buchstab identity, the Dickman ρ-function and its properties, counting not so smooth numbers.
     3. Estimates valid in larger ranges. The de Bruijn estimate and the Erdős, Canfield and Pomerance estimate.
     4. Number Theoretic Applications. Applications to counting pseudoprimes, Carmichael numbers and to factoring algorithms.

     
     
     
     

     Christian Mauduit (Luminy) Pseudorandom Sequences and Cryptography

     Syllabus:

     1. Stream ciphers and cryptography.
     2. What is a pseudorandom sequences ?
     3. Measures of pseudorandomness.
     4. Applications of number theory to the construction of pseudorandom sequences.

     References:

     • D. Knuth, The art of computer programming, vol. 2.
     • A. Menezes, P. van Oorschot and S. Vanstone, Handbook of applied cryptography.

     
     
     
     

     Francesco Pappalardi (Roma Tre) Elliptic Curves in Cryptography

     Syllabus:

     1. INTRODUCTION: Weierstrass Equations, The Group Law, The j-Invariant, Elliptic Curves in Characteristic 2, Endomorphisms, Singular Curves, Elliptic Curves mod n
     2. TORSION POINTS: Division Polynomials, The Weil Pairing.
     3. Elliptic Curves over Finite Fields: The Frobenius Endomorphism, Determining the Group Order, Schoof's Algorithm Supersingular Curves
     4. The Discrete Logarithm Problem: The Index Calculus, Attacks with Pairings
     5. 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
     6. Other Applications: Factoring Using Elliptic Curves, Primality Testing

     References:

     • 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

     Syllabus:TBA
     
     
     

     R.P. Pant (Kumaon University) Number Theory and fixed point

     Syllabus:TBA
     
     
     

TENTATIVE SCHEDULE:

REGISTRATION AND FINANCIAL SUPPORT: