HesapHanem

Fermat Asallık Testi Hesaplayıcı

Fermat asallık testini çalıştırmak için bir sayı ve taban girin.

Nasıl hesaplanır?

Araç, hızlı modüler üs alma ile r = an−1 mod n kalanını hesaplar; böylece büyük kuvvetler hiçbir zaman tam olarak yazılmaz. Kabul edilen en büyük n 9.007.199.254.740.992'dir (2⁵³); üstündeki sayılar tam olarak tutulamaz. r = 1 ise sonuç Muhtemelen asal, başka bir değer ise n'nin Bileşik olduğunun kanıtıdır. n ve a tabanı tam sayı olmalı, n en az 4 olmalı ve a, 2 ile n − 2 arasında bulunmalıdır; aksi hâlde sonuç çıkmaz. Taban boş bırakılırsa 2 kullanılır. “Muhtemelen asal” bir kanıt değildir: belirli bir tabanda testi geçen bileşik sayılara Fermat sözde asalı denir; bu yüzden ikinci bir taban denenmelidir.

Örnek hesaplama

n = 341 sayısını a = 2 tabanıyla sınayalım. Araç 2340 mod 341 değerini bulur. 210 = 1024 = 3 × 341 + 1 olduğundan 210 ≡ 1 (mod 341) ve 2340 = (210)34 ≡ 1 olur. Kalan 1'dir ve sonuç Muhtemelen asal çıkar. Oysa 341 = 11 × 31 bileşiktir; 2 tabanına göre sözde asaldır. Aynı n için taban 3 denenirse kalan 56 olur, sonuç Bileşik çıkar ve sayının asal olmadığı ortaya çıkar.

Bu örneği dene →

Sık yapılan hatalar

  • Muhtemelen asal sonucunu asallık kanıtı saymak. 341, 2 tabanında testi geçer ama 11 × 31'dir; bu yüzden 2, 3, 5 ve 7 gibi birkaç tabanla tekrarlayın.
  • n = 1, 2 veya 3 ya da 2 ile n − 2 dışında bir taban denemek. Teorem bu aralıkta bir taban gerektirdiğinden araç bu girdilerde sonuç vermez.
  • n ile ortak çarpanı olan bir taban seçmek. n = 561 için taban 3 kalan 375 verir ve elenir, taban 5 ise 1 verir; başarısız bir taban kesin kanıttır, geçen taban değildir.
  • Ondalıklı sayı ya da binlik ayraçlı sayı girmek. n ve a düz tam sayı olmalıdır.
  • 561 gibi Carmichael sayılarının daha çok taban denenince yakalanacağını sanmak. n ile aralarında asal her taban bu sayılar için testi geçer; farklı bir test gerekir.

Bu hesaplama hakkında

Fermat'nın küçük teoremi, n bir asal sayıysa, n'ye bölünmeyen herhangi bir a tam sayı tabanı için a^(n-1) ≡ 1 (mod n) olduğunu söyler. Bu hesaplayıcı bu kontrolü tersine çevirerek çalışır: verilen bir n sayısı ve seçilen bir a tabanı için a^(n-1) mod n değerini hesaplar — sonuç 1 değilse n kesinlikle bileşiktir; sonuç 1 ise n yalnızca muhtemelen asaldır, çünkü nadir bileşik sayılar (Fermat sözde asalları ve özellikle inatçı Carmichael sayıları) birçok hatta tüm tabanlar için bu testi geçebilir.

Büyük sayılar için bile hızlı hesaplanabildiğinden, Fermat testi kriptografide ve bilgisayar bilimi eğitiminde ucuz bir ön filtre olarak kullanılır — gerçek dünyadaki RSA anahtar üretiminin temelini oluşturan Miller-Rabin gibi daha yavaş ve titiz asallık testlerini çalıştırmadan önce belirgin bileşikleri hızla eler. Ayrıca sayılar teorisi derslerinde, modüler üs alma işlemini ve asallık için gerekli koşul ile yeterli koşul arasındaki farkı göstermek için standart bir alıştırmadır.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Yorumlar (1)

  • Editör ekibi

    Başarısız bir test kanıttır, geçen test yalnızca ipucudur. Hazır 2 tabanıyla 15'i deneyin: kalan 1 değil 4 çıkar; bu, hiçbir çarpan bulmadan 15'in bileşik olduğunu kanıtlar. Şimdi hazır değer 17'ye bakın: 2'nin 16. kuvveti 17'ye bölününce kalan 1 olur. Bu araç öğretici örnekler için uygundur. Hangi sayıları deniyorsunuz ve art arda birkaç taban kullanıyor musunuz?

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