CSC110/assignments/a4/a4.tex

\documentclass[fontsize=11pt]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage[utf8]{inputenc}
\usepackage[margin=0.75in]{geometry}

\AtBeginEnvironment{align}{\setcounter{equation}{0}}

\title{CSC110 Assignment 4: Number Theory, Cryptography, and Algorithm Running Time}
\author{Azalea Gui \& Peter Lin}
\date{\today}

% Some useful LaTeX commands. You are free to use these or not, and also add your own.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\code}[1]{\texttt{#1}}

\begin{document}
\maketitle

\section*{Part 1: Practice with Proofs}

\begin{enumerate}

\item[1.] Statement to prove:

$$\forall a, k, n \in \Z,~ \gcd(a, n) = 1 \Rightarrow \gcd(a + kn, n) = 1$$

\begin{proof} : \\
$d = \gcd(a,n)$ is defined as $(a=0 \land n=0 \implies d=0) \land \\ (a \neq 0 \lor n \neq 0 \implies d | a \land d | n \land (\forall e \in \N, e | a \land e | n \implies e \le d))$ \\ 
\\
Let $a,k,n \in \Z$ \\
Assume that $\gcd(a,n) = 1$ \\
Since $d = 1 \neq 0$, this implies that $a \neq 0 \lor n \neq 0$ \\
Since $a \neq 0 \lor n \neq 0$, we know $1 | a \land 1 | n \land (\forall e_2 \in \N, e_2 | a \land e_2 | n \implies e_2 \le 1)$ is also true. \\
We need to prove: $(a + kn) \neq 0 \lor n \neq 0 \implies 1 | (a + kn) \land 1 | n \land (\forall e \in \N, e | (a + kn) \land e | n \implies e \le 1)$ \\ 
\\
Suppose $(a + kn) \neq 0 \lor n \neq 0$ \\
We need to prove: $1 | (a + kn) \land 1 | n \land (\forall e \in \N, e | (a + kn) \land e | n \implies e \le 1)$

\begin{enumerate}
    \item[1.] Proving for: $1 | (a + kn)$ \\
        That is: $\exists c \in \Z$ s.t. $(a + kn) = 1 \cdot c$ \\
        Take $c = (a + kn)$ \\
        $(a + kn) = 1 \cdot (a + kn)$ is true.
    
    \item[2.] $1 | n$ is given to be true.
    
    \item[3.] Proving for $\forall e \in \N, e | (a + kn) \land e | n \implies e \le 1$ \\
        Let $e \in \N$ \\
        Suppose $e | (a + kn) \land e | n$ \\
        $a + kn = ex \land n = ey$ for some $x,y \in \Z$ \\
        $a + key = ex$ for some $x,y \in \Z$ \\
        $a = e(x - ky)$ for some $x,y \in \Z$ \\
        Let $c = (x - ky)$ \\
        By substitution, we now have: $a = ec$ \\
        Therefore, $\exists c \in \Z$ s.t. $a = ec$ is true. \\
        Which means $e | a$ is true. \\
        Since we are given $\forall e_2 \in \N, e_2 | a \land e_2 | n \implies e_2 \le 1$ \\
        Take $e_2 = e$, we now have $e | a \land e | n \implies e \le 1$ \\
        And since we now know $e | a$ and $e | n$, we can conclude $e \le 1$. \\
        Which is what we want to show.
\end{enumerate}


\end{proof}

\item[2.] Statement to prove (we've expanded the definition of Omega for you!):

$$\exists c, n_0 \in \R^+,~ \forall n \in \N,~ n \geq n_0 \Rightarrow \log_{3} n - \log_{11} n \geq c \cdot \log_{14} n$$

\begin{proof}
Notice $\log_3n - \log_{11}n = k\log_{14}n$, where $k = \frac{1}{\log_{14}(3)} - \frac{1}{\log_{14}(11)}$.

WTS: $$\exists c, n_0 \in \R^+,~ \forall n \in \N,~ n \geq n_0 \Rightarrow k\log_{14}n \geq c \cdot \log_{14} n$$
Choose $c = k$ and $n_0 = 2$.
WTS: $$\forall n \in \N, n \geq 2 \Rightarrow k\log_{14}n \geq k\log_{14}n$$
Let $n \in \N$ where $n \geq 2$.
We know $k \geq k$. Multiply both sides by $\log_{14}n$.
Therefore $k\log_{14}n \geq k\log_{14}n$.
\end{proof}

\item[3.] Statement to prove (we haven't expanded the definition of Big-O for you, but we encourage you to do so yourself):

$$\forall f, g: \N \to \R^{\geq 0},~ g \in \cO(f) \land \big(\forall m \in \N,~ f(m) \geq 1 \big) \Rightarrow g \in \cO(\floor{f})$$

\begin{proof}
Assume: 
$$\forall m \in \N,~ f(m) \geq 1$$
Also assume $g \in O(f)$, that is:
$$\exists c_0, n_0 \in \R^+, \forall n \in \N, n \geq n_0 \Rightarrow g(n) \leq c_0 \cdot f(n)$$
WTS: $$\exists c_1, n_1 \in \R^+, \forall n \in \N, n \geq n_1 \Rightarrow g(n) \leq c_1 \cdot \floor{f(n)}$$

Choose $n_1 = n_0$ and $c_1 = 2c_0$.

Let $n \in \N$ and $n > n_1$.

By definition of $g \in \cO(f)$, we know $g(n) \leq c_0 \cdot f(n)$.
\begin{align*}
    g(n) &\leq c_0 \cdot f(n)\\
    g(n) &\leq c_0 \cdot (\floor{f(n)} + 1)\\
    g(n) &\leq c_0 \cdot (\floor{f(n)} + \floor{f(n)}) \quad{\text{because } 1 \leq \floor{f(n)}} \\
    g(n) &\leq 2c_0 \cdot \floor{f(n)}\\
    g(n) &\leq c_1 \cdot \floor{f(n)}
\end{align*}
\end{proof}

\end{enumerate}

\newpage

\section*{Part 2: Generating Coprime Numbers}

\begin{enumerate}

\item[1.]
Not to be handed in.

\item[2.]
Complete this part in the provided \texttt{a4\_part2.py} starter file.
Do \textbf{not} include your solution in this file.

\item[3.]
Prove that each loop invariant holds.

\begin{enumerate}
\item[a.] Loop Invariant 1
\begin{proof} : \\
Variables: In this proof, $N$ is the abbreviation for the list \texttt{nums\_so\_far}. \\
\\
Assumption 1: The loop invariant 1 is true for the previous iteration. \\
That is $\forall k_2 \in N, gcd(k_2, 2) = 1 \land gcd(k_2, 3) = 1$ \\
\\
Assumption 2: The statement proven in Part 1.1: \\
$\forall a,k,n \in \Z, gcd(a,n) = 1 \implies gcd(a + kn, n) = 1$ \\
\\
We need to prove: $\forall k \in N + [N[-2] + 6], gcd(k, 2) = 1 \land gcd(k, 3) = 1$ \\
Which is equivalent to: $\forall k \in N, gcd(k, 2) = 1 \land gcd(k, 3) = 1$ and \\ 
$gcd(N[-2] + 6, 2) = 1 \land gcd(N[-2] + 6, 3) = 1$ \\
\\ 
Since the first part is the same as the previous iteration, it is true. \\
What we need to prove becomes: 
$gcd(N[-2] + 6, 2) = 1 \land gcd(N[-2] + 6, 3) = 1$ \\
\\
Pick $k_2 = N[-2] \in N$ \\
By assumption 1, we know that $gcd(N[-2], 2) = 1$ and $gcd(N[-2], 3) = 1$

\begin{enumerate}
    \item[1.] Proving for $gcd(N[-2] + 6, 2) = 1$ \\
        Pick $a = N[-2], k = 3, n = 2$ \\
        Since we know $gcd(N[-2], 2) = 1$, $gcd(a, n) = 1$ is true. \\
        Therefore, by assumption 2, we know that $gcd(a + kn, n) = 1$ is also true. \\
        Substituting the varaibles back, we know $gcd(N[-2] + 6, 2) = 1$.
    \item[2.] Proving for $gcd(N[-2] + 6, 3) = 1$ \\
        Pick $a = N[-2], k = 2, n = 3$ \\
        Since we know $gcd(N[-2], 3) = 1$, $gcd(a, n) = 1$ is true. \\
        Therefore, by assumption 2, we know that $gcd(a + kn, n) = 1$ is also true. \\
        Substituting the varaibles back, we know $gcd(N[-2] + 6, 3) = 1$.
\end{enumerate}
\end{proof}

\item[b.] Loop Invariant 2
\begin{proof} : \\
Variables: In this proof, $N$ is the abbreviation for the list \texttt{nums\_so\_far}, and $|N|$ represents the size of $N$. \\
\\
Assumption 1: The loop invariant 2 is true for the previous iteration. \\
That is $\forall i_2 \in [0, \dots, |N| - 3], N[i_2] + 6 = N[i_2 + 2]$ \\
\\
Let $M = N + [N[-2] + 6]$ be the list of the current iteration. \\
We need to prove: $\forall i \in [0, \dots, |M| - 3], M[i] + 6 = M[i + 2] $

\begin{enumerate}
    \item[1.] Let $i < |M| - 3$ \\
        Since the new entry added to $M$ is not included in $i$, this case is equivalent to the previous iteration, and we know that is true by assumption 1.

    \item[2.] Let $i = |M| - 3$ \\
        We need to prove: $M[|M| - 3] + 6 = M[|M| - 3 + 2]$ \\
        That is $M[-3] + 6 = M[-1]$ \\
        \\
        Let's start with a true statement: \\
        $N[-2] = N[-2]$ \\
        Since $N[-2] = (N + [N[-2] + 6])[-3] = M[-3]$, \\
        $M[-3] = N[-2]$ \\
        Add 6 to both sides: \\ 
        $M[-3] + 6 = N[-2] + 6$ \\
        Since $M[-1] = (N + [N[-2] + 6])[-1] = N[-2] + 6$ is it's last entry, \\
        $M[-3] + 6 = M[-1]$ \\
        Which is what we want to show.
        
\end{enumerate}
\end{proof}

\item[c.] Loop Invariant 3
\begin{proof} : \\
Variables: In this proof, $N$ is the abbreviation for the list \texttt{nums\_so\_far}, and $|N|$ represents the size of $N$. \\
\\
Assumption 1: Loop invariant 3 is true for the previous iteration. \\
That is $\forall i_2 \in [0, \dots, |N| - 2], N[i_2] <  N[i_2 + 1]$ \\
\\
Assumption 2: Loop invariant 2 is true for the previous iteration. \\
That is $\forall i_3 \in [0, \dots, |N| - 3], N[i_3] + 6 = N[i_3 + 2]$ \\
\\
Let $M = N + [N[-2] + 6]$ be the list of the current iteration. \\
We need to prove: $\forall i \in [0, \dots, |M| - 2], M[i] < M[i + 1] $ \\
\\
Assumption 3: Loop invariant 2 is true for the current iteration. \\
That is $\forall i_4 \in [0, \dots, |M| - 3], M[i_4] + 6 = M[i_4 + 2]$ \\
\\
Let's first prove an intermediate statment, statment 4: \\
$\forall i_5 \in [0, \dots, |N| - 2], 0 < N[i_5 + 1] - N[i_5] < 6$ \\
Let $i_5 \in [0, \dots, |N| - 2]$, \\
We want to show $0 < N[i_5 + 1] - N[i_5] < 6$ \\
\\
Pick $i_2 = i_5$, \\
We know that $N[i_5] < N[i_5 + 1]$ by assumption 1. \\
Which means $0 < N[i_5 + 1] - N[i_5]$ \\
\\
Then, we need to prove $N[i_5 + 1] - N[i_5] < 6$ \\
Since $N = \text{list}[1, 5]$ before the first iteration, the base case $N[1] < N[0] + 6$ is true. \\
For the inductive step, let's look at the true statement again: \\
$N[i_5] < N[i_5 + 1]$ \\
Add 6 to both sides: \\
$N[i_5] + 6 < N[i_5 + 1] + 6$ \\
Pick $i_3 = i_5$ \\
We know that $N[i_5] + 6 = N[i_5 + 2]$ by asssumption 2. \\
By substitution, our true statement becomes: \\
$N[i_5 + 2] < N[i_5 + 1] + 6$ \\
$N[(i_5 + 1) + 1] < N[i_5 + 1] + 6$ \\
Which is the end of our induction. \\
\\
We have proven the intermediate statement 4. \\
We now need to prove: $\forall i \in [0, \dots, |M| - 2], M[i] < M[i + 1] $

\begin{enumerate}
    \item[1.] Let $i < |M| - 2$ \\
        Since the new entry added to $M$ is not included in $i$, this case is equivalent to the previous iteration, and we know that is true by assumption 1.

    \item[2.] Let $i = |M| - 2$ \\
        We need to prove: $M[|M| - 2] < M[|M| - 2 + 1]$ \\
        That is $M[-2] < M[-1]$ \\
        \\
        Pick $i_5 = |N| - 2$ \\
        We know that $0 < N[-1] - N[-2] < 6$ by statement 4 \\
        Since $N[-1] = (N + [N[-2] + 6])[-2] = M[-2]$, \\
        Since $N[-2] = (N + [N[-2] + 6])[-3] = M[-3]$, \\
        $0 < M[-2] - M[-3] < 6$ \\
        $M[-2] < M[-3] + 6$ \\
        Pick $i_4 = |M| - 3$ \\
        We know that $M[-3] + 6 = M[-1]$ by assumption 3 \\
        By substitution, we now have: \\
        $M[-2] < M[-1]$
        Which is what we want to show.

\end{enumerate}


\end{proof}

\item[d.] Loop Invariant 4
\begin{proof}
\textit{\newline } Let $N$ = \texttt{nums\_so\_far}.\\
\textit{\newline Lemma 1}. Let $p$ be a prime number and $x \in \Z^+$. Then $p \not|\ x \Leftrightarrow gcd(p, x) = 1$.\\
To prove $p \not|\ x \Rightarrow gcd(p, x) = 1$, assume $p \not|\ x$ and find $gcd(p, x)$. To find the greatest common divisor, only check the 2 positive divisors of $p$, which are $1$ and $p$. $p$ does not divide $x$ by assumption, therefore $gcd(p, x) = 1$ (1 divides all integers).

To prove $p \not|\ x \Leftarrow gcd(p, x) = 1$, consider the contrapositive $gcd(p, x) \neq 1 \Rightarrow p | x$. Because $p$ is prime, its only divisors are $1$ and $p$. If $1$ is not the greatest common divisor, then $p$ must be, which means $p | x$, which proves the contrapositive.\\

\textit{Lemma 2}. $(gcd(2, x) = 1 \land gcd(3, x) = 1) \Rightarrow (x \equiv 1 \lor x \equiv 5 \bmod 6)$.\\
Consider the contrapositive, $(x \not\equiv 1 \land x \not\equiv 5 \bmod 6) \Rightarrow (gcd(2, x) \neq 1 \lor gcd(3, x) \neq 1)$.\\
If $x$ is equivalent to $0$, $2$, or $4 \bmod 6$ then $2 | x$ and $gcd(2, x) = 2 \neq 1$. If $x$ is equivalent to $0$ or $3 \bmod 6$ then $3 | x$ and $gcd(3, x) = 3 \neq 1$. The only numbers that weren't considered were $1$ and $5$, which proves Lemma 2.\\

\textit{Lemma 3}. $\forall n \in \N, N[2n] = 6n + 1 \land N[2n + 1] = 6n + 5$.\\
Let us do a proof by induction over $n$.\\
When $n = 0$, $N[2n] = 1 \land N[2n + 1] = 5$.\\
For the induction step, show\\
$(N[2n] = 6n + 1 \land N[2n + 1] = 6n + 5) \Rightarrow (N[2(n + 1)] = 6(n + 1) + 1 \land N[2(n + 1) + 1] = 6(n + 1) + 5)$.\\
\begin{alignat*}{5}
    &N[2n]       &&= 6n + 1       \quad &&\land N[2n + 1]       &&= 6n + 5\\
    &N[2n] + 6   &&= 6(n + 1) + 1 \quad &&\land N[2n + 1] + 6   &&= 6(n + 1) + 5\\
    &N[2n + 2]   &&= 6(n + 1) + 1 \quad &&\land N[2n + 1 + 2]   &&= 6(n + 1) + 5\\
    &N[2(n + 1)] &&= 6(n + 1) + 1 \quad &&\land N[2(n + 1) + 1] &&= 6(n + 1) + 5\\
\end{alignat*}
which proves Lemma 3.\\

To prove Loop Invariant 4, let $k \in \N$, $0 \leq k \leq N[-1]$ and $k$ is coprime to $2$ and $3$.\\
By Lemma 2, $\exists n \in \N \text{ s.t. } k = 6n + 1 \lor k = 6n + 5$. Then either $N[2n] = k$ or $N[2n + 1] = k$.\\
In addition, because $k \leq N[-1]$, the index of $k$ must be less than $|N| - 1$, by Loop Invariant 3 ($N$ is increasing).
\end{proof}
\end{enumerate}

\item[4.]
Complete this part in the provided \texttt{a4\_part2.py} starter file.
Do \textbf{not} include your solution in this file.

\item[5.]
Complete this part in the provided \texttt{a4\_part2.py} starter file.
Do \textbf{not} include your solution in this file.
\end{enumerate}

\newpage

\section*{Part 3: Running-Time Analysis}

\begin{enumerate}
\item[1.]
Running-time analysis of \texttt{coprime\_to\_2\_and\_3}.

Let $N$ be the list \code{nums\_so\_far}, and let $n$ be the input integer. 

The loop in the function runs until $N[-2] + 6 < n$. Since $N = \text{list}[1, 5]$ before the first iteration, the loop will run $\text{(amount of coprimes below n)} - 2$ times. Since the loop appends $N[-2] + 6$ to $N$, $N[-2]$ will increase for the next iteration by either $5 - 1 = 4$ or $1 + 6 - 5 = 2$ in an alternating way, which is an increase of $3$ on average. This loop will run $(n - 6) / 3 = n / 3 - 2$ times on average. However, since $\cO(n / 3 - 2) = \cO(n)$, we can be conservative here and say that the loop will run at most $n$ times.

Since the loop contained only constant-time operations, the runtime of the loop is $\cO(n)$.

Since there are only constant-time operations outside the loop, the runtime of the entire function is $\cO(n)$.

\item[2.] 
Running-time analysis of \texttt{starting\_coprime\_numbers}.

Let $P$ be the size of the input set \code{primes}, and let $m$ be the product of the numbers in \code{primes}.

Let $c_0, \dots, c_n$ be constants that doesn't depend on any variables.

The inner loop \code{for p in primes} runs $P$ iterations, and since each iteration contains only a constant number of constant-time operations, it takes $c_0P$ steps where $c_0$ is a constant. The outer loop iterates $m - 1$ times, taking $c_0P + c_1$ steps each time, with a total of $(m - 1)(c_0P + c_1)$ steps.

Outside the outer loop, there is one non-constant-time operation \code{math.prod}, which computes the product of all numbers in \code{primes}, which takes $P$ steps. And there are various constant-time operations as well taking $c_2$ steps. So, the entire function will take $(m - 1)(c_0P + c_1) + P + c_2$ steps.

Thus, the total number of basic operations is:
\begin{align}
RT_{\code{starting\_coprime\_numbers}}(P, m) &= (m - 1)(c_0P + c_1) + P + c_2 \\
& = c_0mP + c_1m - c_0P + P - c_1 + c_2 \\
& \in \Theta(mP + m) \\
& \in \Theta(mP) ~~~ (\text{since } P \ge 1)
\end{align}

\item[3.]
Running-time analysis of \texttt{coprime\_to\_all}.

Let $P$ be the size of the input set \code{primes}, let $m$ be the product of the numbers in \code{primes}, and let $n$ be the input integer.

Let $N$ be the list \code{nums\_so\_far}, and let $|N|$ be its length.

Let $c_0, \dots, c_n$ be constants that doesn't depend on any variables.

The loop in the function runs until $N[-\varphi(m)] + m < n$ where $\varphi(m)$ is the initial length of $N$ which is the amount of starting coprime numbers. The loop will run $\text{(amount of coprimes below n)} - \varphi(m)$ times. Since the loop appends $N[-\varphi(m)] + m$ to $N$, $N[-\varphi(m)]$ will increase for the next iteration by $k$ on average and the loop will run $(n - m) / k$ times on average, where $k$ is the average of the sequential differences in $N$ before the first iteration, which can be written as:
\begin{align}
    k &= (N[1] - N[0] + N[2] - N[1] + \dots + N[-1] - N[-2] + (N[0] + m) - N[-1]) / \varphi(m)\\
    &= \frac{m}{\varphi(m)}
\end{align}

The loop will run $(n - m) / k  = (n - m) * (\varphi(m) / m)$

Since $\varphi(m)$ will be maximized when $m$ is a prime number, in which case $\varphi(m) = m - 1$, so $\varphi(m) < m$, and $\varphi(m) / m < 1$. Therefore, $\varphi(m) / m$ is bounded by a constant, and we can ignore it in our runtime analysis, and we can say that our loop will take $n - m$ operations (by the precondition, $n \ge m$).

Outside the loop, there are two non-constant-time operations. One is \code{math.prod}, which computes the product of all numbers in \code{primes}, which takes $P$ steps. And the other is \code{starting\_coprime\_numbers(primes)}, which we previously computed the steps to be $mP + m$, ignoring constants.

The total number of steps in this function is at most $n - m + P + mP + m = n + P + mP$ steps, which is contained in $\cO(n + P + mP)$.

And since $P \ge 1$, $\cO(n + P + mP) = \cO(n + mP)$

\end{enumerate}

\section*{Part 4: Two New Cryptosystems}

Complete this part in the provided \texttt{a4\_part4.py} starter file.
Do \textbf{not} include your solution in this file.

\end{document}