Ein Verfahren zur Primfaktorzerlegung großer Zahlen mit Hilfe binärer quadrati\-scher Formen (Q2524092)

Verf. findet aus zwei Darstellungen \(m = x_i^2+Ny_i^2\) \((i = 1, 2\); \(N\) ein fester numerus idoneus) eine echte Faktorzerlegung von \(m=m_1 m_2\). [Bem. des Ref.: Die bei \textit{E. Trost} [Primzahlen (1953; Zbl 0053.360*), S. 33] für beliebiges \(N > 0\) angegebene Methode ist nicht allgemein anwendbar, der Beweis fehlerhaft; Gegenbeispiel nach R. Pacher: \(1504 = 38^2+15\cdot 2^2 = 17^2+15\cdot 9^2]\). Verf. bestimmt sämtliche Darstellungen, indem er zunächst \(m\equiv x_q^2 + Ny_q^2\mod q\) mit den Primzahlen \(q = 3, 5, \ldots, 31\) löst (wie, ist nicht beschrieben) und daraus \(x, y\equiv x_q, y_q \mod q\) nach dem Lehmerschen Sieb bestimmt, \(x, y\) liegt damit \(\mod \prod_qq\approx 10^{11}\) fest. Zur Anwendung auf \(m\approx 10^{16}\) (warum nicht \(m\approx 10^{22}\) ?) ist nur noch zu prüfen, ob die simultanen Lösungen, \(\mod q\) auch als natürliche Zahlen Lösungen sind. Verf. gewinnt dann aus der Menge aller Lösungen, falls sie nicht-leer ist, sämtliche Teiler von \(m\), insbesondere natürlich auch einen evtl. Primzahlbeweis. Die Rechenzeit hängt wesentlich von dem leider nicht beschriebenen Siebprogramm ab. Im Universalrechner ist das Programm nach Angabe des Verf. zeitlich noch dem suksessiven Dividieren durch alle Primzahlen bis \(\sqrt m\) unterlegen, sofern diese gespeichert sein können. (Nach Ansicht des Ref. genügt die Speicherung bis \(\root 4 \of m\), wenn noch genügend Platz für ein Primzahlsieb vorhanden ist.)