On Prime Factorization Algorithms and Their Comparisons

Abstract

Bilgisayarların evler ve işletmelerde yaygınlaşması ve internetin hızla büyümesiyle birlikte, güvenli elektronik iletişim önemli bir konu haline gelmiştir. Elektronik bilgiyi korumak için en çok kullanılan açık anahtarlı sistemlerden biri olan RSA, (Rivest,1978) büyük bir tam sayının asal çarpanlarına ayrılmasının hesaplama açısından zor olduğu gerçeğine dayanır. Eğer uygun (polinom zamanlı bir algoritma bulunabilirse) bir süre içinde herhangi büyük bir tam sayıyı asal çarpanlarına ayırabilen etkili bir algoritma geliştirilirse, RSA kripto sistemi kırılır. Bu tezde Fermat çarpanlara ayırma algoritması, Euler çarpanlara ayırma algoritması, Quadratik Sieve çarpanlara ayırma algoritması, Pollard rho çarpanlara ayırma algoritması, Pollard çarpanlara ayırma algoritması ve sürekli kesirler gibi verilen bir sayının asal olmadığını kabul edilerek asal çarpanlarına ayırma metotları detaylı bir şekilde incelenecek ilgili teoremler ispatlarıyla verilecek bu metotlar birbirileriyle kıyaslanarak örneklendirilecektir.

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.