ISSN:
1436-5057
Keywords:
10A25
;
68C25
;
Calculation
;
factorization of integers
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Bei Eingabe vonn erzeugt der Pollardsche Faktorisierungsalgorithmus durch $$x_0 : = 2;x_{i + 1} : = x_i^2 - 1(\bmod n),i = 1,2,3,...$$ eine Folge in ℤ n . Der Algorithmus bildet mit festemm∈[logn, n 1/4] die größten gemeinsamen Teiler $$ggT(\prod _{i = km + 1}^{km + m} (x_{2i} - x_i ),n),k = 0,1,2,...$$ und benötigt im Mittel $$0\left( {\sqrt p } \right)$$ viele Makroschritte (=Multiplikationen/Divisionen in ℤ n ), um den Primfaktorp vonn aufzufinden. Wir haben den Pollard-Algorithmus unter Verwendung modifizierter Iterationsformeln $$x_{i + 1} = b \cdot x_i^\alpha + c(\bmod n),i = 1,2,...$$ mitx 0,b,c,α∈ℕ und α≥2 ausgewertet. Die experimentellen Daten zeigen, daß die modifizierten Versionen im Falle ggT(α,p-1)≠1 im Mittel $$0\left( {\sqrt {\frac{p}{{ggT(\alpha ,p - 1}}} } \right)$$ viele Makroschritte zum Auffinden des Primfaktorsp vonn benötigen.
Notes:
Abstract The factorization algorithm of Pollard generates a sequence in ℤ n by $$x_0 : = 2;x_{i + 1} : = x_i^2 - 1(\bmod n),i = 1,2,3,...$$ wheren denotes the integer to be factored. The algorithm finds an factorp ofn within $$0\left( {\sqrt p } \right)$$ macrosteps (=multiplications/divisions in ℤ n ) on average. An empirical analysis of the Pollard algorithm using modified sequences $$x_{i + 1} = b \cdot x_i^\alpha + c(\bmod n),i = 1,2,...$$ withx 0,b,c,α∈ℕ and α≥2 shows, that a factorp ofn under the assumption gcd (α,p-1)≠1 now is found within $$0\left( {\sqrt {\frac{p}{{ged(\alpha ,p - 1}}} } \right)$$ macrosteps on average.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02253297
Permalink
