HesapHanem

Miller-Rabin Asallık Testi Hesaplama

Miller-Rabin ile asallık testi yapmak için negatif olmayan bir tam sayı girin.

Nasıl hesaplanır?

Bir tam sayı n girin (yalnızca rakam; negatif, ondalık ve virgüllü değerler reddedilir). 2'den küçük değerler bileşik olarak bildirilir. Araç önce n'yi 2 ile 37 arasındaki asallara böler; bir eşleşme sonucu hemen belirler (n o asalın kendisiyse asal, değilse bileşiktir ve o asal tanık olarak gösterilir). Aksi halde n − 1 = 2s · d yazar (d tek) ve 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 tabanlarını sırayla dener. Bir taban, s'den küçük bir r için ad ≡ ±1 (mod n) ya da a2r·d ≡ −1 (mod n) koşulunu sağlarsa geçer. Kalan ilk taban n'nin bileşik olduğunu kanıtlar ve tanık olarak gösterilir. Hepsi geçerse n asaldır; bu on iki tabanla bu sonuç 318.665.857.834.031.151.167.461'in (yaklaşık 3,18 × 1023; on iki tabanın hepsine karşı en küçük güçlü yalancı asal, Sorenson ve Webster) altında kesindir. Bu büyüklükten itibaren karar bunun yerine “büyük olasılıkla asal” olarak okunur. Sunucudaki matematik kütüphanesine bağlı olarak 263 − 1'in üstündeki sayılar karar yerine Bilinmiyor dönebilir.

Örnek hesaplama

n = 3215031751 sayısını sınayalım. 37'ye kadar hiçbir asal çarpanı yoktur, bu yüzden deneme bölmesi bir şey bulmaz. Sonra n − 1 = 3215031750 = 21 × 1607515875 olur; yani s = 1 ve d = 1607515875. 2, 3, 5 ve 7 tabanlarının hepsi geçer, dolayısıyla yalnızca bu dört tabanı kullanan bir test n'ye asal derdi. 11 tabanı ise ne 1 ne de n − 1 sonucunu verir, yani kalır. Araç composite sonucunu ve 11 tanığını bildirir. Buna karşılık 97 için asal çıkar ve tanık yerinde tire görünür.

Bu örneği dene →

Sık yapılan hatalar

  • Tanığı n'nin bir çarpanı sanmak. 1681 (41 × 41) için tanık 2'dir ve testi geçemeyen bir tabandır; 561 için tanık 3'tür ve 561'i gerçekten böler. İkisi de tam bir çarpanlara ayırma değildir.
  • Asal bir sayıda tanık görmeyi beklemek. Tire, hiçbir tabanın sorun bulmadığı anlamına gelir; asallarda sonuç budur.
  • Elle yalnızca 2 tabanını deneyip güvenmek. 2047 = 23 × 89 gibi bazı bileşik sayılar tek başına 2 tabanını geçer; birkaç taban gerekir, araç bu yüzden on iki taban dener.
  • 1, 0 ya da negatif bir sayı girip asallık kararı beklemek. 1 ve 0 bileşik olarak gösterilir, ama katı anlamda ikisi de bileşik sayı değildir; negatif sayılarda sonuç çıkmaz.
  • Virgüllü, içinde boşluk bulunan, ondalık noktalı ya da işaretli bir sayı yapıştırmak. Yalnızca düz rakamlar kabul edilir.

Kaynaklar

Bu hesaplama hakkında

Miller-Rabin testi, n − 1 sayısını d tek sayı olacak şekilde 2ˢ·d biçiminde yazıp, bir tanık taban a'nın aᵈ ≡ 1 (mod n) ya da bir r < s için a^(2ʳ·d) ≡ −1 (mod n) koşulunu sağlayıp sağlamadığını kontrol eder. Tek bir tanıkla sonuç yalnızca olasılıksaldır; ancak küçük, kanıtlanmış sabit bir tanık taban kümesiyle (örneğin 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) test yapıldığında, 318.665.857.834.031.151.167.461'in (yaklaşık 3,18 × 10²³, Sorenson ve Webster 2015) altındaki her tam sayı için deterministik bir sonuç elde edilir — bu da çoğu uygulamanın ihtiyaç duyacağının çok ötesindedir. Bu büyüklükten itibaren on iki tabanın hepsini geçen bir sayı büyük olasılıkla asal olarak bildirilir, çünkü bu sınırda o tabanlara karşı güçlü bir yalancı asal vardır; bileşik kararı ise her zaman kesindir.

Kriptograflar ve yazılım geliştiriciler, RSA veya Diffie-Hellman anahtarları için büyük asal aday sayılar üretirken tam olarak bu tür bir testi kullanır; bilgisayar mühendisliği öğrencileri ise Miller-Rabin'in büyük bir tam sayının asallığını kontrol etmede neden deneme bölmesinden çok daha hızlı ölçeklendiğini gerçek sayılar üzerinde görmek için bu aracı kullanır.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Yorumlar (1)

  • Editör ekibi

    Tanık sütununu dikkatle okuyun. Sayıyı küçük bir asal bölüyorsa tanık o asalın kendisidir; örneğin 561 için 3 görünür ve onu bölerek çarpanlara ayırmaya başlayabilirsiniz. Sayıyı bir taban yakalıyorsa tanık yalnızca bileşik olduğunu kanıtlar, çarpan değildir. Asal bir sayıda tire görünür. Sayıları bir kriptografi alıştırması, bir bulmaca ya da ödev için mi deniyorsunuz? Hangi büyüklükleri denediğinizi yazın.

Popüler hesaplayıcılar

Kredi Hesaplama

Aylık taksit, toplam faiz ve ödeme planını hesaplayın.

Yüzde Hesaplama

Yüzde değişim, indirim ve oran hesaplamaları.

İndirim Hesaplama

İndirimli fiyatı, kazancı ve indirim tutarını hesaplayın.

Vücut Kitle Endeksi (VKİ)

Boy ve kiloya göre vücut kitle endeksini hesaplayın.

Yaş Hesaplama

Doğum tarihinden bugüne tam yıl, ay ve gün cinsinden yaşınızı hesaplayın.

Bileşik Faiz Hesaplama

Ana para, faiz oranı ve süreye göre bileşik faizle nihai tutarı hesaplayın.

Tüm Hesaplayıcılar