Legendren symbolin laskuri

Tietoa tästä laskurista

Legendren symboli (a/p), joka on määritelty kokonaisluvulle a ja parittomalle alkuluvulle p, on tiivis tapa vastata lukuteorian perustavanlaatuiseen kysymykseen: onko kongruenssilla x² ≡ a (mod p) ratkaisua? Tämä laskuri laskee sen Eulerin kriteerillä: (a/p) ≡ a^((p-1)/2) (mod p), joka on 1, jos a on neliönjäännös modulo p, −1, jos se on epäjäännös, ja 0, jos p jakaa a:n tasan.

Legendren symboli on neliöllisen resiprookkisuuden teorian rakennuspalikka, ja se esiintyy kaikkialla laskennallisessa lukuteoriassa ja kryptografiassa — mukaan lukien alkulukutestit, modulaaristen neliöjuurten laskemisen algoritmit ja elliptisten käyrien kryptografian konstruktiot — aina, kun on merkitystä, onko luku täydellinen neliö alkuluvun modulossa.