Legendre-Kongruenz

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:

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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.