Chennai Mathematical Institute


11:45 am, Lecture Hall 1
Rigorous Analysis of a randomized number field Sieve

Jonathan D Lee (Dept of Mathematics, Oxford, UK),
Ramarathnam Venkatesan (Microsoft Research, Bangalore and Redmond)

Ramarathnam Venkatesan
Microsoft, Seattle.


Factorisation of semi-primes} $n$ is of cryptographic significance. The Number Field Sieve (NFS) is the state of the art algorithm, but no rigorous proof that it halts or even generates relationships is known. We analyse a novel explicitly randomised variant. For each $n$, we bound the expected time taken to form a congruence of squares above by $\exp((c+\o(1)) \log^{1/3}n \log \log^{2/3} n)$, with $c = 2.77$ unconditionally. On the GRH we prove an upper bound of the same form with $c = \sqrt[3]{\frac{64}{9}}$, matching the heuristic guestimates. Our analysis uses and extends equi-distribution and Bombieri-Vinagradov results on smooth numbers by by Soundarajan, and A. Harper. I will survey the results needed, and show how they fit in the analysis