Die Legendre-Kongruenz ist ein Begriff aus dem mathematischen Teilgebiet der Zahlentheorie. Es handelt sich um eine Kongruenz, bei der auf beiden Seiten je eine Quadratzahl steht:

${\displaystyle x^{2}\equiv y^{2}\ {\pmod {m}}}$

Diese nach Adrien-Marie Legendre benannten Kongruenzen bilden die Grundlage mehrerer Faktorisierungsverfahren. Unter Verwendung von Faktorbasen werden dort Legendre-Kongruenzen erzeugt, mit deren Hilfe wiederum Teiler von ganzen Zahlen berechnet werden. Beispiele sind die Kettenbruchmethode, das Quadratische Sieb und SQUFOF.

Eine Legendre-Kongruenz hat modulo ${\displaystyle m}$ genau zwei Lösungen, wenn der Modulus ${\displaystyle m}$ eine Primzahl größer Zwei ist. Diese werden als triviale Lösungen bezeichnet und lauten

${\displaystyle x\equiv \pm y\ {\pmod {m}}}$

Ist der Modulus hingegen eine zusammengesetzte Zahl, so besitzt eine Legendre-Kongruenz noch zusätzliche Lösungen.

Quellen

• Hans Riesel: Prime Numbers and Computer Methods for Factorization. 2. Auflage. Birkhäuser, Boston 1994, ISBN 0-8176-3743-5, S. 156–158
• Song Y. Yan: Number theory for computing. 2. Auflage. Springer, 2002, ISBN 3-540-43072-5, S. 234–237