Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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 m genau zwei Lösungen, wenn der Modulus m ein 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

• 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

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Legendre-Kongruenz, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.