ISSN:
1436-5057
Keywords:
10A25
;
68C25
;
Calculation
;
factorization of integers
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Abstract The analysis of the integer factoring algorithms of Morrison-Brillhart and Schroeppel is based on a hypothesis concerning the number-theoretic function $$\psi (n,\upsilon ):\# \{ x \in [1,n]\left| {(p prim \wedge p\left| x \right.)} \right. \Rightarrow p \leqslant \upsilon \} .$$ This hypothesis is supported by experimented results, which are also given in this paper. Contrary to previous conjectures our analysis shows, that the algorithm of Morrison-Brillhart is faster than the algorithm of Schroeppel both from practical and asymptotical point of view.
Notes:
Zusammenfassung Die Algorithmen von Morrison-Brillhart und Schroeppel sind für große natürliche Zahlen (allgemeiner Gestalt und bezüglich der worst-case-Rechenzeit) die effizientesten aller bis heute bekannten Faktorisierungsalgorithmen. Der vorgelegte Effizienzvergleich basiert auf einer theoretischen Analyse, deren Annahmen experimentell verifiziert wurden. Wegen der übergroßen Rechenzeiten ist nämlich ein experimenteller Vergleich der Laufzeiten beider Algorithmen für Zahlenn〉1050 zur Zeit technisch sehr schwierig. Die der Analyse zugrunde gelegten Annahmen betreffen das Verhalten der zahlentheoretischen Funktion $$\psi (n,\upsilon ):\# \{ x \in [1,n]\left| {(p prim \wedge p\left| x \right.)} \right. \Rightarrow p \leqslant \upsilon \} $$ sowie damit verwandter Funktionen. Entgegen den bisherigen Vermutungen können wir zeigen, daß der Morrison-Brillhart-Algorithmus dem Schroeppel-Algorithmus für Zahlen aller Größenbereiche überlegen ist.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02280781
Permalink
