İçeriğe atla

Yarı asal

Vikipedi, özgür ansiklopedi

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.[1] 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.[2]

Örnekler:

  • 1685 = 5 × 337
  • 1681 = 412
  • 1679 = 23 × 73
  • 1678 = 2 × 839

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.[3] Ö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.[4] 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:

φ(p2) = p2p.

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

(OEIS'de A117543 dizisi).
(OEIS'de A152447 dizisi).
(OEIS'de A154928 dizisi).

Kriptografide kullanımı

[değiştir | kaynağı değiştir]

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.[2] 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.

Yarı asalların listesi (OEIS'de A001358 dizisi) 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

[değiştir | kaynağı değiştir]
  1. ^ (OEIS'de A001358 dizisi)
  2. ^ a b Information Security, Governance, Risk, and Compliance - EMC 7 Mayıs 2013 tarihinde Wayback Machine sitesinde arşivlendi.. RSA. Retrieved on 2014-05-11.
  3. ^ Chris Caldwell, The Prime Glossary: semiprime 4 Mart 2016 tarihinde Wayback Machine sitesinde arşivlendi. at The Prime Pages. Retrieved on 2013-09-04.
  4. ^ Broadhurst, David (12 Mart 2005). "To prove that N is a semiprime". 1 Kasım 2013 tarihinde kaynağından arşivlendi. Erişim tarihi: 4 Eylül 2013.