HesapHanem

Karesel Kalıntı Denetleyici

Karesel kalıntıyı kontrol etmek için bir a değeri ve p asal modülü girin.

Nasıl hesaplanır?

Araç Euler kriterini hesaplar: r = a(p−1)/2 mod p. Büyük sayılarda taşma olmasın diye hızlı modüler üs alma kullanılır. a negatif olmayan bir tam sayı, p ise tek bir asal sayı olmalıdır. Önce a, a mod p değerine indirilir. Bu değer 0 ise Legendre sembolü 0 olur ve sonuç a ≡ 0 olarak yazılır. r = 1 ise a bir karesel kalıntıdır (sembol +1). Aksi halde r = p − 1 olur ve a kalıntı değildir (sembol −1). Değerler tam sayıya yuvarlanır. p = 2, çift sayı, asal olmayan sayı (bölme denemesiyle kontrol edilir) veya negatif a için sonuç üretilmez.

Örnek hesaplama

a = 10 ve p = 13 alalım. Adım 1: (13 − 1) ÷ 2 = 6, yani 106 mod 13 hesaplanır. Adım 2: 10² = 100 ≡ 9, 10³ ≡ 9 × 10 = 90 ≡ 12 ve 10⁶ ≡ 12² = 144 ≡ 1 (mod 13). Adım 3: Euler değeri 1 çıkar; sonuç Kuadratik kalan, Legendre sembolü 1 olur. Doğrudan da doğrulayabilirsiniz: 6² = 36 = 2 × 13 + 10, yani x = 6 için x² ≡ 10 (mod 13).

Bu örneği dene →

Sık yapılan hatalar

  • 15 gibi asal olmayan bir modül girmek. Euler kriteri ve Legendre sembolü yalnızca asal sayılar için geçerlidir; araç bu durumda sonuç vermez.
  • Euler değerinde −1 görmeyi beklemek. Kalıntı olmayan sayıda modüler sonuç p − 1 olarak gösterilir (p = 13 için 12); −1 ise Legendre sembolü satırında görünür.
  • Karesel kalıntıyı tam kareyle karıştırmak. 10 sıradan tam sayılarda tam kare değildir ama mod 13'te kalıntıdır.
  • Sonuç 0 çıktığında bunu kalıntı olmayan saymak. a, p'nin katıysa sembol 0'dır ve sonuç a ≡ 0 olarak ayrı bir durumdur.
  • Bir asal modda bulunan sonucu başka bir asal için de geçerli sanmak. Cevap her p için değişir.

Bu hesaplama hakkında

Bir a tam sayısı, x² ≡ a (mod p) olacak şekilde bir x varsa, p asal sayısına göre karesel kalıntıdır — başka bir deyişle a, sıradan tam sayılarda tam kare olmasa bile modüler aritmetikte tam karedir. Euler kriteri, bunu doğrudan x aramadan hızlıca test etmenin bir yolunu sunar: a^((p−1)/2) ≡ 1 (mod p) ise a, p modunda bir karesel kalıntıdır; ≡ −1 ise kalıntı değildir.

Sonuç genellikle +1, −1 veya 0 değerini alan Legendre sembolü (a/p) ile ifade edilir. Bu hesaplayıcı bu sembolü hesaplar; sayılar teorisi derslerinde ve kriptografik algoritmalarda rutin bir adımdır — karesel kalıntılar asallık testlerinde, modüler kareköklerin hesaplanmasında kullanılan Tonelli-Shanks algoritmasında ve bazı dijital imza ile sıfır bilgi ispatı yapılarında doğrudan karşımıza çıkar.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Yorumlar (1)

  • Editör ekibi

    Kalan olması bir karekökün var olduğunu söyler, ne olduğunu değil. p sayısı 4'e bölündüğünde 3 kalanını veriyorsa bir kök a^((p+1)/4) mod p değeridir. Varsayılan a = 5, p = 11 ile deneyin: 5³ = 125, 11'e bölümünden kalan 4'tür ve 4² = 16'nın kalanı 5'tir. Küçük öğretim örneklerini mi kontrol ediyorsunuz, yoksa büyük asalları mı? İhtiyacınız olan boyutları 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