Math 157辅导、讲解CS/python语言、讲解java/c++编程、辅导Mathematical Software

A11-20-18

November 19, 2018

0.1 Math 157: Intro to Mathematical Software

0.2 UC San Diego, fall 2018

0.3 Homework 7: due November 20, 2018

Please enter all answers within this notebook. As usual, don’t forget to cite sources and collaborators.

Throughout this problem set, use the SageMath (stable) kernel.

0.3.1 Problem 1: Elliptic curve Diffie-Hellman

Grading criteria: correctness of code.

1a. The following code defines an elliptic curve over Fp for a certain prime p. This has the

structure of an abelian group; compute the order of this group.

In [1]: p = Primes().next(650101087)

E = EllipticCurve(GF(p), [0,1,0,1,-1])

1b. Check that the following element is a generator.

In [0]: g = E(108964023, 615592367)

1c. Using E, g, and the secrets a and b defined below, perform the analogue of a Diffie-Hellman

key exchange. You should show how Alice computes the shared secret, how Bob computes the

shared secret, and check that they get the same answer. (Hint: remember that the analogue of

modular multiplication is denoted by addition, and that the analogue of exponentiation g?n is

denoted n*g.)

In [0]: a = 54087872 # Alice's secret

b = 29136533 # Bob's secret

0.3.2 Problem 2: Attacking elliptic curve Diffie-Hellman

Grading criteria: correctness of code.

Throughout this problem, use the same elliptic curve and generator as in problem 1.

2a. Take the code given in lecture (on 11-07) for the baby-step giant-step method for computing

discrete logarithms, and adapt it to this elliptic curve. To test your function, check that on input

"E(471134727, 23460382)" it outputs "157".

1

In [0]: def bs_gs(g, A):

# Step 1

m = floor(sqrt(g.multiplicative_order())) # Compute m

# Step 2

small_g_powers = {g^e:e for e in range(m)} # Make a list of the small powers of g

# Step 3

gpow = A # Initialize gpow with the given value A

mult = g^(-m)

for f in xrange(m):

if gpow in small_g_powers: # If gpow is in our list of small powers

return small_g_powers[gpow]+f*m # We are done!

gpow *= mult # Other wise, move on to the next f value

2b. Using your function from 2a, determine Alice and Bob’s shared secret using only the public

information given below. You should compute this secret in two different ways - once from Alice’s

perspective and once from Bob’s - and check that they agree.

In [0]: A = E(209288576, 240251595) # Alice's public value, computed using her secret

B = E(195168995, 549448815) # Bob's public value, computed using his secret

In [0]:

0.3.3 Problem 3: The Sato-Tate conjecture, data collection

Grading criteria: correctness of code.

3a. Define the elliptic curves E1 : y

2 = x

3 + x ? 1, E2 : y

2 = x

3 + x, E3 : y

2 = x

3 + x + 1, and

E4 : y

2 = x

3 + x + 2 in Sage. For each curve Ei

, find the smallest prime p greater than 3 such that

Ei has exactly p + 1 points when reduced mod p.

In [0]:

3b. Given an elliptic curve Ep over a finite field Fp, define Np to be the number of Fp-points on

Ep and define cp to be the quantity Np?(p+1)

2

√

p+1

. Hasse’s theorem says that we always have |cp| ≤ 1.

Write a function which takes as input an elliptic curve E with integer coefficients and a prime p,

reduces E modulo p to get an elliptic curve Ep defined over Fp, and returns cp. If E doesn’t reduce

modulo p to get an elliptic curve (i.e., if Sage gives an error when you try to change the ring), your

function shouldn’t output anything.

For example, the curve E : y

2 = x

3 + x + 1 has 4 points over F3. Your function should therefore

return 0 on input "E, 3". The elliptic curve isn’t defined over F2, so it should have no output on

input "E, 2". Note that by Hasse’s theorem, your output should always fall between -1 and 1.

In [0]: def Hasse(E, p):

# Your code here

3c. Make a pandas DataFrame with 4 columns, corresponding to the 4 curves defined in 3a,

and 1000 rows, corresponding to the first 1000 primes. The entry of the DataFrame corresponding

to the curve Ei and the prime p should have the value Hasse(E_i, p), stored as a float.

In [0]:

2

0.3.4 Problem 4: The Sato-Tate conjecture, data analysis

Grading criteria: correctness of code and thoroughness of analysis.

4a. For each of the four elliptic curves Ei defined in problem 3a, write down all of the first 1000

primes for which the reduction of Ei mod p isn’t an elliptic curve.

In [0]:

4b. For each of the four elliptic curves Ei defined in problem 3a, compute the percentage of the

first 1000 primes for which the reduction of Ei mod p is an elliptic curve with exactly p + 1 points.

In [0]:

4c. For each of the four elliptic curves Ei defined in problem 3a, make a histogram containing

the values cp for the first 1000 primes.

In [0]:

4d. The Sato-Tate conjecture (now a theorem in the case we are looking at) says that for any

elliptic curve E, as N goes to infinity, there are only two possible distributions for the values of cp

- the ones exhibited by these curves.

What do you think these distributions are, and which do you think is more common? It may

help to try some more examples.

0.3.5 Problem 5: Sunspots

Grading criteria: correctness of code and results.

Let sunspots be the sunactivity dataframe (defined below for you).

In [0]: from statsmodels import datasets

sunspots = datasets.sunspots.load_pandas().data.set_index("YEAR")

5a. For how many years was the activity ≥ 100?

In [0]:

5b. Make a histogram plot of all activity from 1900 to the end of the dataset.

In [0]:

5c. Which year(s) had the highest activity?

In [0]:

3

0.3.6 Problem 6: Irises

Grading criteria: correctness of code and explanations.

The iris dataset is a famous example used in statistics education. Run the following block of

code to download the iris dataset into a pandas dataframe.

In [0]: import seaborn as sns

iris = sns.load_dataset('iris')

6a. Describe in words in as much detail as you can what the iris dataset contains. How many

samples are in the data set, and what is being sampled?

6b. Plot all of the sepal (length, width) pairs in a scatterplot, and the petal (length, width) pairs

in another scatterplot.

In [0]:

6c. Compute the average petal width for each of the "species"-categories.

In [0]: