Çarpanlara ayırma

Çarpanlara ayırma, bir polinomun, tam sayının ya da matrisin kendisini oluşturan bileşenlerin çarpımı şeklinde yazılmasıdır. Örneğin 15 sayısı 3 ve 5 asal sayılarının çarpımı şeklinde yazılabilir: 3 × 5, ya da x2 − 4 polinomu (x − 2)(x + 2) şeklinde yazılabilir.Çarpanlara ayırmadaki temel amaç bir bütünü daha küçük yapılara ayırmaktır; sayıları asal sayıların çarpımı, polinomları indirgenemeyen polinomların çarpımı şeklinde yazmak gibi. Çarpanlara ayırmanın tersi genişletmedir.Asal çarpanlarına ayırma çok büyük sayılar için zor bir problemdir. Bu problemin bilinen bir çözümü yoktur. Bu yüzden RSA gibi açık anahtarlı şifreleme yöntemlerinde kullanılır.Aritmetiğin temel teoremine göre 1'den büyük her tam sayı asal sayıların çarpımı şeklinde yazılabilir.Bir  tamsayısını çarpanlara ayırmak için, 'nin bölenini 'yu bulmak veya 'nin asal olduğuna karar vermek için bir algoritmaya gerek vardır. Böyle bir bölen bulunduğunda, bu algoritmanın  ve  çarpanlarına tekrar tekrar uygulanması, sonunda 'nin tam çarpanlara ayrılmasını sağlar.'nin bir  bölenini bulmak için,  ve  olacak şekilde 'nun tüm değerlerini test etmek yeterlidir. Aslında, eğer ,  olacak şekilde 'nin bir böleniyse, o zaman  olacak şekilde , 'nin bir bölenidir.'nun değerleri artan sırada denenirse, bulunan ilk bölen mutlaka bir asal sayıdır ve  ortak çarpanının 'dan küçük herhangi bir böleni olamaz. Tam çarpanları bulmak için, 'nin 'dan küçük ve 'den büyük olmayan bir bölenini arayarak algoritmaya devam etmek yeterlidir.Yöntemi uygulamak için 'nun tüm değerlerini denemeye gerek yoktur. Prensip olarak, sadece asal bölenleri denemek yeterlidir. Bunun, örneğin Eratosten kalburu ile üretilebilecek bir asal sayılar tablosuna sahip olması gerekir. Çarpanlara ayırma yöntemi esas olarak Eratosthenes'in eleği ile aynı işi yaptığından, yalnızca asal olup olmadıkları hemen belli olmayan sayıları bölen için denemek genellikle daha kolaydır. Tipik olarak, 2, 3, 5 ve son hanesi 1, 3, 7, 9 olan ve rakamların toplamı 3'ün katı olmayan > 5 sayıları test edilerek ilerlenebilir.Bu yöntem, küçük tamsayıları çarpanlara ayırmak için iyi çalışır, ancak daha büyük tamsayılar için verimsizdir. Örneğin, Pierre de Fermat, 6. Fermat sayısının'nin asal sayı olmadığını keşfedemedi. Aslında yukarıdaki yöntemi uygulamak, 10  ondalık basamaklı bir sayı için 10.000'den fazla bölme gerektirir.Daha verimli çarpanlara ayırma algoritmaları vardır. Ancak nispeten verimsiz kalırlar, çünkü tekniğin mevcut durumu ile, rastgele seçilen iki asal sayının çarpımı olan 500 ondalık basamaklı bir sayı daha güçlü bilgisayarlarla bile çarpanlara ayrılamaz. Bu, güvenli internet iletişimi için yaygın kullanılan RSA şifreleme sisteminin güvenliğini sağlar.693 tektir (2 bölen değildir), ancak 3:'ün katıdır: biri  ve 'e sahiptir. 231 ve birinci bölen adayı olarak 3 ile devam edin.231 aynı zamanda 3:'ün katıdır:  ve dolayısıyla  vardır. Birinci bölen adayı olarak 77 ve 3 ile devam edin.77, 3'ün katı değildir, çünkü rakamlarının toplamı 14'tür, 3'ün katı değildir. Son basamağı 7 olduğu için 5'in katı da değildir. Test edilecek bir sonraki tek bölen 7'dir.  ve dolayısıyla . Bu, 7'nin asal olduğunu gösterir (doğrudan test edilmesi kolaydır). Birinci bölen adayı olarak 11 ve 7 ile devam edin.Birden çok değişkenin olduğu bir ifadede önce benzer terimler bir araya getirilip ortak çarpan parantezine alınır, ardından oluşan diğer ortak terim de paranteze alınır. Örneğin,