A research on the variations of the quadratic sieve integer factoring algorithm

Abstract

Tamsayıları asal çarpanlarına ayırmak için polinom zamanlı bir algoritma henüz bulunamamıştır. RSA şifreleme sisteminin güvenliği bir tamsayıyı asal çarpanlarına ayırmanın zorluğuna dayanır. RSA'nın bulunmasıyla birlikte tamsayıları çarpanlarına ayırma probleminin önemi daha da artmıştır. Bu problemin çözümünde şu ana kadar geliştirilen algoritmaların en önemlilerinden birisi ?Kuadratik Elek? metodudur.Bu tez Kuadratik Elek metodu ve varyasyonları üzerine bir çalışmadır. Öncelikle yukarıdaki problemin çözümünde kullanılan bazı temel algoritmalar ve teknikler verilecektir. Maple uygulamalarıyla birlikte, Kuadratik Elek metodu ve varyasyonları detaylı bir şekilde incelenecektir.

No polynomial time solutions for the integer factorization problem (IFP) have yet been found. The security of RSA cryptosystem is based on the difficulty of the above problem. With the advent of RSA, the IFP has gained a great deal more practical importance. One of the important methods that has been developed so far is the Quadratic Sieve Method (QS).The work presented here addresses the quadratic sieve integer factorization algorithm and its variations. We will begin with some elementary factorization algorithms and techniques. And then, the quadratic sieve and its variations will be presented together with some Maple implementations.