Exercise 3¶

In [1]:
p = 424243
Fp = GF(p)
A = 323
In [2]:
E = EllipticCurve(Fp, [0, A, 0, 1, 0])
E
Out[2]:
Elliptic Curve defined by y^2 = x^3 + 323*x^2 + x over Finite Field of size 424243
In [3]:
# Define the generator
P = E(308951, 234702)
P
Out[3]:
(308951 : 234702 : 1)
In [4]:
# Define the point for which we want to find the discrete logarithm
Q = E(125565, 39963)
Q
Out[4]:
(125565 : 39963 : 1)
In [5]:
# Let's compute the solution, so we can use it to check what we are doing later on
solution = P.discrete_log(Q)
solution
Out[5]:
57
In [6]:
n = 2^5 * 5 # number of points (in the subgroup) on the curve
n
Out[6]:
160

Exercise 3a¶

In [7]:
# Here, we have to compute the discrete logarithm base 2^5
# Hence, we have p_i = 2
p_i = 2
In [8]:
Q_i = Q
a_ijminus1 = 0
n_i = n/p_i
In [9]:
# The image of P in the subgroup of order 2
R_i = n_i * P
R_i
Out[9]:
(0 : 0 : 1)

for-loop, iteration 0¶

In [10]:
j = 0
In [11]:
n_i = n/(p_i^(j+1))
In [12]:
Q_i = Q_i - (a_ijminus1*p_i^(j-1))*P

# The target for 2^0
Q_i
Out[12]:
(125565 : 39963 : 1)
In [13]:
S_i = n_i*Q_i
In [14]:
S_i, R_i
Out[14]:
((0 : 0 : 1), (0 : 0 : 1))

At this point, we need to solve the discrete logarithm $S_i=a_{2,0}R_i$. Filling in the points we just obtained, we get $$(0,0) = a_{2,0} (0,0)$$ Clearly, this holds when $a_{2,0}=1$.

In [15]:
# To check our results, we perform the following computation
a_ijminus1 = R_i.discrete_log(S_i)
a_ijminus1
Out[15]:
1
In [16]:
# As a sanity check, let us compute the correct result from the already-computed discrete logarithm.
Mod(solution, 2^1)
Out[16]:
1

for-loop, iteration 1¶

In [17]:
j = 1
In [18]:
n_i = n/(p_i^(j+1))
In [19]:
Q_i = Q_i - (a_ijminus1*p_i^(j-1))*P

# The target for 2^1
Q_i
Out[19]:
(338173 : 375090 : 1)
In [20]:
S_i = n_i*Q_i
In [21]:
S_i, R_i
Out[21]:
((0 : 1 : 0), (0 : 0 : 1))

At this point, we need to solve the discrete logarithm $S_i=a_{2,1}R_i$. Filling in the points we just obtained, we get $$P_\infty = a_{2,1} (0,0)$$ Clearly, this holds when $a_{2,1}=0$.

In [22]:
# To check our results, we perform the following computation
a_ijminus1 = R_i.discrete_log(S_i)
a_ijminus1
Out[22]:
0

for-loop, iteration 2¶

In [23]:
j = 2
In [24]:
n_i = n/(p_i^(j+1))
In [25]:
Q_i = Q_i - (a_ijminus1*p_i^(j-1))*P

# The target for 2^2
Q_i
Out[25]:
(338173 : 375090 : 1)
In [26]:
S_i = n_i*Q_i
In [27]:
S_i, R_i
Out[27]:
((0 : 1 : 0), (0 : 0 : 1))

At this point, we need to solve the discrete logarithm $S_i=a_{2,2}R_i$. Filling in the points we just obtained, we get $$P_\infty = a_{2,2} (0,0)$$ Clearly, this holds when $a_{2,2}=0$.

In [28]:
# To check our results, we perform the following computation
a_ijminus1 = R_i.discrete_log(S_i)
a_ijminus1
Out[28]:
0

for-loop, iteration 3¶

In [29]:
j = 3
In [30]:
n_i = n/(p_i^(j+1))
In [31]:
Q_i = Q_i - (a_ijminus1*p_i^(j-1))*P

# The target for 2^3
Q_i
Out[31]:
(338173 : 375090 : 1)
In [32]:
S_i = n_i*Q_i
In [33]:
S_i, R_i
Out[33]:
((0 : 0 : 1), (0 : 0 : 1))

