asal çarpanlara ayırma  

zaman karmaşıklığı sebebiyle günümüzün belli başlı bazı şifreleme yöntemlerinin temelini oluşturur. klasik bilgisayarlarda çözmenin kolay bir yolu bilinmemektedir. örneğin n sayısının m'den küçük asal çarpanı var mı? sorusuna polinom zamanda (n'in fonksiyonu olarak) doğru cevap veren bir klasik algoritma bulunamamıştır.

öte yandan kuantum bilgisayarları için bu işi polinom zamanda yapan bir algoritma biliyoruz. (bkz: shor'un algoritması)

(bkz: asal sayı teoremi)

potansiyel bir cevahir kirişçi tehdidi gibi duran matematiksel bir işlem. zordur.

hem np'de hem de co-np'de olduğunu bildiğimiz problemlerden birisi. eğer bir gün np-tam olduğunu gösterirsek bu np ve co-np kümelerinin birbirine eşit olduğu anlamına gelecek. ama bu da aynı zamanda kuantum bilgisayarları için np ve p kümelerinin birbirine eşit olduğu anlamına gelecek çünkü asal çarpanlara ayırma problemi için kuantum bilgisayarlarında çalışan polinom zamanlı bir algoritma biliyoruz. yani asal çarpanlara ayırma probleminin np-tam olduğunu göstermek aynı problemin kuantum bilgisayarları için p olduğunu göstermeye eş değer.

peki bu bilgi günlük hayatta ne işimize yarar? içeriden biraz daha bilgi almadan pek işe yaramaz. mesela bugün 100 matematikçiye "asal çarpanlara ayırma np-tam mıdır?" diye sorsak 99.7'si olumsuz cevap verir. bahislerinizi oynarken bu oranı göz önünde bulundurun.

(bkz: asal sayılar)