Llogaritës i simbolit Legendre

Rreth kësaj llogaritëseje

Simboli i Legendre-it (a/p), i përcaktuar për një numër të plotë a dhe një numër të thjeshtë tek p, është një mënyrë e shkurtër për t’iu përgjigjur një pyetjeje themelore në teorinë e numrave: a ka zgjidhje kongruenca x² ≡ a (mod p)? Ky llogaritës e vlerëson duke përdorur kriterin e Euler-it: (a/p) ≡ a^((p-1)/2) (mod p), që është e barabartë me 1 nëse a është mbetje kuadratike mod p, −1 nëse nuk është mbetje, dhe 0 nëse p e pjesëton saktësisht a-në.

Simboli i Legendre-it është element ndërtimi i teorisë së reciprocitetit kuadratik dhe shfaqet kudo në teorinë llogaritëse të numrave dhe në kriptografi — duke përfshirë testet e thjeshtësisë, algoritmet për llogaritjen e rrënjëve katrore modulare dhe ndërtimet në kriptografinë me kurba eliptike — kudo ku ka rëndësi nëse një numër është katror i plotë modulo një numër të thjeshtë.