At this point, we need to solve the discrete logarithm $S_i=a_{2,3}R_i$. Filling in the points we just obtained, we get $$(0,0) = a_{2,3} (0,0)$$ Clearly, this holds when $a_{2,3}=1$.

In [34]:
# To check our results, we perform the following computation
a_ijminus1 = R_i.discrete_log(S_i)
a_ijminus1
Out[34]:
1

for-loop, iteration 4¶

In [35]:
j = 4
In [36]:
n_i = n/(p_i^(j+1))
In [37]:
Q_i = Q_i - (a_ijminus1*p_i^(j-1))*P

# The target for 2^4
Q_i
Out[37]:
(339160 : 133756 : 1)
In [38]:
S_i = n_i*Q_i
In [39]:
S_i, R_i
Out[39]:
((0 : 0 : 1), (0 : 0 : 1))

At this point, we need to solve the discrete logarithm $S_i=a_{2,4}R_i$. Filling in the points we just obtained, we get $$(0,0) = a_{2,4} (0,0)$$ Clearly, this holds when $a_{2,4}=1$.

In [40]:
# To check our results, we perform the following computation
a_ijminus1 = R_i.discrete_log(S_i)
a_ijminus1
Out[40]:
1

Combining the results¶

In [41]:
# Our intermediate results were
a2_0 = 1
a2_1 = 0
a2_2 = 0
a2_3 = 1
a2_4 = 1

# Our final result is
a_2 = a2_0 + a2_1*2 + a2_2*2^2 + a2_3*2^3 + a2_4*2^4
a_2
Out[41]:
25
In [42]:
# As a sanity check, let us compute the correct result from the already-computed discrete logarithm.
Mod(solution, 2^5)
Out[42]:
25
In [43]:
# To verify our result, we compute (a_2)*(n/2^5)*P, and check whether this is equal to (n/2^5)*Q.
a_2 * (n/2^5)*P, (n/2^5)*Q, a_2 * (n/2^5)*P == (n/2^5)*Q
Out[43]:
((146249 : 144755 : 1), (146249 : 144755 : 1), True)
Hence, we get that $a\equiv 25\mod 2^5$.

Exercise 3b¶

In [44]:
# Here, we have to compute the discrete logarithm base 5
# Hence, we have p_i = 5
p_i = 5
In [45]:
Q_i = Q
a_ijminus1 = 0
n_i = n/p_i
In [46]:
R_i = n_i * P

# The image of P in the subgroup of order 5
R_i
Out[46]:
(80722 : 1884 : 1)

for-loop, iteration 0¶

In [47]:
j = 0
In [48]:
n_i = n/(p_i^(j+1))
In [49]:
Q_i = Q_i - (a_ijminus1*p_i^(j-1))*P

# The target for 5
Q_i
Out[49]:
(125565 : 39963 : 1)
In [50]:
S_i = n_i*Q_i
In [51]:
S_i, R_i
Out[51]:
((405809 : 261409 : 1), (80722 : 1884 : 1))
In [61]:
for i in range(5):
    print(str(i)+ "*R_i gives", str(i*R_i))

0*R_i gives (0 : 1 : 0)
1*R_i gives (80722 : 1884 : 1)
2*R_i gives (405809 : 261409 : 1)
3*R_i gives (405809 : 162834 : 1)
4*R_i gives (80722 : 422359 : 1)

At this point, we need to solve the discrete logarithm $S_i=a_{5,0}R_i$. Filling in the points we just obtained, we get $$(0,0) = a_{5,0} (0,0)$$ Clearly, this holds when $a_{5,0}=1$.

In [52]:
# To check our results, we perform the following computation
a_ijminus1 = R_i.discrete_log(S_i)
a_ijminus1
Out[52]:
2
In [53]:
# As a sanity check, let us compute the correct result from the already-computed discrete logarithm.
Mod(solution, 5)
Out[53]:
2

Verifying the result¶

In [54]:
a_5 = a_ijminus1
In [55]:
# To verify our result, we compute (a_2)*(n/5)*P, and check whether this is equal to (n/5)*Q.
a_5 * (n/5)*P, (n/5)*Q, a_5 * (n/5)*P == (n/5)*Q
Out[55]:
((405809 : 261409 : 1), (405809 : 261409 : 1), True)

Exercise 3c¶

In [56]:
a = CRT([25, 2], [2^5, 5])
a
Out[56]:
57
In [57]:
# To verify our result, we compute a*P, and check whether this is equal to Q.
a*P, Q, a*P == Q
Out[57]:
((125565 : 39963 : 1), (125565 : 39963 : 1), True)