EXPONENTIAL SUMS IN CODING THEORY, CRYPTOLOGY AND ALGORITHMS
The following sections are included:
Introduction
Exponential Sums — Basic Notions
Getting started
Exponential sums — What are they?
Exponential sums — What do we want from them?
Exponential sums — How do we classify them?
Timeline
Johann Carl Friedrich Gauss, 1801
Hermann Klaus Hugo Weyl, 1916
Godfrey Harold Hardy and John Edensor Littlewood, 1920
Louis Joel Mordell, 1932
Ivan Matveevich Vinogradov, 1935
Loo-Keng Hua, 1940
André Weil, 1948
Pierre Deligne, 1914
You, ????
Some terminology
Rational exponential sums
Complete and incomplete exponential sums
Simplest Bounds and Applications
The basic case — Linear sums
Nice result almost for free
Gaussian sums
Linear sums once again
Distribution of functions modulo p
More Sophisticated Methods
Extend and conquer
Clone, extend and conquer
Mordell's bound
Shorter sums … but large bound
Some Strongest Known Results
Weil's kingdom
Exponential functions
More applications
What else can we estimate?
Twin Brothers of Exponential Sums — Character Sums
Definitions
Polya—Vinogradov bound again
Let's push it down!—Other methods are helpful as well
Applications to Coding Theory
Direct applications
Less obvious applications: Dimension of BCH codes
Definitions
Preparations
Main result
Discussion: Some lessons to learn
Applications to Cryptography
Distribution of some cryptographic primitives
Security of exponentiation with precomputation
Diffie-Hellman triples and RSA pairs
Lattices and exponential sums
Introduction and notation
Hidden number problem and lattices
Extended hidden number problem, lattices and exponential sums
Bit security of the Diffie-Hellman secret key
Attack on the digital signature algorithm
Other applications and open questions
Applications to Algorithms
Primitive roots
Pseudorandom regular graphs
Polynomial factorisation
Complexity lower bounds
Tutorial Problems
References
