Asal çarpanlara ayırma

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

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.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.

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.

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.