Polynomial selection for the number field sieve
Shi Bai ( Phd candidate)
COMPUTER SCIENCE SEMINAR Algorithm and Data group seminarDATE: 2011-10-14
TIME: 14:00:00 - 15:00:00
LOCATION: CSIT Seminar Room, N101
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
The number field sieve is asymptotically the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The running time of subsequent stages depends on the quality of the chosen polynomials in polynomial selection.
Polynomial selection can be divided into three steps: polynomial
generation, size optimization and root optimization. In this seminar,
we will give some analysis of the polynomial generation algorithms. We
will also describe some improved methods for size optimization and
root optimization. These methods have been implemented and used to
obtain some good polynomials in practice.
BIO:
Shi is a third-year PhD student under the supervision of Prof. Richard Brent in the Algorithms & Data group at College of Engineering & Computer Science of ANU. I am interested in computational number theory and cryptography. Recently, I am working on the polynomial selection algorithms for the number field sieve.
