1
$\begingroup$

I am currently doing the elliptic curves and I'm stuck for 8 hours without finding solutions. I under stand the process of double and add but don't know how to obtain 5 * 8P = 4OP =11 P. 11 P was in the answers my teacher gave me please someone help.

enter image description here

$\endgroup$
5
  • $\begingroup$ Curve order is prime with $n=19$. Does this tells you something like $[19]P=$ ? $\endgroup$
    – kelalaka
    Commented Nov 2, 2023 at 17:02
  • $\begingroup$ $40 P \ne 11 P$. Is it possible that the problem actually was $5 \cdot 6P$? $30P = 11P$ $\endgroup$
    – poncho
    Commented Nov 2, 2023 at 17:05
  • $\begingroup$ @kelalaka pleaseee help me.It doesn’t give any explanation at my book… Understanding cryptography is the name check if you don’t believe me $\endgroup$
    – Stefan
    Commented Nov 2, 2023 at 17:18
  • $\begingroup$ @poncho it’s actually 5*8P=40P $\endgroup$
    – Stefan
    Commented Nov 2, 2023 at 17:19
  • $\begingroup$ Yes, poncho is right. I was expecting you to see that. $[n]P = \mathcal{O}$ where $n$ is the order of the $P$, in your case it is explicit $=19$. There is a mistake on the text. $\endgroup$
    – kelalaka
    Commented Nov 2, 2023 at 18:39

1 Answer 1

3
$\begingroup$

The points of an elliptic curve forms an abelian group under the usual point addition. In finite field case, the order is finite, i.e. the curve has finite number of points. The order can be prime or composite. In your case it is prime with 19. Primes means that every element, except the identity element $\mathcal{O}$, has order 19, therefore we can say $[19]P = \mathcal{O}$. By using this, we can say that $[t]P = [t \bmod 19]P$. By using this we can see that

$$[30]P = [30 \bmod 19]P = [11]P,$$ and $$[40]P = [40 \bmod 19]P = [2]P$$

Therefore we can conclude that, to have the result $[11]P$ we need 30.

We can verify this using SageMath. Here is SageMath terminal calculation:

K = GF(17)

E = EllipticCurve(K, [0,0,0,2,2])
print(E)

q = E.order()
print("Order of Curve = ",q )

P = E([5,1])

print("11 * P = ", 11 * P)
print("30 * P = ", 30 * P)
print("40 * P = ", 40 * P)
print("2 * P  = ", 2 * P)

assert( 11*P ==  30 *P )

with output;

Elliptic Curve defined by y^2 = x^3 + 2*x + 2 over Finite Field of size 17
Order of Curve =  19
11 * P =  (13 : 10 : 1)
30 * P =  (13 : 10 : 1)
40 * P =  (6 : 3 : 1)
2 * P  =  (6 : 3 : 1)

You can test it yourself here. As a result, as @poncho already mentioned, the exercise may be wrong and $5 \cdot 6P \equiv 30 P \equiv 11P$ makes more sense.

$\endgroup$
4
  • 1
    $\begingroup$ It is better to use SageMathCell with permanent link. It is better to include that $[40]P=[2]P$, too. $\endgroup$
    – kelalaka
    Commented Nov 2, 2023 at 19:01
  • $\begingroup$ Indeed I’m gonna mention it to my professor.thanks for your help.Have a nice day $\endgroup$
    – Stefan
    Commented Nov 2, 2023 at 19:20
  • $\begingroup$ @kelalaka Awesome! Didn't know SageMathCell exists. Thank you! $\endgroup$
    – Titanlord
    Commented Nov 2, 2023 at 19:25
  • 1
    $\begingroup$ @Stefan don't forget to accept and upvote. $\endgroup$
    – kelalaka
    Commented Nov 2, 2023 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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