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

Vassil S. Dimitrov

Dept. of Electrical and Computer Engineering
University of Calgary
Canada

Computational number theory and its applications

Abstract

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:

• D. Knuth. The Art of Computer Programming, v. 2: Seminumerical Algorithms, 3rd ed. Addison-Wesley, 1997. (1st ed., 1969; 2nd ed., 1981.)
• H. S. Wilf. Algorithms and Complexity, 2nd ed. A. K. Peters, 2002.
• R. Brent, P. Zimmerman. Modern Computer Arithmetic, Cambridge Monographs on Applied and Computational Mathematics. Cambridge Univ. Press, 2011.
• V. S. Dimitrov, G. Jullien, R. Muscedere. Multiple-Base Number System: Theory and Applications, Circuits and Electrical Engineering. CRC Press, 2012.

Course materials

• V. S. Dimitrov. Loading the bases. Slides. [pdf]
• V. S. Dimitrov, K. Järvinen, M. J. Jacobson, Jr., W. F. Chan, Z. Huang. FPGA implementation of point multiplication on Koblitz curves using Kleinian integers. Slides. [pdf]
• V. S. Dimitrov, K. Järvinen. Another look at inversions over binary fields. Slides. [pdf]
• H. S. Wilf. Algorithms and Complexity, internet ed., 1994. [copy on the author's webpage] (Check esp. chs. 4-5.)
• V. S. Dimitrov. Number theory and its applications in digital signal processing and cryptography (course notes). Report 27, Lab. of Signal Processing and Computer Technology. Helsinki Univ. of Technology, 1999.
• V. S. Dimitrov. Computer arithmetic and computational complexity (course notes). Univ. of Calgary, 2012.

Last changed March 6, 2012 0:23 EET by local organizers, ewscs12(at)cs.ioc.ee
EWSCS'12 page: //cs.ioc.ee/ewscs/2012/