Kalkulator Legendrovega simbola

O tem kalkulatorju

Legendrov simbol (a/p), opredeljen za celo število a in liho praštevilo p, je strnjen način odgovora na temeljno vprašanje teorije števil: ali ima kongruenca x² ≡ a (mod p) rešitev? Ta kalkulator ga izračuna z Eulerjevim kriterijem: (a/p) ≡ a^((p-1)/2) (mod p), kar je enako 1, če je a kvadratni ostanek po modulu p, −1, če je kvadratni neostanek, in 0, če p natančno deli a.

Legendrov simbol je gradnik teorije kvadratne recipročnosti in se pojavlja v računski teoriji števil in kriptografiji – med drugim pri testih praštevilskosti, algoritmih za izračun modularnih kvadratnih korenov in konstrukcijah v kriptografiji na eliptičnih krivuljah – povsod, kjer je pomembno, ali je število popoln kvadrat po modulu praštevila.