Παραγοντοποίση Ακεραίων

Abstract

This chapter is devoted to one of the most important topics of the Computational Number Theory which is the integer factorization. We shall describe the methods of Fermat, Legendre, Dixon, Continuous Fractions and the algorithms p-1 and ρ of Pollard. Note that polynomial time algorithm for the integer factorization is not invented yet. The most effective integer factorization algorithms are the Number Field Sieve and the method of Elliptic Curves but the development of the necessary mathematical tools for their presentation is not in the aims of this book.

Το κεφάλαιο αυτό είναι αφιερωμένο σε ένα από τα πλέον σημαντικά θέματα της Υπολογιστικης Θεωρίας Αριθμών που είναι η παραγοντοποίηση ακεραίων. Θα περιγράψουμε τις μεθόδους παραγοντοποίησης των Fermat, Legendre, Dixon, <br/>των συνεχών κλασμάτων και τους αλγόριθμους p-1 και ρ του Pollard. Ας σημειωθεί ότι αλγόριθμος πολυωνυμικού χρόνου για την παραγοντοποίηση ενός ακεραίου δεν έχει ακόμη ανακαλυφθεί. Οι πλέον αποτελεσματικοί αλγόριθμοι παραγοντοποίησης σήμερα είναι το κόσκινο των σωμάτων αλγεβρικών αριθμών και η μέθοδος των ελλειπτικών καμπυλών των οποίων όμως η περιγραφή εκφεύγει από το πλαίσιο του παρόντος συγγράμματος.