A Monte Carlo method for factorization. (English) Zbl 0312.10006

Pollard, J. M.

BIT, Nord. Tidskr. Inf.-behandl. 15, 331-334 (1975).

The following simple method will find small prime factors \(p\) of a number \(n\) in \(O(p^{1/2})\) arithmetical operations as opposed to the \(O(p)\) operations required by trial division. Let \(x_0=2\), \(x_{i+1}\equiv x_i^2-1\pmod n\) (other similar sequences may be used). Generate in turn the pairs \((x_j,x_{2j})\), accumulating the product (mod \(n\)) of the numbers \(x_{2j}.x_j\). At intervals, compute the g.c.d. of this product and \(n\), which may give a factor, not necessarily prime. Probabilistic arguments predict that on average one should take about \(1.03\,p^{1/2}\) steps to find a prime \(p\); this is confirmed by experiment. The method has been further discussed by R. K. Guy [Proc. 5th Manitoba Conf. numer. Math., Winnipeg 1975, 49–89 (1976; Zbl 0338.10001)].

Reviewer: J. M. Pollard (Maidenhead)

MSC:

11Y05	Factorization
11Y11	Primality
65C05	Monte Carlo methods

Citations:

Zbl 0338.10001

References:

[1]	M. C. Wunderlich and J. L. Selfridge,A Design for a Number Theory Package with an Optimized Trial Division Routine, Comm. A.C.M. 17,5 (May 1974), 272–276. · Zbl 0276.68025
[2]	J. M. Pollard,Theorems on Factorization and Primality Testing, Proc. Camb. Phil. Soc. 76 (1974), 521–528. · Zbl 0294.10005
[3]	D. E. Knuth,Seminumerical Algorithms: the Art of Computer Programming, Vol. 2, Addison-Wesley, 1969. · Zbl 0191.18001
[4]	Michael A. Morrison and John Brillhart,A Method of Factoring and the Factorization of F 7, Math. Comp. 29,129 (1975), 183–206. · Zbl 0302.10010