17th Estonian Winter School in Computer Science (EWSCS)
XVII Eesti Arvutiteaduse Talvekool

Palmse, Estonia, February 26 -March 2, 2012

Vassil S. Dimitrov

Dept. of Electrical and Computer Engineering
University of Calgary

Computational number theory and its applications


The use of computational number-theoretic techniques is well known in the domain of cryptography. Most of the currently used public key cryptographic systems are based on some classical results in number theory. There are new and challenging areas like pairing- based cryptographic protocols that use some very essential facts from algebraic geometry. In my course I shall try to showcase some applications in the areas outside cryptography, like digital signal processing, digital communications, image compression, etc. Most of the students studying computer science are not aware of some of these applications, which is unfortunate. My point will be to bridge the gap between the computer scientists and computer engineers.

The material is segmented into four lectures briefly like this:

  1. Basic facts from theory of computer arithmetic. Another look at some fundamental computational problems. Provable lower bounds. Known upper bounds. Open problems.
  2. Applications in digital signal processing (DSP). The role of multiplicative complexity theory in DSP applications. Fourier transform over finite fields.
  3. Speeding up cryptographic algorithms. Faster implementation of cryptographic primitives based on various number-theoretic techniques.
  4. Discussions on open problems. Purely computational number theory open problems (like solving specific Diophantine equations, Diophantine approximations, etc.). Discussions on open problems with substantial practical impact. Conclusions.

Books that will be used:

Course materials

Valid CSS! Valid XHTML 1.0 Strict Last changed March 6, 2012 0:23 EET by local organizers, ewscs12(at)cs.ioc.ee
EWSCS'12 page: http://cs.ioc.ee/ewscs/2012/