Problem 4
Here is the curve $E(\mathbb{F}_p)$ and its order.
{{{id=1|
p = 1461501637330902918203684832716283019655973349331
E = EllipticCurve(GF(p),[1,0])
n = E.count_points()
factor(n)
///
2^2 * 3 * 41 * 2970531783192892110170091123407079308243848271
}}}
Here are two points $P$ and $Q$ on $E(\mathbb{F}_p)$ with $Q = [a]P$.
{{{id=2|
P = E(916695884547111349904583025841061270186986038721,
580841286046155102637492926195177127992061729856)
Q = E(1299635880259853636262044538415126323429627504320,
1120139906107476246466144743069490058897077692330)
///
}}}
Value of $a$ mod the largest factor of $\#E(\mathbb{F}_p)$.
{{{id=3|
t = 2970531783192892110170091123407079308243848271 # largest factor of #E(F_p)
s = 1864316221141791753837087178908449374069570910 # value of a mod t
///
}}}
Problem 6
In this problem you will implement some variants of Pollard's rho method. We will use the following elliptic curve and points.
{{{id=4|
p = 1048583
E = EllipticCurve(GF(p),[183801, 823458])
P = E(580655,963078)
Q = E(774292,954498)
///
}}}
The following function takes the two points $P$ and $Q$ in the discrete log problem and returns a random walk function. (Note that in SAGE/Python functions can pass and/or return other functions.)
{{{id=5|
def walk_setup(P,Q):
'''Compute a random walk function on E using 16 partitions.'''
s = 16 # number of partitions
A = [randint(1,P.order()) for i in range(s)]
B = [randint(1,P.order()) for i in range(s)]
PP = [A[i]*P+B[i]*Q for i in range(s)]
# We define our random walk function
def walk(T):
'''Random walk function using parameters A,B,PP defined above.
Input is a tuple T of the form T = (R, u, v), where R = u*P + v*Q.
Output is of the same form, with updated values (R',u',v').
'''
# Choose partition by lifting x-coordinate to integers and reducing mod s
k = ZZ(T[0][0])%s
# Apply the walk function for the kth partition, keeping track of multipliers of P and Q
return (T[0]+PP[k],T[1]+A[k],T[2]+B[k])
return walk
///
}}}
The following function implements Pollard's rho method in a naive way: at each step in the pseudorandom walk we store the computed point in a list and search the list for a collision. While this is the fastest way to find a collision, it is space-intensive.
Note that instead of using a Python list structure we use a dictionary structure, which allows for faster searching. See the Python tutorial for details.
{{{id=8|
def collision_search(P,Q):
'''Use the walk function to choose random points on E until a collision is found.
output the discrete log of Q to the base P and the number of times the walk function is called.
'''
# Choose a random starting point P0; initialize u0, v0.
b = randint(1,P.order())
P0,u0,v0 = b*P,b,0
# Set up the pseudorandom walk function
walk = walk_setup(P,Q)
X = (P0,u0,v0) # first input to walk
i = 0 # number of steps in the walk
D = {} # list of points computed; we use a dictionary instead of a list for speed
while(True):
X = walk(X) # step through the walk
i += 1
if X[0] in D: # we found a collision
u1,v1 = X[1],X[2] # u and v values of the current point
u2,v2 = D[X[0]] # u and v values of the collided point
a = ((u1-u2)/(v2-v1)) % P.order() # compute the discrete log
return a,i
else:
D[X[0]] = (X[1],X[2]) # store u and v in the dictionary at index X[0]
///
}}}
{{{id=9|
collision_search(P,Q)
///
}}}
(a)
{{{id=10|
def floyd_rho(P,Q):
'''Compute discrete log using Floyd cycle finding.'''
# Initialize as above.
# Repeat until P_i = P_{2i}
# Compute P_{i+1} and P_{2i+1}
# Output the discrete logarithm and the total number of times the walk function is called.
///
}}}
{{{id=11|
floyd_rho(P,Q)
///
}}}
(b,c)
{{{id=12|
def distpt_rho(P,Q,d):
'''Compute discrete log of Q to the base P using distinguished points.
1/d = probability of hitting a distinguished point'''
# Initialize as above.
while(True):
# Iterate the random walk
# Test for distinguished points
if ZZ(x)%d == 0: # here x is the x-coordinate of P_i
# if P_i is in the list:
# output the discrete log, number of distinguished points, and number of calls to walk.
# else:
# Store P_i,u_i,v_i in a list (or dictionary).
else:
# (for part (c)): make sure we're not in a useless cycle
///
}}}
{{{id=13|
distpt_rho(P,Q,32)
///
}}}
(d)
Compute the average number of calls to walk in each of the three algorithms above over 1000 trials.
{{{id=14|
///
}}}
{{{id=28|
///
}}}