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 \(\pmod 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 \textit{R. K. Guy} [Proc. 5th Manitoba Conf. Numer. Math., Winnipeg 1975, 49--89 (1976; Zbl 0338.10001)].