Υπολογιστής Συμβόλου Legendre

Σχετικά με αυτόν τον υπολογιστή

Το σύμβολο Legendre (a/p), που ορίζεται για έναν ακέραιο a και έναν περιττό πρώτο p, είναι ένας συμπαγής τρόπος να απαντηθεί ένα θεμελιώδες ερώτημα της θεωρίας αριθμών: έχει η ισοτιμία x² ≡ a (mod p) λύση; Αυτός ο υπολογιστής το υπολογίζει με το κριτήριο του Euler: (a/p) ≡ a^((p-1)/2) (mod p), που ισούται με 1 αν το a είναι τετραγωνικό υπόλοιπο mod p, −1 αν δεν είναι, και 0 αν το p διαιρεί ακριβώς το a.

Το σύμβολο Legendre είναι δομικό στοιχείο της θεωρίας της τετραγωνικής αντιστροφής και εμφανίζεται σε όλη την υπολογιστική θεωρία αριθμών και την κρυπτογραφία — συμπεριλαμβανομένων των ελέγχων πρώτων αριθμών, των αλγορίθμων για τον υπολογισμό τετραγωνικών ριζών modulo και των κατασκευών στην κρυπτογραφία ελλειπτικών καμπυλών — παντού όπου έχει σημασία αν ένας αριθμός είναι τέλειο τετράγωνο modulo έναν πρώτο.