In many cryptographic applications it is necessary to generate elliptic curves (ECs) whose order possesses certain properties. The method that is usually employed for the generation of such ECs is the so-called Complex Multiplication method. This method requires the use of the roots of certain class field polynomials defined on a specific parameter called the discriminant. The most commonly used polynomials are the Hilbert and Weber ones. The former can be used to generate directly the EC, but they are characterized by high computational demands. The latter have usually much lower computational requirements, but they do not directly construct the desired EC. This can be achieved if transformations of their roots to the roots of the corresponding (generated by the same discriminant) Hilbert polynomials are provided. In this paper we present a variant of the Complex Multiplicationmethod that generates ECs of cryptographically strong order. Our variant is based on the computation of Weber polynomials. We present in a simple and unifying manner a complete set of transformations of the roots of aWeber polynomial to the roots of its corresponding Hilbert polynomial for all values of the discriminant. In addition, we prove a theoretical estimate of the precision required for the computation ofWeber polynomials for all values of the discriminant.We present an extensive experimental assessment of the computational efficiency of the Hilbert and Weber polynomials along with their precision requirements for various discriminant values and we compare them with the theoretical estimates.We further investigate the time efficiency of the new Complex Multiplication variant under different implementations of a crucial step of the variant. Our results can serve as useful guidelines to potential implementers of EC cryptosystems involving generation of ECs of a desirable order on resource limited hardware devices or in systems operating under strict timing response constraints