מחשבון סמל לז'נדר

אודות מחשבון זה

סמל לז'נדר (a/p), המוגדר עבור מספר שלם a וראשוני אי-זוגי p, הוא דרך קומפקטית לענות על שאלה יסודית בתורת המספרים: האם לשוויון בחשבון מודולרי x² ≡ a (mod p) יש פתרון? המחשבון מעריך אותו באמצעות קריטריון אוילר: (a/p) ≡ a^((p-1)/2) (mod p), ששווה ל-1 אם a הוא שארית ריבועית מודולו p, ל-−1 אם הוא אי-שארית, ול-0 אם p מחלק את a בדיוק.

סמל לז'נדר הוא אבן בניין בתורת ההדדיות הריבועית ומופיע בכל תורת המספרים החישובית והקריפטוגרפיה — כולל מבחני ראשוניות, אלגוריתמים לחישוב שורשים ריבועיים מודולריים ובנייות בקריפטוגרפיה של עקומות אליפטיות — בכל מקום שבו חשוב אם מספר הוא ריבוע מושלם מודולו ראשוני.