Asal Çarpan Hesaplama

Asal çarpanlar, bir sayıyı bölebilen asal sayılardır. Örneğin 60 = 2² × 3 × 5 yazımında 2, 3 ve 5 sayının asal çarpanlarıdır. Her tam sayı (1'den büyük) asal çarpanlar çarpımı olarak tek biçimde yazılabilir; bu Aritmetiğin Temel Teoremi olarak bilinir.

Yalnızca 1 ve kendisine tam bölünebilen 1'den büyük tam sayılara asal sayı denir. İlk birkaç asal sayı: 2, 3, 5, 7, 11, 13, 17, 19, 23... 2, tek çift asal sayıdır. 100'e kadar 25 asal sayı vardır.

Asal çarpanlar; EBOB ve EKOK hesaplamasında, şifreleme algoritmalarında (özellikle RSA), kesirlerin sadeleştirilmesinde ve sayı teorisi problemlerinde temel rol oynar. Modern internet güvenliği büyük sayıların asal çarpanlarına ayrılmasının zorluğuna dayanır.

√n'ye kadar olan asal sayılara bölünebiliyorsa asal değildir. Hiçbirine tam bölünmüyorsa asaldır. Örneğin 97 için √97 ≈ 9,8'e kadar test edilir (2, 3, 5, 7); hiçbiri bölmez, dolayısıyla 97 asaldır.

360 = 2³ × 3² × 5. Bölme adımları: 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5, 5 asal. Sonuç: 2³ × 3² × 5 = 8 × 9 × 5 = 360 ✓. 360'ın 24 farklı pozitif böleni vardır.

n = p₁^a₁ × p₂^a₂ × ... şeklinde asal çarpan gösteriminde toplam bölücü sayısı (a₁+1) × (a₂+1) × ... formülüyle bulunur. Örneğin 36 = 2² × 3² için bölücü sayısı (2+1)(2+1) = 9'dur (1,2,3,4,6,9,12,18,36).

EBOB için ortak asal çarpanların en küçük kuvvetlerini çarpın. EKOK için tüm asal çarpanların en büyük kuvvetlerini çarpın. Örneğin 12 = 2²×3, 18 = 2×3²: EBOB = 2¹×3¹ = 6, EKOK = 2²×3² = 36.

Evet, asal sayıların sayısı sonsuzdur. Öklid yaklaşık MÖ 300'de bunu kanıtlamıştır: Sonlu sayıda asal sayı olduğunu varsayarsak, hepsinin çarpımına 1 ekleyerek mevcut asallara bölünemeyen yeni bir sayı oluşturulabilir — bu çelişki sonsuzluğu kanıtlar.

Büyük asallar için Eratostenes Kalburu (küçük sayılar), Miller-Rabin testi (olasılıksal) ve Lucas-Lehmer testi (Mersenne asalları için) kullanılır. Bilinen en büyük asal sayı 2024'te bulunan 41 milyon basamaklı bir Mersenne asalıdır (2^136279841 - 1).

RSA şifrelemesi, iki büyük asal sayının çarpımı olan n = p × q hesabının kolay, ancak n'den p ve q'nun bulunmasının (çarpanlara ayırma) çok zor olduğu gerçeğine dayanır. 2048 bitlik RSA anahtarı için bu işlem günümüz bilgisayarlarıyla milyarlarca yıl sürer.