# Elliptic curve discrete logarithm problem and mini example

Consider the group E23(9,17), this the group defined by the equation y2 mod 23 = x3 + 9x + 17 mod 23. What is the discrete logarithm k of Q = (4,5) to the base P = (16,5)?

the solution is: 2P = (20,20), 3P = (14,14), 4P = (19,20), 5P = (13,10), 6P = (7,3), 7P = (8,7), 8P = (12,17), 9P = (4,5) = Q k = 9

i need the detail arithmetic method that explain this result please

• What issue is there applying the point doubling and point addition formulas? – fgrieu May 16 '18 at 17:26
• Which part of the solution do you not understand? Do you not know what a discrete log is? Or do you not know how point addition works? – Alex May 16 '18 at 17:27
• This looks like homework/test preparation on which not enough effort has been spent. In fact, I am giving a class test tonight covering elliptic curve arithmetic where this type of question is typical :-) – kodlu May 16 '18 at 21:43
• exactly Alex I did not know how point addition t work – mhmad nkrash May 17 '18 at 11:33

Thanks every body the idea is completed By refer To the reference Cryptography and Network security first edition page 196 --- 198

The solution is: We have to compute additive multiple of P until Q is founded thus we should calculate 2P,3p,4P,5P….. until Q is founded.

p(16,5) First I compute 2p=R(X_r,Y_r)

S=(3〖〖*X〗_p〗^2+a)/(2Y_p )=(3〖*16〗^2+9)/(2*5) Modulo 23= 777/10 modulo 23

1/10 modulo 23=7

S=777*7 modulo 23=11

X_r=S^2-2*X_p=〖11〗^2-2*16=121-32=89 modulo 23=20

Y_r=S(X_p-X_r )-Y_p=11(16-20)-5=-49 modulo 23=20

We can compute 3p by add p(16,5)To 2p(20,20)

but I will compute 4p by duplicate 2p(20,20)

S=(3〖〖*X〗_p〗^2+a)/(2Y_p ) =(3〖*20〗^2+9)/(2*20) Modulo 23 = 1209/40 modulo 23=1209*1/4*〖10〗^(-1) modulo 23

1/10 modulo 23=7

1/4 modulo 23=6

S=1209*7*6 modulo 23=17

X_r=S^2-2*X_p=〖17〗^2-2*20=289-40=249 modulo 23=19

Y_r=S(X_p-X_r )-Y_p=17(20-19)-20=-3 modulo 23=20

Also We can compute 5p by add p(16,5)To 4p(19,20)

but I will compute 8p by duplicate 4p(19,20)

S=(3〖〖*X〗_p〗^2+a)/(2Y_p ) =(3〖*19〗^2+9)/(2*20) Modulo 23 = 1092/40 modulo 23 =1092*1/4*1/10 modulo 23

1/10 modulo 23=7 1/4 modulo 23=6

S=1092*7*6 modulo 23=2

X_r=S^2-2*X_p=2^2-2*19 =4-38=-34 modulo 23=12

Y_r=S(X_p-X_r )-Y_p =2(19-12)-20=-6 modulo 23=17

Now I will compute 9 P by add P(16,5) To 8p(12,17)

S=(Y_q-Y_p)/(X_q-X_p ) =(17-5)/(12-16)=12/(-4) =-12*1/4 modulo 23=-12*6 modulo 23=20 1/4 modulo 23=6

X_r= S^2-X_p-X_q =〖20〗^2-16-12=400-28 =372 modulo 23=4

Y_r=S(X_p-X_r )-Y_p =20(16-4)-5 =235 modulo 23=5

9P=(4,5)=Q So the discrete logarithm of Q(4,5) based on P (16,5) over Elliptic curve E_23=(17,9) is Q=9P