Question about Novotney's paper on Weak Curves

Question

This is the paper - https://wstein.org/edu/2010/414/projects/novotney.pdf

In Section 2.1

I see 2 chunks of code/commands in SageMath

sage: #Group Order Compare SLOW
sage: m = 21345332
sage: p = 4516284508517
sage: E = EllipticCurve(GF(p), [7,1])
sage: Q = E.gens()[0]
sage: mQ = m*Q;
sage: print E.order().factor()
sage: time mRec = PolligHellman(Q,mQ)
sage: print mRec
11 * 13 * 31582419389 
Time: CPU 49.14 s, Wall: 49.14 s
21345332

sage: #Group Order Compare FAST
sage: m = 21345332
sage: p = 4516284508517
sage: E = EllipticCurve(GF(p), [7,1])
sage: Q = E.gens()[0]
sage: mQ = m*Q;
sage: print E.order().factor()
sage: time mRec = PolligHellman(Q,mQ)
sage: print mRec
2^3 * 19 * 23 * 67 * 2089 * 18913
Time: CPU 0.16 s, Wall: 0.16 s
21345332

E seems to be the same in both cases - but E.order.factor() is different. How can that happen?

I see this pdf referred to here also - http://koclab.cs.ucsb.edu/teaching/ecc/project/2015Projects/Sommerseth+Hoeiland.pdf

From Page 3

the article ”Weak Curves InElliptic Curve Cryptography” written by Novotney.He looks at the elliptic curve E:y2=x3+ 7x+ 1and Galios Field over prime p= 4516284508517: When the order of the point P is 4516285972627 it has the prime factors 11·13·31582419389.
Solving the ECDLP with Pohlig-Hellman takes 49.14 seconds. When the order of the point P is 9254332285624 it has the prime
factors 2^3·19·23·67·2089·18913.
Solving the ECDLP with the same Pohlig-Hellman code takes 0.16 seconds.

9254332285624 = 2^3 * 19 * 23 * 67 * 2089 * 18913

So both are the same thing.

So - is it really E.order() or P.order()

How do I get the points which have the order 9254332285624 &

I tried this in sage

p = 4516284508517
E = EllipticCurve(GF(p), [7,1])
P = E.gens()[0]

print (E.order())
4516285972627

print (P.order())
4516285972627

How do I get the point for which the order is 9254332285624?

Answer 1

There is obviously missing information on both lecture projects. With a small try, I've found a curve with the required order.

If you set the field as the prime field $F_P$ where $p=9254331510119$, the curve

$$E(F_p) : y^2 = x^3 + 7x + 1$$

p = 9254331510119
E = EllipticCurve(GF(p), [7,1])
print(E.order().factor())

outputs

$$9254332285624 = 2^3 \cdot 19 \cdot 23 \cdot 67 \cdot 2089 \cdot 18913$$ as required.

---

Actually, I was lucky since I simply started 9254332285624-1000000 and I did not use the Hasse bound

$$|N - (q+1)| \le 2 \sqrt{q}$$ where $N$ is the number of point on the curve, here $N= 9254332285624$, and $q$ is the number of elements of the finite field, here we have the prime field $F_p$. With removing the absolute value we have this form

$$q+1-2{\sqrt q} ≤ N ≤ q+1+2{\sqrt q}$$

$$q+1-2{\sqrt q} ≤ 9254332285624 ≤ q+1+2{\sqrt q}$$

and calculating

$$9254332285625 - 4 \sqrt{2313583071406} \leq q \leq 9254332285625 + 4 \sqrt{2313583071406} $$

$$9254326201438 < q < 9254338369812$$

So, if you seek the primes in the above range ( possibly with a next_prime function of SageMath) you will definitely find your candidate primes, which are expected little ( exactly 407391 primes on this range) to satisfy the required curve order.

---

The SageMath code with Hasse Bound;

expected_order = 2^3 * 19 * 23 * 67 * 2089 * 18913

#This is specific to this order!
start = floor(expected_order - 4 * sqrt(expected_order/4))
end   = floor(expected_order + 4 * sqrt(expected_order/4))

p = start -1

primeCount = 0

for x  in range(start,end):
    p = p.next_prime()
    primeCount = primeCount + 1
    if p > end:
        break
        
    E = EllipticCurve(GF(p), [7,1])
    
    if E.order() == expected_order:
        print ( p)
        break
    
print("Finished")
print("Number of tested primes =", primeCount)

and the output;

9254331510119
Finished
Number of tested primes = 177222