2018-02-23.ipynb

Kernel: SageMath 8.1

Math 157: Intro to Mathematical Software

UC San Diego, winter 2018

Homework 6: due February 23, 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 except as specified.

This homework consists of 5 problems, each of equal value.

Problem 1: The birthday paradox (and comedy)

Grading criteria: correctness of code and thoroughness of explanations.

1a. A well-known statement of mathematical folklore asserts that if you choose $N$ people at random, then the probability that two of them have the same birthday exceeds 50% as soon as $N \geq 23$. This is sometimes called the birthday paradox not because of any logical inconsistency, but simply because people find this counterintuitive; a more accepted terminology is the birthday problem.

Write a function that, given $N$, computes this probability. For simplicity, you may assume that every year consists of 365 days (i.e., ignore leap years) and that birthdays are distributed uniformly at random.

1b. Verify numerically that the probability exceeds 0.5 if and only if $N \geq 23$.

1c. If a year were to consist of $M$ days, how would the crossover value depend (asympotically) on $M$? Why?

1d. Explain, in your own words, what the following three things have in common.

• The birthday problem.

• The baby-step-giant-step attack on discrete logarithms.

• The mathematical theory of late-night comedy reported by Slate last week. (Not a joke!)

Problem 2: Chinks in the armor

Grading criteria: correctness of code and mathematical reasoning.

2a. There exist two primes $p$ and $q$ such that $N = pq$ and $\varphi(N)$ have the following values. Find $p$ and $q$.

N = 46708822349259203361344297606349795508624596894610331963475250447878049614343188469958138667702672064437158794030506161936018920993393470466541259138024527655091597122885936534640983967743981020417066596244043571854706943422478922714341547167502363866097396753119154853150662020146962118536726679429506821989
ph = 46708822349259203361344297606349795508624596894610331963475250447878049614343188469958138667702672064437158794030506161936018920993393470466541259138024513978876893776281066371789960571608641635171633767722385559809330963145405657507385159096521621672648416769760458924356578637127097073558518163200222200556

2b. The following integer $N$ is a product of two primes of roughly equal size (which are known to me but secret to you). The integer $t$ given below has the property that $M^3 \equiv t \pmod{N}$ for some positive integer $M$ not greater than $10^{105}$. Find $M$.

N = 76423640358847412652374294300302041459529359752680987485518411448531451335119684258103920661719583680308606457161396261605016691913851993440982486450916973319097247600145790676526404213081447781619033665382062984788563242010572490285667221071318294609426838188283710453878988160806557791285882029204772981529
t = 11807826974296406142491583468052817190645455044270507694732514014928570915157636104659010509935579145791187971616680786969637105700382114579562649014536639676091007952025381665220916825703280184232877376453652231909120222974982306195030361794694545267682687918232040294524659748461552986872564797138673247308

Problem 3: Elliptic curve Diffie-Hellman

Grading criteria: correctness of code.

3a. The following code defines an elliptic curve (whatever that is!) over $\mathbb{F}_p$ for a certain prime $p$. This has the structure of an abelian group; compute the order of this group.

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

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

g = E(4808979935694435458, 2167227988161099418)

3c. Using $E$ and $g$, perform the analogue of a Diffie-Hellman key exchange. Hint: the analogue of modular multiplication is denoted by addition, and the analogue of exponentiation g^n is denoted n*g.

g+g+g, 3*g

# Your code goes here
a = randint(0, p-1) # Alice's secret
b = randint(0, p-1) # Bob's secret
# ...

Replacement values:

p = 2430985831
E = EllipticCurve(GF(p), [0,1,0,1,-1])
g = E(1142679369, 725589986)

Problem 4: Attacking elliptic curve Diffie-Hellman

Grading criteria: correctness of code.

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

4a. Take the code given in lecture for the baby-step-giant-step method for computing discrete logarithms, and adapt it to this elliptic curve.

def elliptic_bsgs(h):
    # your code goes here

4b. Take the code given in lecture for the Chinese Remainder Theorem method for computing discrete logarithms, and adapt it to this elliptic curve. (Hint: first factor the order of $E$.)

def elliptic_crt(h):
    # your code goes here

4c. Test your solutions to 4a and 4b using the following code.

m = randint(0, p-1)
h = m*g
print(m)
print(g.discrete_log(h))
print(elliptic_bsgs(h))
print(elliptic_crt(h))

Problem 5: A preview of R

Grading criteria: correctness and thoroughness of explanations.

For the following exercise, switch your kernel to "R (R-Project)".

In each of the following cells, run the R commands as indicated, then explain in words:

• what is the data being analyzed;

• what the code is doing;

• one conclusion you drew from the data.

You might want to consult the documentation for the R datasets package, from which these examples were taken.

pairs(mtcars)

require(stats); require(graphics)
coplot(circumference ~ age | Tree, data = Orange, show.given = FALSE)

x <- apply(HairEyeColor, c(1, 2), sum)
x
mosaicplot(x)