Computing Factor Tables, and Tables of Class Numbers

1 June 2016
Roger Heath-Brown

Efficient factorization or efficient computation of class 
numbers would both suffice to break RSA.  However the talk lies more in 
computational number theory rather than in cryptography proper. We will 
address two questions: (1) How quickly can one construct a factor table 
for the numbers up to x?, and (2) How quickly can one do the same for the 
class numbers (of imaginary quadratic fields)? Somewhat surprisingly, the 
approach we describe for the second problem is motivated by the classical 
Hardy-Littlewood method.

  • Cryptography Seminar