Asal çarpanlara ayırma

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.

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 × (2521 − 1) × (2607 − 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.

Ç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.2 GHz 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.

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(b3) 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.

Fonksiyon problemi versiyonu: Bir N tam sayısı verildiğinde 1 < d < N olacak şekilde N'yi bölen bir d sayısı bulunuz (veya N'nin asal olduğu sonucuna varınız). Bu problem FNP'de olup FP'de olup olmadığıysa bilinmemektedir. Pratikte uygulamalarda çözülen versiyon, bu versiyondur.

Karar problemi versiyonu: 1 ≤ M ≤ N olacak şekilde M ve N tam sayıları verildiğinde, 1 < d < M olacak şekilde öyle bir d sayısı var mıdır ki N'yi bölüyor olsun? Bu versiyon kullanışlıdır çünkü çokça çalışılmış tüm karmaşıklık sınıfları fonksiyon değil karar problemleri üzerinden tanımlanmıştır. Bu, problemin optimizasyon problemleri için sıkça kullanılanlara denk gelen doğal bir karar versiyonudur, çünkü bu versiyon ikisel arama ile birleştirilerek fonksiyon versiyonu da logaritmik sayıda sorgu ile çözülebilir. Çarpanlara ayırma probleminin karar versiyonunun tam olarak hangi karmaşıklık sınıfında yer aldığı bilinmemektedir. Ne var ki hem NP hem de co-NP'de olduğu bilinmektedir. Çünkü asal çarpanlar verildiğinde hem EVET hem de HAYIR cevapları teyit edilebilir. (Çarpanların asallığı AKS asallık testi ile, çarpımlarının N olduğunu da basitçe çarparak kontrol edilebilir.) Aritmetiğin temel teoremince sadece bir çözümün kabul edilebileceği kesindir (sıralı olmaları koşuluyla). Bu da gösterir ki problem hem UP hem de co-UP sınıflarındadır. Problemin BQP'de olduğu Shor algoritması dolayısıyla bilinmektedir. P, NP-complete, ve co-NP-complete karmaşıklık sınıflarının üçünde de olmadığı sanılmaktadır. Dolayısıyla NP-intermediate karmaşıklık sınıfında olmaya adaydır. NP-Complete veya co-NP-Complete olduğu gösterildiği takdirde, NP = co-NP olması gerekecektir. Oysa bu son derece beklenmedik bir netice olacağı için çarpanlara ayırma probleminin bu iki sınıfta da olmadığı düşünülmektedir. Çok sayıda insan klasik polinomsal-zaman algoritmalar bulmayı deneyip başaramadıklarından yaygın kanı P sınıfının dışında olduğu yönündedir.

Bunlara karşın ""N" bileşik sayı mıdır?" (veya buna denk olarak ""N" asal sayı mıdır?") karar problemleri "N"'nin çarpanlarını bulmaya nazaran çok daha kolay görünmektedir. Bu karar problemlerinden ilki AKS asallık testi ile N'nin basamak uzunluğu cinsinden polinomsal zamanda çözülebilmektedir. Bununla beraber, çok küçük bir hata payına razı olmak koşuluyla çok hızlı sonuç verebilen çeşitli olasılıksal algoritmalar bulunmaktadır. Asallık testinin kolay oluşu, başlangıcında büyük asal sayılar bulma gerekliliğinden dolayı RSA algoritması için büyük önem arz etmektedir.

Amaca özel bir çarpanlara ayırma algoritmasının çalışma zamanı, çarpanlara ayrılmaya çalışan sayının veya bilinmeyen çarpanlarından birinin özelliklerine bağlıdır: büyüklük, özel form, vs. Tam olarak çalışma süresinin ne olduğuysa algoritmadan algoritmaya değişir.

Amaca özel algoritmaların önemli bir alt sınıfı "1. Kategori" olarak adlandırılan algoritmalardır ki bunların çalışma süreleri en küçük asal çarpanın büyüklüğüne bağlıdır. Formu bilinmeyen bir tam sayı verildiğinde küçük çarpanları ayıklamak için genellikle bu algoritmalar genel algoritmalardan önce çalıştırılır.

Aynı zamanda 2. kategori veya kaşifi Maurice Kraitchik'e atfen Kraitchik ailesi algoritmalar 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.

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.

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.

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, GΔ'da 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" PΔ'da olmak üzere GΔ'nın bir üreteç ve asal form fq kümelerini oluşturmak kaydıyla, üreteçler ve fq arasında bir bağıntı dizisi üretilir. "q"'nun büyüklüğü bir değeri için ile sınırlandırılabilir.

d bir çarpan ve Δ bir ikinci dereceden formun negatif diskriminantı olmak koşuluyla, Δ, -dn şeklinde negatif bir tam sayı olsun.

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 S2(Δ) 2-Sylow 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.