The principal aim of this notes is to give a survey on the state of the art of algorithmic number theory, with particular focus on the theory of elliptic curves.
Computational security is the goal of modern cryptographic constructions: the security of modern criptographic schemes stems from the assumption that an adversary is not able to efficiently solve certain mathematical problems. That is to say, those schemes can be broken given enough time and computational power, but they can be considered practically unbreakable. Here we review the most common mathematical problems underlying modern cryptosystems and study the computational complexity related to the best known algorithms known to break them.
The structure of the document is as follows. In the first part (chapters 1-4) we study the basic mathematical tools needed to deal with the above problems. The second part shows how to use what we have learned in the first part to solve three foundamental tasks, namely primality proving, integer factoring and discrete logarithms evaluation. The last chapter deals with two explicit constructions of pairings using elliptic curves.