Kalkulačka Legendreova symbolu

O této kalkulačce

Legendreův symbol (a/p), definovaný pro celé číslo a a liché prvočíslo p, je stručný způsob, jak odpovědět na základní otázku teorie čísel: má kongruence x² ≡ a (mod p) řešení? Tato kalkulačka jej vyhodnocuje pomocí Eulerova kritéria: (a/p) ≡ a^((p-1)/2) (mod p), které se rovná 1, je-li a kvadratický zbytek modulo p, −1, je-li kvadratický nezbytek, a 0, pokud p dělí a beze zbytku.

Legendreův symbol je stavebním kamenem teorie kvadratické reciprocity a objevuje se v celé výpočetní teorii čísel a kryptografii – včetně testů prvočíselnosti, algoritmů pro výpočet modulárních odmocnin a konstrukcí v kryptografii na eliptických křivkách – všude, kde záleží na tom, zda je číslo dokonalým čtvercem modulo prvočíslo.