Pollard, J. M. A Monte Carlo method for factorization. (English) Zbl 0312.10006 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) Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 2 ReviewsCited in 59 Documents MSC: 11Y05 Factorization 11Y11 Primality 65C05 Monte Carlo methods PDF BibTeX XML Cite \textit{J. M. Pollard}, BIT, Nord. Tidskr. Inf.-behandl. 15, 331--334 (1975; Zbl 0312.10006) Full Text: DOI 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 · doi:10.1017/S0305004100049252 [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 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.