Legendre Sembolü Hesaplama

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.