Yarı asal

Sayı kuramında yarı asal sayılar (ayrıca 2 asalımsı olarak da adlandırılır), iki tane asal sayının çarpımı şeklinde yazılabilen pozitif tam sayılardır. Dolayısıyla ya bir asal sayının karesidirler (bu aynı zamanda herhangi bir asal sayının tüm bölenlerinin çarpımı anlamına gelir) ya da dört tane farklı (iki tane asal sayı, sayının kendisi ve 1) pozitif bölene sahiptirler. Buna bağlı olarak, dört tane pozitif bölene sahip her sayı yarı asal olmak zorunda değildir (Örnek: 8). Bir asal sayının karesi olmayan asal sayılara ayrık asal sayılar denir. Bir yarı asal sayı n için Ω(n) tanım gereği ikiye eşittir. Yarı asallar RSA gibi kriptografi sistemlerinde kullanılır.

Örnekler:

• 1685 = 5 × 337
• 1681 = 41Şablon:2
• 1679 = 23 × 73
• 1678 = 2 × 839

Özellikler

Her asal sayının karesi bir yarı asal olduğu için, büyük bir sayının asallığı tespit edildiğinde, daha büyük sayıların da yarı asallığı tespit edilmiş olur. Büyük bir sayının yarı asallığını, çarpanlarının asal olduğunu tespit etmeden bulmak az da olsa olasıdır. Örneğin, Eratosten kalburunda yarı veya tam asalları bulmak istesek, üst sınırın kareköküne kadar değil, küpköküne kadar gitmemiz yetecektir. Yarı asallığın tespiti konusunda, örneğin Goldwasser-Kilian ECPP teoremini kullanan çalışmalar yapılmıştır. Chen teoremine göre, yeterince büyük bir sayı Goldbach hipotezini sağlamıyorsa, yani iki asal sayının toplamı olarak yazılamıyorsa, o zaman o sayı bir asal sayı ile bir yarı asal sayının toplamıdır.

Eğer n, p ve q gibi iki farklı asal çarpanı olan bir ayrık yarı asal sayı ise, Euler totient fonksiyonunun değeri aşağıdaki gibi kolayca hesaplanır:

φ(n) = (p − 1) (q − 1) = p q − (p + q) + 1 = n − (p + q) + 1.

Kare bir yarı asal için de:

φ(pŞablon:2) = p² − p.

Asal Zeta Fonksiyonu, yarı asallara uygulanabilir ve şu sonuçlar ortaya çıkar:

$\sum _{\mathrm{\Omega }(n)=2}\frac{1}{n^2}\approx 0.1407604$ Şablon:OEIS.

$\sum _{\mathrm{\Omega }(n)=2}\frac{1}{n(n-1)}\approx 0.17105$ Şablon:OEIS.

$\sum _{\mathrm{\Omega }(n)=2}\frac{\ln n}{n^2}\approx 0.28360$ Şablon:OEIS.

Kriptografide kullanımı

Yarı asallar RSA kriptografisinde kullanılır ve RSA Security şirketi dönem dönem yarı asalların bulunması konusunda yarışmalar açıp ödüller vermektedir. Kriptografide, yarı asallara yönelik basit kırma algoritmalarını bertaraf etmek için yarı asallar, bu algoritmalar ve diğer olası algoritmalar göz önüne alınarak dikkatli bir biçimde seçilmelidirler. 1974 yılında uzaya gönderilen Arecibo mesajı'nda bit sayısı bir yarı asal (1679) seçilmiştir. Bu şekilde, dikdörtgen biçiminde sadece iki şekilde (73x23 ya da 23x73) gösterilebilir. Bu gösterimlerinden bir karmaşık, biri de istenendir.

Liste

Yarı asalların listesi Şablon:OEIS ile verilir. 500'den küçük yarı asal sayılar şunlardır:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, 118, 119, 121, 122, 123, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 159, 161, 166, 169, 177, 178, 183, 185, 187, 194, 201, 202, 203, 205, 206, 209, 213, 214, 215, 217, 218, 219, 221, 226, 235, 237, 247, 249, 253, 254, 259, 262, 265, 267, 274, 278, 287, 289, 291, 295, 298, 299, 301, 302, 303, 305, 309, 314, 319, 321, 323, 326, 327, 329, 334, 335, 339, 341, 346, 355, 358, 361, 362, 365, 371, 377, 381, 382, 386, 391, 393, 394, 395, 398, 403, 407, 411, 413, 415, 417, 422, 427, 437, 445, 446, 447, 451, 453, 454, 458, 466, 469, 471, 473, 478, 481, 482, 485, 489, 493, 497.

Ayrıca bakınız

• Asal sayı
• Asalımsı