PhD Thesis:
Algorithms for integer factorization and discrete logarithms computation
Granted by l'Université de Lorraine.
Thesis director: Paul Zimmermann.
Abstract:
In this thesis, we study the problems of integer factorization and
discrete logarithm computation in finite fields. First, we study the ECM
algorithm for integer factorization and present a method to analyze the
elliptic curves used in this algorithm by studying the Galois properties
of division polynomials. Then, we present in detail the NFS algorithm for
integer factorization and we study in particular the polynomial selection
step for which we propose improvements of existing algorithms. Next, we
present two algorithms for computing discrete logarithms in finite fields:
NFS-DL and FFS. We also give some details of two computations of discrete
logarithms carried out during this thesis, one with NFS-DL and the other
with FFS. Finally, we study a common step of the NFS algorithm for integer
factorization and the NFS-DL and FFS algorithms for discrete logarithm
computations: the filtering step. We study this step thoroughly and
present an improvement for which we study the impact using data from
several computations of discrete logarithms and factorizations.
Manuscript: [
For screen
|
For printing (color)
|
For printing (black and white)
]
Defense presentation:
[ pdf ]