Türkçe Bilgi: Asal çarpanlara ayırma

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 makinayı 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 tamsayı 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 tamsayı 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 tamsayı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) Ç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 tamsayı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 tamsayı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. ==Çarpanlara ayırmaAmaca özel

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 tamsayı verildiğinde küçük çarpanları ayıklamak için genellikle bu algoritmalar genel algoritmalardan önce çalıştırılır. * Deneme bölmesi * Tekerlek çarpanlara ayırma yöntemi * Pollard'ın rho algoritması * Cebirsel-grup çarpanlara ayırma algoritmaları: Pollard'ın p - 1 algoritması, Williams'ın p + 1 algoritması ve Lenstra eliptik eğri çarpanlara ayırma yöntemi * Fermat'ın çarpanlara ayırma metodu * Euler'in çarpanlara ayırma metodu * Özel sayı cismi eleme yöntemi

Genel amaçlı

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

L_n\left [1]

olduğu, Lenstra ve Pomerance ==Ayrıca bakınız== * Bir pozitif tam sayının kanonik gösterimi ==Kaynakça== ==Ek okumalar== * 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ı.

Kaynaklar

Vikipedi

Asal Çarpanlara Ayırma

Amaca özel

Amaca özel

Genel amaçlı

Dış bağlantılar

Kaynaklar

çarpanlara ayırma

Asal Sayı

Bell sayısı

Adi Shamir

Ayrık Logaritma

Jacobi sembolü

Gottfried Leibniz

Asal Çarpanlara Ayırma

Asal Çarpanlara Ayırma Hakkında Detaylı Bilgi

Amaca özel

Amaca özel

Genel amaçlı

Dış bağlantılar

Kaynaklar

Görüşler ve Yorumlar

Okuma Önerileri

çarpanlara ayırma

Asal Sayı

Bell sayısı

Adi Shamir

Ayrık Logaritma

Jacobi sembolü

Gottfried Leibniz