A New Ranking Function for Polynomial Selection in the Number Field Sieve

Nicolas David (1) , Paul Zimmermann (2)

1 ENS Cachan - École normale supérieure - Cachan
2 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms

This article explains why the classical Murphy-E ranking function might fail to correctly rank polynomial pairs in the Number Field Sieve, and proposes a new ranking function.

Domaines: Algorithme et structure de données [cs.DS]

Nicolas David, Paul Zimmermann. A New Ranking Function for Polynomial Selection in the Number Field Sieve. Contemporary mathematics, 2020, 75 Years of Mathematics of Computation, 754, pp.315-325. ⟨10.1090/CONM/754/15139⟩. ⟨hal-02151093v4⟩