Elliptic curve discrete logarithm problem and mini example [closed]

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, 2018 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?
– NNN
May 16, 2018 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 :-) May 16, 2018 at 21:43
• exactly Alex I did not know how point addition t work May 17, 2018 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

Here an example using c++:

#include <iostream>

struct Point {
int x;
int y;
};

// Elliptic curve parameters
const int a = 9;
const int p = 23;

// Addition of two points on the elliptic curve
Point addPoints(const Point& p1, const Point& p2) {
int lambda, x3, y3;

if (p1.x == p2.x && p1.y == p2.y) {
// Doubling a point
lambda = (3 * p1.x * p1.x + a) * inverseMod(2 * p1.y, p) % p;
} else {
lambda = (p2.y - p1.y) * inverseMod(p2.x - p1.x, p) % p;
}

x3 = (lambda * lambda - p1.x - p2.x + 2 * p) % p;
y3 = (lambda * (p1.x - x3) - p1.y + 2 * p) % p;

return {x3, y3};
}

// Scalar multiplication of a point on the elliptic curve
Point scalarMultiply(const Point& p, int scalar) {
Point result = {0, 0};

while (scalar > 0) {
if (scalar & 1) {
}

scalar >>= 1;
}

return result;
}

// Calculate the inverse of a number modulo p
int inverseMod(int num, int p) {
int t = 0, r = p, new_t = 1, new_r = num;

while (new_r != 0) {
int quotient = r / new_r;
int temp_t = t;
t = new_t;
new_t = temp_t - quotient * new_t;

int temp_r = r;
r = new_r;
new_r = temp_r - quotient * new_r;
}

if (t < 0) {
t += p;
}

return t;
}

int main() {
Point P = {16, 5};
Point Q = {4, 5};
int k = 1;

while (true) {
Point kP = scalarMultiply(P, k);

if (kP.x == Q.x && kP.y == Q.y) {
break;
}

k++;
}

std::cout << "Discrete logarithm of Q to the base P is: " << k << std::endl;

return 0;
}

• Welcome to Cryptography.se. This is not a place to answer only in codes. We presents code to illustrate the idea. Even Stack Overflow code only answer are not welcomed without explanations... Jun 23, 2023 at 16:51