diff --git a/src/sage/schemes/elliptic_curves/ell_finite_field.py b/src/sage/schemes/elliptic_curves/ell_finite_field.py
index 16ded52a13b..1cb97a66174 100755
--- a/src/sage/schemes/elliptic_curves/ell_finite_field.py
+++ b/src/sage/schemes/elliptic_curves/ell_finite_field.py
@@ -2881,8 +2881,12 @@ def EllipticCurve_with_prime_order(N):
 
     while True:
         # Iterating over the odd primes by chunks of size log(`N`).
-        S.extend(p for p in prime_range(prime_start, prime_end)
-                 if kronecker(N, p) == 1)
+        #S.extend(p for p in prime_range(prime_start, prime_end)
+        #         if kronecker(N, p) == 1)
+        for p in prime_range(prime_start, prime_end):
+            if kronecker(N, p) == 1:
+                # Equivalent to p* = (-1)^((p - 1) / 2) * p in [BS2007]_ page 5.
+                S.append(-p if p >> 1 & 1 else p)
 
         # Every possible products of distinct elements of `S`.
         # There probably is a more optimal way to compute all possible products
@@ -2890,10 +2894,10 @@ def EllipticCurve_with_prime_order(N):
         # done multiple times.
         for e in powerset(S):
             D = product(e)
-            if -D % 8 != 5:
+            if D % 8 != 5:
                 continue
 
-            Q = BinaryQF([1, 0, D])
+            Q = BinaryQF([1, 0, -D])
             sol = Q.solve_integer(4 * N)
             if sol is None:
                 continue
@@ -2903,7 +2907,7 @@ def EllipticCurve_with_prime_order(N):
             p2 = N + 1 + x
             for p_i in [p1, p2]:
                 if is_prime(p_i):
-                    H = hilbert_class_polynomial(-D)
+                    H = hilbert_class_polynomial(D) # -abs(D)
                     for j0, _ in H.roots(ring=GF(p_i)):
                         E = EllipticCurve(j=j0)
                         if E.order() == N: