Karesel Kalıntı Denetleyici

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.