A Probabilistic Factorization Algorithm with Quadratic Forms of Negative Discriminant (Q3755496)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4004252
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A Probabilistic Factorization Algorithm with Quadratic Forms of Negative Discriminant |
scientific article; zbMATH DE number 4004252 |
Statements
1987
0 references
computational number theory
0 references
probabilistic algorithm
0 references
factorization
0 references
extended Riemann hypothesis
0 references
primality
0 references
quadratic forms
0 references
A Probabilistic Factorization Algorithm with Quadratic Forms of Negative Discriminant (English)
0 references
0.8350405097007751
0 references
0.829910397529602
0 references
0.8097406029701233
0 references
Der vom Autor vorgestellte neue Faktorisierungsalgorithmus leistet die vollständige Zerlegung einer natürlichen Zahl N mit Wahrscheinlichkeit \(>\) in einer Laufzeit von \(\exp \sqrt{(5/4)\log N\quad \log \log N}\) Schritten unter der Voraussetzung, daß eine verallgemeinerte Riemannsche Vermutung (ERH) richtig ist. Der neue Algorithmus beruht auf folgenden Ideen: 1) Es genügt, den 2-Anteil der Idealklassengruppe von \({\mathbb{Q}}(\sqrt{- N})\) zu kennen, da die ambigen quadratischen Formen der Diskriminante -N (o.B.d.A. \(\equiv 1 mod 4\), andernfalls faktorisiere man 3N) eineindeutig den Zerlegungen von N in zwei Faktoren entsprechen. Die Verwendung dieser Idee geht auf Shanks zurück und wurde von H. W. Lenstra und Schnorr bereits zur Konstruktion probabilistischer Algorithmen benutzt. 2) Auswahl von Primformen, die unter Annahme von ERH die Klassengruppe erzeugen. 3) Bestimmung genügend vieler Relationen zwischen diesen Erzeugenden durch einen probabilistischen Algorithmus; im Falle des Erfolgs liefert dieses Verfahren eine Matrix, deren Determinante ein Vielfaches \(\neq 0\) der Klassenzahl ist. 4) Potenzieren der Primformen mit dem ungeraden Anteil dieser Determinante liefert ein Erzeugendensystem für die 2-Klassengruppe und damit die gewünschte Zerlegung von N. Entscheidend ist dabei eine optimale Wahl der Anzahl der Primformen und des Konstruktionsverfahrens für die Relationen. Neben gittertheoretischen Überlegungen sind hier tiefliegende Methoden aus der algebraischen und analytischen Zahlentheorie erforderlich, dazu die neuesten Verfahren zur schnellen Determinantenberechnung (Wiedemann). Seysens Verfahren ist inzwischen von A. K. Lenstra noch weiter bis zu einer Laufzeit von \(\exp (1+o(1))\sqrt{\log N\quad \log \log N}\) verbessert worden, indem das Aufsuchen der Relationenmatrix unter Verwendung elliptischer Kurven beschleunigt wurde; diese Möglichkeit wird von Seysen bereits in der vorliegenden Arbeit angedeutet.
0 references