Legendre-Kongruenz

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 ein 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

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • CFRAC — Die Kettenbruchmethode (Abk.: CFRAC) berechnet zwei Teiler einer natürlichen Zahl, die keine Primzahl ist. Durch wiederholte Anwendung lässt sich so die Primfaktorzerlegung dieser Zahl ermitteln. Die Kettenbruchmethode wurde 1931 von Derrick… …   Deutsch Wikipedia

  • Kettenbruchmethode — Die Kettenbruchmethode (Abk.: CFRAC) berechnet zwei Teiler einer natürlichen Zahl, die keine Primzahl ist. Durch wiederholte Anwendung lässt sich so die Primfaktorzerlegung dieser Zahl ermitteln. Die Kettenbruchmethode wurde 1931 von Derrick… …   Deutsch Wikipedia

  • Quadratische-Reste-Problem — Der quadratische Rest ist ein Begriff aus dem mathematischen Teilgebiet Zahlentheorie. Eine Zahl a ist ein quadratischer Rest bezüglich eines Moduls m, wenn sie zu m teilerfremd ist und es eine Zahl x gibt, für die die Kongruenz gilt. Für den… …   Deutsch Wikipedia

  • Quadratischer Nichtrest — Der quadratische Rest ist ein Begriff aus dem mathematischen Teilgebiet Zahlentheorie. Eine Zahl a ist ein quadratischer Rest bezüglich eines Moduls m, wenn sie zu m teilerfremd ist und es eine Zahl x gibt, für die die Kongruenz gilt. Für den… …   Deutsch Wikipedia

  • Euklidisches Lemma — Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler, nämlich der Zahl 1 und sich selbst. Die kleinsten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 … (Folge A000040 in OEIS) Das Wort „Primzahl“ kommt aus… …   Deutsch Wikipedia

  • Primzahlen — Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler, nämlich der Zahl 1 und sich selbst. Die kleinsten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 … (Folge A000040 in OEIS) Das Wort „Primzahl“ kommt aus… …   Deutsch Wikipedia

  • Quadratischer Rest — Der quadratische Rest ist ein Begriff aus dem mathematischen Teilgebiet Zahlentheorie. Eine Zahl a ist ein quadratischer Rest bezüglich eines Moduls m, wenn sie zu m teilerfremd ist und es eine Zahl x gibt, für die die Kongruenz gilt. Für den… …   Deutsch Wikipedia

  • Primzahl — Die Zahl 12 ist keine Primzahl. Eine Primzahl ist eine natürliche Zahl, die größer als eins und ausschließlich durch sich selbst und durch eins teilbar ist. Eine Primzahl ist also eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler …   Deutsch Wikipedia

  • Eisenstein-Zahl — Eisenstein Zahlen als Punkte eines Dreiecksgitters in der komplexen Zahlenebene Die Eisenstein Zahlen sind eine Verallgemeinerung der ganzen Zahlen auf die komplexen Zahlen. Sie sind nach dem deutschen Mathematiker Gotthold Eisenstein, einem… …   Deutsch Wikipedia

  • Elementare Zahlentheorie — Ursprünglich ist die Zahlentheorie (auch: Arithmetik) ein Teilgebiet der Mathematik, das sich allgemein mit den Eigenschaften der ganzen Zahlen und insbesondere mit den Lösungen von Gleichungen in den ganzen Zahlen (Diophantische Gleichung)… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”