logo IMB
Retour

Séminaire de Théorie Algorithmique des Nombres

Nonlinear polynomial selection for the number field sieve: improving Montgomery's method

Cyril Bouvier

( imb )

Salle 385

le 01 mars 2016 à 11:00

The number field sieve is the most efficient known algorithm for factoring large integers that are free of small prime factors. The goal of the polynomial selection, the first stage of this algorithm, is to compute a pair of integer polynomials. Montgomery proposed a method for generating two nonlinear polynomials which relies on the construction of small modular geometric progressions. In this talk, I will present theoretical and practical improvements to Montgomery's method that allow us to generate pairs of a quadratic and a cubic polynomials and pairs of two cubic polynomials for larger integer that was previously possible. Joint work with Nicholas Coxon.