On prime factorization algorithms and their comparisons

With the widespread adoption of computers in homes and businesses, along with the rapid growth of the internet, secure electronic communication has become a critical concern. One of the most commonly used public-key systems for safeguarding electronic information is RSA, (Rivest,1978) which is based on the computational difficulty of factoring a large composite number into its prime factors. If an efficient algorithm (a polynomial-time algorithm) capable of factoring any large integer into its prime factors in a reasonable amount of time were to be developed, the security of the RSA system would be broken. In this thesis, various methods for factoring composite numbers will be extensively examined, assuming that a given number is not prime, and these methods will be presented with detailed explanations of the relevant theorems. Methods such as the Fermat factorization algorithm, the Euler factorization algorithm, the Quadratic Sieve factorization algorithm, the Pollard rho factorization algorithm, and the Pollard p-1 factorization algorithm and the continued fractions factorization algorithm will be discussed by giving concrete examples.