Kalkulačka Legendrovho symbolu

O tejto kalkulačke

Legendrov symbol (a/p), definovaný pre celé číslo a a nepárne prvočíslo p, je stručný spôsob, ako odpovedať na základnú otázku teórie čísel: má kongruencia x² ≡ a (mod p) riešenie? Táto kalkulačka ho vyhodnocuje pomocou Eulerovho kritéria: (a/p) ≡ a^((p-1)/2) (mod p), čo sa rovná 1, ak a je kvadratický zvyšok modulo p, −1, ak je nezvyšok, a 0, ak p číslo a presne delí.

Legendrov symbol je stavebným kameňom teórie kvadratickej reciprocity a objavuje sa v celej výpočtovej teórii čísel a kryptografii — vrátane testov prvočíselnosti, algoritmov na výpočet modulárnych druhých odmocnín a konštrukcií v kryptografii na eliptických krivkách — všade tam, kde záleží na tom, či je číslo úplným štvorcom modulo prvočíslo.