2
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ There should be a typo. Contact the author? $\endgroup$
    – kelalaka
    Apr 19 at 13:04
  • $\begingroup$ @kelalaka How to contact him - No contact info is given in the PDF. I came across this while looking for some sample EC DLP problems to try out Pohlig Hellman on. The paper itself is not important for me, but the point who co-ordinates are missing is. $\endgroup$
    – user93353
    Apr 20 at 1:38
  • $\begingroup$ What were you need to look at where the Novotey paper is published. Search for Peter Novotney University of Washington. $\endgroup$
    – kelalaka
    Apr 20 at 18:53
3
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.