Στην παρούσα Διπλωματική Εργασία θα ασχοληθούμε με το πασίγνωστο πρόβλημα της Παραγοντοποίησης Ακεραίων. Η προσέγγιση μας είναι από τη μεριά της Επιστήμης των Υπολογιστών και της Υπολογιστικής Πολυπλοκότητας. Προσπαθούμε να κατανοήσουμε γιατί η Παραγοντοποίηση Ακεραίων θεωρείται ένα υπολογιστικά δύσκολο πρόβλημα και να δούμε τις πρακτικές εφαρμογές και συνέπειες αυτής της θεώρησης. / In the present Diploma Thesis we are going to deal with the very well known problem of Integer-Factoring. Our approach is from the side of Computer Science and Computational Complexity. We are trying to understand why Integer-Factoring is widely considered as a hard problem to solve and see the practical applications of this consideration.

[pt] A dissertação apresenta detalhadamente o algoritmo de fatoração de Shor, tanto em termos de sua execução passo a passo como mediante sua representação em forma de circuito, abordando aspectos tanto de sua parte clássica como de sua parte quântica. Inicialmente são apresentados aspectos de teoria dos números indispensáveis para a compreensão do algoritmo e em seguida são desenvolvidos conceitos e propriedades de mecânica quântica e de informação quântica pertinentes. Em atenção ao caráter eminentemente estocástico do algoritmo realiza-se um estudo de sua fonte estocástica e demonstram-se os principais teoremas que embasam a avaliação de sua probabilidade de sucesso. Desenvolvem-se exemplos de simulação clássica do algoritmo. Finalmente, a eficiência do algoritmo de fatoração de Shor é comparada com a de algoritmos clássicos. / [en] The dissertation presents in detail Shor s factoring algorithm, including its execution step by step and its representation in the form of a circuit, addressing aspects of both its classical and its quantum parts. Aspects of number theory indispensable to understand the algorithm are presented, followed by a development of concepts and properties of quantum mechanics and quantum information. Considering the eminently stochastic character of the algorithm, a study of its stochastic source is carried out and the main theorems that support the evaluation of its probability of success are proved. Examples of classical simulation of the algorithm are developed. Finally, the efficiency of Shor s factoring algorithm is compared with that of classical algorithms.