Primality proofs with elliptic curves: Conjectures for the expected number of curve orders

Abstract. In this article we state two conjectures, which enable us to give a satisfying answer to the question posed by the authors of article [4] concerning the expected number of curve orders for a given prime during the application of the elliptic curve primality proving method. The presented train of thoughts isolate the problematic aspects of this subject, and reveal the areas which require further development.

Key words and phrases. Elliptic curve primality proving, negative fundamental discriminant, elliptic curve order, Legendre symbol, smooth number, class number, square-free number, random walk, quadratic (non-)residue, Siegel–Walfisz theorem, number of (distinct) prime factors, Abel's identity.