Yarı asal

Vikipedi, özgür ansiklopedi
Şuraya atla: kullan, ara

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, ya da dört tane farklı bölenleri vardır. Dört tane böleni olan sayılar, 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:

  • 1681 = 412
  • 1679 = 23 × 73
  • 1678 = 2 × 839

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

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.

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

Yarı asalların listesi (OEIS'de A001358 dizisi) ile verilir. 1000'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, 159, 161, 166, 169, 177, 178, 183, 185, 187, 194, 201, 202, 205, 206, 209, 213, 214, 215, 218, 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, 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, 501, 502, 505, 511, 514, 515, 517, 519, 526, 527, 529, 533, 535, 537, 538, 542, 543, 545, 551, 553, 554, 559, 562, 565, 566, 573, 579, 581, 583, 586, 589, 591, 597, 611, 614, 622, 623, 626, 629, 633, 634, 635, 649, 655, 662, 667, 669, 671, 679, 681, 685, 687, 689, 695, 698, 699, 703, 706, 707, 713, 717, 718, 721, 723, 731, 734, 737, 745, 746, 749, 753, 755, 758, 763, 766, 767, 771, 778, 779, 781, 785, 789, 791, 793, 799, 802, 803, 807, 813, 815, 817, 831, 835, 838, 841, 842, 843, 849, 851, 862, 865, 866, 869, 871, 878, 879, 886, 889, 893, 895, 898, 901, 905, 913, 914, 917, 921, 922, 923, 926, 933, 934, 939, 943, 949, 951, 955, 958, 959, 961, 965, 973, 974, 979, 982, 985, 989, 993, 995 ve 998.

Ayrıca bakınız[değiştir | kaynağı değiştir]

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

  1. ^ (OEIS'de A001358 dizisi)
  2. ^ a b Information Security, Governance, Risk, and Compliance - EMC. RSA. Retrieved on 2014-05-11.
  3. ^ Chris Caldwell, The Prime Glossary: semiprime at The Prime Pages. Retrieved on 2013-09-04.
  4. ^ Broadhurst, David (12 March 2005). "To prove that N is a semiprime". http://physics.open.ac.uk/~dbroadhu/cert/semgpch.gp. Erişim tarihi: 2013-09-04.