2018-02-16.ipynb

Kernel: SageMath 8.1

Math 157: Intro to Mathematical Software

UC San Diego, winter 2018

Homework 5: due February 16, 2018

Please enter all answers within this notebook unless otherwise specified. As usual, don't forget to cite sources and collaborators.

Through this problem set, use the SageMath 8.1 kernel. Tips:

• You can use preparser(False) to turn off the Sage preparser (e.g., to avoid issues with pandas) and preparser(True) to turn it back on.

• To avoid issues with CoCalc, don't forget to delete temporary files.

• Run the following imports before executing cells using numpy or pandas.

import numpy as np
import pandas as pd

Problem 1: Distances between cities

Grading criteria: correctness of code.

1a. Retrieve the CSV version of the Zip Code Database, upload it into your project, and import it into a DataFrame.

1b. Import the Excel file "state_capitals.xlsx" (sourced from Wikipedia, found in this directory) into a DataFrame.

1c. Construct a new DataFrame in which each row consists of:

• the name of a state;

• the two-letter postal abbrevation of the state;

• the name of the capital city;

• a list of the zip codes associated to that city;

• the latitude and longitude associated to the first zip code in the list.

Problem 2: Minimum spanning trees

Grading criteria: correctness of code. Note: you will need to reference your answer to problem 1, but this problem will be graded independently (i.e., as if your answer to problem 1 is correct, whether it is or not).

William Stein announces the formation of CoCalc Fiber, a new broadband network which will connect the capital cities of the 48 continental United States (excluding Alaska and Hawaii) with a series of underground cables joining certain pairs of cities. Naturally, William wants to minimize the cost of building this network; he assumes that the cost of building a network link between some pairs of cities is proportional to the distance between those two cities.

2a. Define a function that implements the haversine formula: given two latitude-longitude pairs, compute the distance between those two points on Earth. Use kilometers instead of miles, because the US was supposed to convert to the metric system in 1975. Check your formula by computing the distance between New York City and San Diego, as reported by the Great Circle Mapper web site.

2b. Construct a complete graph in which each vertex is labeled by the name of a state, and each edge is labeled by the distance between the capital cities.

2c. Construct the minimal spanning tree corresponding to the optimal CoCalc Fiber network.

2d. William decides to scale back his plans and connect only the Western states (meaning Montana, Wyoming, Colorado, New Mexico, and all continental states west of these). Furthermore, he is now only going to build links between states which are adjacent (meaning that they share a land border, not just a corner); and all city pairs will now be treated as costing the same amount. Construct the minimal spanning tree corresponding to the optimal network.

Problem 3: "Year-old bug ruined crypto!"

Grading criteria: correctness of code and explanations.

The article "Socat slams backdoor, sparks thrilling whodunit -- Year-old bug ruined crypto" is about a potential backdoor in some networking software called Socat, in which "the SSL implementation uses a non-prime number as its Diffie-Hellman $p$-parameter". See also Socat? What? (timeline of events).

3a. Using the Chinese remainder theorem, explain what the problem is with using a nonprime parameter in Diffie-Hellman.

3b. The parameter $p$ in the Socat story is defined below. Use the trial_division function to find all prime factors of $p$ less than $10^6$.

p = 143319364394905942617148968085785991039146683740268996579566827015580969124702493833109074343879894586653465192222251909074832038151585448034731101690454685781999248641772509287801359980318348021809541131200479989220793925941518568143721972993251823166164933334796625008174851430377966394594186901123322297453

3c. One theory that was floated about the Socat story is that the parameter $p$ had suffered from a transcription error, e.g., there is a prime that differs from $p$ in one decimal digit and this was what was intended. Write code to find all such primes. (Do not allow substituting a 0 for the leading digit.)

3d. Repeat 3c but with binary digits instead of decimal digits.

Problem 4: A backdoor to factoring

Grading criteria: correctness of code and explanations.

4a. Explain, in your own words, the backdoor to factoring being described in this quote. (This topic is treated in more detail in Math 187B.)

"We performed a large-scale study of RSA and DSA cryptographic keys in use on the Internet and discovered that significant numbers of keys are insecure due to insufficient randomness. We found that 5.57% of TLS hosts and 9.60% of SSH hosts share public keys in an apparently vulnerable manner..." -- see https://factorable.net/

4b. Use this backdoor to factor the numbers $a$ and $b$ defined below.

a = 659481018095533082202091938200108415755014729057676791347712890248315591033900561408617722880031918351642894659648847446299804878752991957454382452262126117247899544055830787469355702640917

b = 223986669883088680371243199849357901244618017803455583407479556994195127176620839487674896299802613306139834600384565144314609009904613010988914195091967322701239166323910725912324556645705719757

4c. Compare the size of $a$ and $b$ to the current state of the RSA Factoring Challenge. Would it have been feasible to factor them without the backdoor?

Problem 5: Primitive roots

Grading criteria: correctness of code and explanations.

5a. Look up, then formulate in your own words, the statement of Artin's conjecture on primitive roots.

5b. Compute, to at least five decimal places, the prediction made by Artin's conjecture for the probability that 2 is a primitive root modulo a random prime $p$.

5c. Write a function that, given an input $n$, computes the probability that 2 is a primitive root modulo a random prime less than $n$.

5d. Make a plot of your answer to 5c for $n$ up to at least $10^6$, with at least 10 sample points (of your choice). Use a logarithmic scale on the $x$-axis.

Problem 6: Graphs and number theory

Grading criteria: correctness of code.

6a. Read the definition of a Paley graph, then write a function that, given a prime $p$ congruent to 1 modulo 4, constructs the Paley graph associated to that prime. (There also exist Paley graphs associated to prime powers, but your function need not construct those.)

6b. Using your answer to 6a for $p=13$ and the Paley construction, construct (but do not print) a $28 \times 28$ matrix which achieves the Hadamard determinant bound.

6c. Check that your answer to 6b actually does achieve the Hadamard bound.