HesapHanem

Legendre Sembolü Hesaplama

Bir tam sayı a ve tek asal p girin; Legendre sembolünü hesaplayın.

Nasıl hesaplanır?

Legendre sembolü (a/p), tek bir p asalı için x² ≡ a (mod p) denkliğinin çözümü olup olmadığını söyler. Araç Euler kriterini kullanır: a^((p−1)/2) mod p değerini tekrarlı kareleme ile hesaplar; bu yöntem büyük p için bile hızlıdır. Sonuç, kuvvet 1 ise 1 (a, p modunda bir kareyi gösterir), p − 1 ise -1 (a kare değildir) ve p, a'yı bölüyorsa 0'dır. Negatif a kabul edilir; önce 0 ile p − 1 aralığına indirilir. Hem a hem p tam sayı olmalıdır. Araç p'nin 1.000.000.000'u aşmayan tek bir asal olduğunu denetler, aksi halde sonuç vermez; yani p = 2, bileşik sayılar ve 1.000.000.007 gibi daha büyük asallar kabul edilmez.

Örnek hesaplama

(3/7) değerini bulalım. Burada (p − 1) ÷ 2 = 3 olduğundan 3³ mod 7 gerekir. 3³ = 27 ve 27 − 3 × 7 = 6, bu da 7 − 1, yani mod 7'de −1'e eşittir. Legendre sembolü bu nedenle -1'dir. Doğrudan kontrol de aynı sonucu verir: mod 7'deki kareler 1² = 1, 2² = 4 ve 3² = 9 ≡ 2'dir; yani yalnızca 1, 2 ve 4 karedir, 3 değildir. Buna karşılık (2/7) = 1'dir, çünkü 2 bu listede yer alır.

Bu örneği dene →

Sık yapılan hatalar

  • 9 ya da 15 gibi bileşik bir modül girmek: sembol yalnızca asal p için tanımlıdır ve araç sonuç vermez; bunun için farklı bir fonksiyon olan Jacobi sembolü gerekir.
  • 0'ı "çözüm yok" diye okumak: 0, p'nin a'yı böldüğü anlamına gelir ve bu durumda x = 0 aslında x² ≡ a denkliğinin çözümüdür.
  • -1'i "a negatif" ya da "x negatif" diye okumak; bu, a'nın kuadratik kalan olmadığını gösterir, yani hiçbir tam sayı x için x² ≡ a (mod p) sağlanmaz.
  • Sembolü çözüm sayısını bulmak için kullanmak: 1 olduğunda tam iki çözüm x ve p − x vardır, ancak araç bunları bulmaz.
  • a ya da p için ondalık veya kesir girmek ya da p = 2 yazmak: a ve p tam sayı olmalı, p ise tek bir asal olmalıdır.

Bu hesaplama hakkında

Legendre sembolü (a/p), bir tam sayı a ve tek bir asal p için tanımlanır ve sayı teorisindeki temel bir soruyu yanıtlamanın derli toplu bir yoludur: x² ≡ a (mod p) uyumunun bir çözümü var mıdır? Bu hesaplayıcı bunu Euler kriteriyle değerlendirir: (a/p) ≡ a^((p-1)/2) (mod p); bu, a, p modunda bir kuadratik kalan ise 1, kalan değilse −1 ve p, a'yı tam olarak bölüyorsa 0'dır.

Legendre sembolü, kuadratik karşılıklılık teorisinin bir yapı taşıdır ve hesaplamalı sayı teorisi ile kriptografide — asallık testleri, modüler karekök hesaplama algoritmaları ve eliptik eğri kriptografisindeki yapılar dahil — bir sayının bir asala göre tam kare olup olmadığının önemli olduğu her yerde karşımıza çıkar.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Yorumlar (1)

  • Editör ekibi

    Aracı hızlıca sınamak için iki tamamlayıcı kural var: (−1/p) simgesi, p sayısının 4'e bölümünden kalan 1 ise 1 olur; (2/p) simgesi ise p sayısının 8'e bölümünden kalan 1 veya 7 ise 1 olur. Buna göre (−1/13) 1, (−1/11) −1, (2/7) 1 ve (2/11) −1 çıkar ve araç da bunların hepsini aynı şekilde verir. Bunu sayılar kuramı ödevi için mi kullanıyorsunuz, yoksa kodda modüler karekök gibi bir iş için mi?

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