Task 1:
Write a function ECtest(A,B,p)
that tests if y^2 = x^3 + Ax + B is an elliptic curve
mod p. That is, return True if the discriminant is nonzero
mod p, and False otherwise.
Task 2:
Write a function ECpoints(A,B,p)
that returns a list of all points (x,y)
on the curve y^2 = x^3 + Ax + B mod p. Include the point
at infinity O represented as the pair (0,-1).
Task 3:
Write a function ECorders(p)
that runs through all (Weierstrass) elliptic curves modulo
a prime p and returns a list consisting of their orders. Here
the order of an elliptic curve means the number of points.
Task 4:
Write a function ECaverageorder(p)
that returns the average order of a (Weierstrass) elliptic
curve mod p.
Task 5: For primes p between 5 and 50, count the number of elliptic curves mod p, determine their average order, and upper and lower bounds on their order (for a given p). Can you predict the behavior of these quantities for arbitrary p > 3.
Task 6:
Write a function ECadd(P,Q,A,B,p) which returns the sum
of two points P=(x1,y1) and Q=(x2,y2) on the
elliptic curve y^2 = x^3+Ax+B mod p. You can use my
code for inversion mod p.
If your algorithm fails because
something is not invertible mod p, return that number.
Check your code with A=B=4 and p=59 to make sure you get the following sums:
Also check with with A=B=4, p=55 and P=(1,3), Q=(45,3). This should fail because 11 is not invertible mod 55 and return the number 44.
Note: you can test if the output of this function is a point rather than
a number with the code if type(R) == type((0,0)) where
R = ECadd(P,Q,A,B,p).
Task 7:
Write a function ECPorder(P,A,B,p) to find the order of the
point P=(x,y) on the elliptic curve y^2 = x^3+Ax+B mod p.
If your algorithm fails because
something is not invertible mod p, return that number.
Task 8: Consider the elliptic curve E given by y^2=x^3+4x+4 with the point P=(1,3). Compute the order of P on E mod p=47. Compute the order of P on E mod q=59. Try to compute the order of P on E mod n=pq=2773, explain why this fails, and how this failure leads to the factorization n=pq.
Task 9: Using the elliptic curve E and the point P from the previous task, factor n=42857766101 by trying to compute the order of P mod n.