Primality proofs with elliptic curves: probabilistic factorisation

Abstract. We give an asymptotic for the expected number of complete factorisations of natural numbers of the form \(fq \leq n\), utilising probabilistic factorisation methods, where \(f\) is a
\(b(n)\)-smooth number, and \(q\) is a prime larger than \(b(n)\), with \(b(n) : \mathbb{N} \rightarrow [e,\sqrt{n})\).

Key words and phrases. Elliptic curve primality proving, smooth number, first category algorithm, probabilistic factoring.