This is an empirical result to complement Poncho's answer;
Take Curve25519 which has a cofactor $8$ as the order $n$ of the group factors as
$\small{n = 2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989}$
We use SageMath and SageMath random_element
function in which it may return the identity element $\mathcal{O}$ of the curve ( the of chance getting it is negligible) , on Curve25519 $\mathcal{O}
= (0:1:0)$ on Weierstrass form.
import time
def randomBasePointByCofactor(E,identity,cofactor):
s = time.time()
ci = 0
n = E.order()
for i in range(1,10000):
P = E.random_element()
if cofactor*P != identity:
ci = ci +1
e = time.time()
print("time elapsed on randomBasePointByCofactor", e-s)
return (ci)
def randomBasePointByOrder(E,identity,cofactor):
s = time.time()
ci = 0
n = Integer(E.order() / cofactor)
for i in range(1,10000):
P = E.random_element()
if n*P == identity:
ci = ci +1
e = time.time()
print("time elapsed on randomBasePointByOrder", e-s)
return (ci)
p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
K = GF(p)
A = K(0x76d06)
B = K(0x01)
E = EllipticCurve(K, ((3 - A^2)/(3 * B^2), (2 * A^3 - 9 * A)/(27 * B^3)))
IP = E((0,1,0))
Bound = 10000
print(" number of found generators =" , randomBasePointByCofactor(E,IP,8), "/", Bound)
print(" number of found generators =", randomBasePointByOrder(E,IP,8),"/", Bound)
A sample result is
time elapsed on randomBasePointByCofactor 1.9164307117462158
number of found generators = 9999 / 10000
time elapsed on randomBasePointByOrder 64.77565383911133
number of found generators = 1267 / 10000
Therefore
the cofactor method is faster ~32 times faster in the experiments.
We can explain this in simple terms as; $8$ requires 4 doublings and 1 addition, whereas $n$ requires 251 doublings and 125 addition with naive double-and-algorithm. This gives ~75 times more calculations if we assume doubling and additions have the same speed which they are not.
the cofactor method produces more generators than the order method since the $1/8$ of the random elements from $8\cdot q$ falls into the large prime $q$ of the Curve25519.
Therefore, the cofactor method is preferable.