11:30 am, Lecture Hall 5
On Rigorous Analysis of Factoring Algorithms
Ramarathman Venkatesan
Microsoft Research.
25-07-14

---

Abstract

In designing a crypto-system one uses the best benchmark attack algorithms and chooses the parameters; then one closes one's eyes and fervently hopes that, as indicated by the best known estimates, it would take centuries to crack the system.

For public key crypto-system such as RSA, the index calculus algorithms have remained the standard for decades. We look at the formal analysis of their runtime. The situation is less than perfect: the best among them for factoring is called Number Field Sieve, for which is not clear how to show termination. We provide run time bounds matching the heuristic estimates: for NFS the results are unconditional. For Quadratic Sieve, we motivate a Fourier Concentration Conjecture and a Random Matrix Rank Conjecture and establish the run times.

I will introduce the basics and survey the results.

With Jonathan D Lee, Trinity College, Mathematics Department, Cambridge UK.