Asal çarpanlara ayırma

[bullvar_katip]

Sayı teorisinde, asal çarpanlara ayırma bir bileşik sayının, çarpıldıklarında yine aynı sayıyı verecek şekilde, bir ve kendisi dışındaki bölenlerine ayrılmasıdır. Sayılar çok büyük olduğunda, kuantum olmayan hızlı bir algoritma bilinmemektedir. 2009 yılında sonuçlanan bir çalışmada bir grup araştırmacı 232 basamaklı bir sayıyı (RSA-768), yüzlerce makineyi iki yıl boyunca çalıştırarak çarpanlarına ayırmışlardır. Bu problemin varsayılan zorluğu, kriptografi alanında sıkça kullanılan RSA gibi algoritmaların tasarımında çok önemli bir yere sahiptir. Bu problem, eliptik eğriler, cebirsel sayı kuramı ve kuantum hesaplama gibi matematik ve bilgisayar biliminin birçok alanında önem arz etmektedir. Belli uzunluktaki her sayının çarpanlara ayrılma zorluğu aynı değildir. Çarpanlara ayrılması en zor sayılar (halihazırda bilinen teknikler ışığında) yarıasallar, yani iki asal sayının çarpımı şeklinde yazılabilen sayılardır. Bu sayılardan ikisi de büyük, mesela 2000 bit uzunluğunda ve rastgele, birbirleriyle yakın uzunlukta (fakat çok yakın değil, çünkü böyle sayılar için Fermat'ın çarpanlara ayırma metodu kullanılabilir) olacak şekilde seçildiği takdirde, en hızlı çarpanlara ayırma algoritmaları en hızlı bilgisayarlarda dahi çalışsa pratikte kullanılabilecek bir hızda çözüme ulaşamamaktadır. Çarpanlara ayrılacak sayının asal çarpanlarının bit uzunlukları arttıkça algoritmanın çalışma süresi şiddetli biçimde artmaktadır. RSA gibi çok sayıda kriptografik protokol bu problemin veya bir benzerinin zorluğuna dayanmaktadır. Bir başka deyişle eğer bir sayıyı hızlı bir şekilde çarpanlara ayırma algoritması bulunsaydı, RSA tabanlı açık anahtar kriptografisi güvenliğini yitirirdi. Asallara ayırma sağ|küçükresim|upright=0.86|864 sayısının asal çarpanlarına ayrılması. Asal çarpanları yazmanın kısa bir yolu: Aritmetiğin temel teoremi gereğince, her pozitif tam sayı asal çarpanlarına tek bir biçimde ayrılır (1 için özel bir duruma gerek yoktur, boş çarpım tanımının olması yeterlidir). Fakat,aritmetiğin temel teoremi bu çarpanların nasıl bulunacağı konusunda bir şey söylemez; sadece var olduklarını söyler. Genel bir çarpanlara ayırma algoritması verildiğinde, bu algoritmayı tekrar tekrar uygulamak suretiyle herhangi bir tam sayı asal çarpanlarına kadar ayrılabilir. Fakat özel bir amaca yönelik bir çarpanlara ayırma algoritması için bu söz konusu değildir çünkü bu özel algoritma daha ayrıştırmanın sonraki adımlarındaki daha küçük çarpanlara ayırma problemlerinde işe yaramayabilir veya çok yavaş çalışabilir. Mesela deneme bölmesi N = 2 × (2 − 1) × (2 − 1) için 10N sayısını hızlı bir biçimde 2 × 5 × N olarak çarpanlara ayırır ama N sayısını hızlı bir biçimde çarpanlarına ayıramaz. En son gelişmeler Çarpanlarına ayrılması en zor tam sayılar birbirine yakın uzunluktaki iki büyük asal sayının çarpımı şeklinde olanlar, bir başka deyişle yarıasallardır. Tam da bu yüzden kriptografide bu sayılar kullanılmaktadır. Halihazırda çarpanlarına ayrılmış en büyük yarıasal 232 basamaklı, 768-bitlik bir sayıdır. (12 Aralık 2009) Çeşitli araştırma enstitülerinin ortak çalışmasıyla yapılan bu işlem, iki yıl sürmüş ve tek çekirdekli bir 2.2GHz AMD Opteron bilgisayarın 2000 yıl çalışmasına denk bir işlem gücüne mal olmuştur. Diğer tüm çarpanlara ayırma rekorları gibi bu rekor da genel sayı cismi eleme (GNFS) algoritmasının son derece optimize bir şekilde yüzlerce makine üzerinde çalıştırılmasıyla tamamlanabilmiştir. Zorluk ve karmaşıklık Eğer b bitlik büyük bir sayı yaklaşık aynı uzunlukta iki asal sayının çarpımı ise, yayınlanmış hiçbir algoritma bu sayıyı polinomsal zamanda (yani belli bir k değeri için Yani O(b) zamanda) çarpanlarına ayıramamaktadır. Tüm pozitif ε değerleri için O((1+ε))'den daha hızlı yani üstel-altı zaman algoritmalarsa yayınlamış bulunmaktadır. GNFS algoritmasıyla "b"-bitlik bir yarıasalın çarpanlarına ayrılması için yayınlanmış olan en iyi asimptotik çalışma zamanı, tür. Sıradan bir bilgisayar için, GNFS 100 basamaktan daha büyük sayılarda çalışmak üzere yayınlanmış en iyi algoritmadır. Fakat bir kuantum bilgisayarı için, Peter Shor 1994 yılında polinomsal zamanda çözüme ulaşan bir algoritma keşfetmiştir. Eğer gelecekte büyük bir kuantum bilgisayarı inşa edilebilirse bu keşif kriptografi açısından önemli sonuçlar doğuracaktır. Shor algoritması "b"-bitlik bir girdi için sadece O(b) zaman ve O(b) yer gerektirmektedir. 2001 yılında, 7-kübitlik bir kuantum bilgisayar ilk kez Shor'un algoritmasını çalıştırmış ve 15'i çarpanlarına ayırmıştır. Çarpanlara ayırma probleminin hangi karmaşıklık sınıfına dahil olduğu incelenirken problemin değişik versiyonlarını ayırt etmek gerekir. Fonksiyon problemi versiyonu: Bir N tam sayısı verildiğinde 1 olarak da bilinen genel çarpanlara ayırma algoritmalarının çalışma süreleri sadece çarpanlarına ayrılacak olan sayının büyüklüğüne bağlıdır. RSA sayılarını çarpanlarına ayırmak için bu algoritmalar kullanılır. Genel çarpanlara ayırma algoritmalarının çoğu kareler çakışması metoduna dayalıdır. Dixon algoritması Tekrarlı bölme çarpanlara ayırma metodu (CFRAC) İkinci derece elek metodu Genel sayı cismi eleme metodu Shank'in kare formları çarpanlara ayırma metodu (SQUFOF) Diğer kayda değer algoritmalar Kuantum bilgisayarları için Shor algoritması Sezgisel çalışma süresi Sayılar teorisinde beklenen çalışma süresi sezgisel olarak, O ve L notasyonu ile ifade edilecek olursa, olan birçok çarpanlara ayırma algoritması vardır. Bu algoritmalara bazı örnekler eliptik eğri metodu ve ikinci dereceden elek metodudur. Bu şekilde bir diğer algoritma da Schnorr tarafından önerilen sınıf grup ilişkileri metodudur. Bu durum Seysen ve Lenstra tarafından genelleştirilmiş Riemann hipotezi (GRH) ışığında ispatlanmıştır. Kesin çalışma süresi Schnorr-Seysen-Lenstra olasılıksal algoritmasının beklenen çalışma süresinin olduğu, Lenstra ve Pomerance tarafından GRH varsayımı yerine çarpanlar kullanılmak suretiyle kesin bir şekilde ispatlanmıştır. Algoritma, G ile gösterilen diskriminant Δ'nın pozitif ikili ikinci dereceden fom sınıf grubunu kullanır. G (a, b, c) gibi aralarında asal tam sayı üçlülerinin kümesidir. Schnorr-Seysen-Lenstra algoritması Algoritmanın girdisi, belirli sabit bir değerden büyük, pozitif ve tek bir "n" tam sayısıdır. Bu çarpanlara ayırma algoritmasında, diskriminant Δ, "d" bir pozitif çarpan olmak kaydıyla, Δ= -dn şeklinde "n"'nin bir tam katı olarak seçilir. Algoritma, Gda bir "d" değeri için yeterli düzgün formlarının olduğunu umar. Lenstra ve Pomerance söz konusu "d"'nin seçiminin belirli küçük bir kümeyle sınırlanarak düzgünlüğün garanti edilebileceğini göstermişlerdir. P ile Kronecker sembolü olan tüm q asal sayılarının kümesini gösterelim. "q" Pda olmak üzere Gnın bir üreteç ve asal form f kümelerini oluşturmak kaydıyla, üreteçler ve f arasında bir bağıntı dizisi üretilir. "q"'nun büyüklüğü bir değeri için ile sınırlandırılabilir. Kullanılacak olan bağıntı, Gnın tarafsız elemanına eşit olan üsler çarpımı arasındaki bir bağıntıdır. Bu bağıntılar,, aslında Gnın kertesi 2'yi bölen bir elemanı olan, Gnın çokanlamlı bir formunu inşa etmek için kullanılacaktır. Δ'nın ilişkin çarpanlara ayrımını hesaplayarak ve bir EBOB alarak, bu çokanlamlı form "n"'nin tam bir asal çarpanlara ayrımlanmasını verir. Bu algoritmanın ana basamakları şunlardır: Çarpanlarına ayrılacak sayı "n" olsun. d bir çarpan ve Δ bir ikinci dereceden formun negatif diskriminantı olmak koşuluyla, Δ, -dn şeklinde negatif bir tam sayı olsun. Bir için, ilk t asal sayıyı alalım. olmak üzere, , Gnın rassal bir asal formu olsun. Gnın bir X üretici kümesini bul. "X" kümesi ve {f : q ∈ P} arasında şunu sağlayan bir bağıntı dizisi topla: Δ = -4a.c or a(a - 4c) or (b - 2a).(b + 2a) olmak kaydıyla Δ'nın en büyük tek böleninin aralarında asal çarpanlarına ayrımını elde etmek için, derecesi 2'yi bölen bir f ∈ G elamanı olan bir "(a, b, c)" çokanlamlı formu oluştur. Eğer çokanlamlı form "n"'nin bir çarpanlara ayrımını verirse dur, aksi takdirde "n"'nin bir çarpanlara ayrımı bulunana dek başka bir çokanlamlı form bul. Kullanışsız çokanlamlı formların üretimini en baştan engellemek için G(Δ)'nın S(Δ) grubunu inşa et. Herhangi bir pozitif tam sayıyı çarpanlarına ayıran bir algoritma elde edebilmek için bu algoritmaya deneme bölmesi, Jacobi toplamı testi gibi birkaç basamak daha eklemek gerekmektedir. Beklenen çalışma süresi Verildiği şekliyle algoritma rassal seçimler yapması dolayısıyla olasılıksal bir algoritmadır. Beklenen çalışma süresi en çok 'dir. Ayrıca bakınız Bir pozitif tam sayının kanonik gösterimi Kaynakça Konuyla ilgili yayınlar Chapter 5: Exponential Factoring Algorithms, pp.191–226. Chapter 6: Subexponential Factoring Algorithms, pp.227–284. Section 7.4: Elliptic curve method, pp.301–313. Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.4: Factoring into Primes, pp.379–417. Dış bağlantılar Paolo Ardoino, üç algoritma ve C kaynak kodları. asal çarpanlara ayırma : Paul Herman & Ami Fischman, Pollard Rho & Shor da dahil birçok asal çarpanlara ayırma algrotiması için C++ kaynak kodları. Çarpanlara ayırma Kategori:Çözülememiş bilgisayar bilimi problemleri