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:

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 genau zwei Lösungen, wenn der Modulus eine Primzahl größer Zwei ist. Diese werden als triviale Lösungen bezeichnet und lauten

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

Quellen Bearbeiten

  • 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