diff options
| -rw-r--r-- | tech-math/reflection.tex | 48 | ||||
| -rw-r--r-- | tech-math/ws6.tex | 29 |
2 files changed, 77 insertions, 0 deletions
diff --git a/tech-math/reflection.tex b/tech-math/reflection.tex new file mode 100644 index 0000000..acaab9b --- /dev/null +++ b/tech-math/reflection.tex @@ -0,0 +1,48 @@ +%%% Guiding Questions: + +\newdimen\gap \gap=.1\hsize +\def\sec#1{\bigskip\vskip\gap\goodbreak\vskip-\gap\noindent{\bf #1}\nobreak} +\nopagenumbers + +\sec{Overall, what did you like about working on this project?} + +In this project, my group studied a number of distributed networked technologies and wrote a few representative algorithms. +I primarily worked on writing the RSA encryption and decryption Python scripts as well as establishing some of the connections to real-world applications. +I liked the open-ended nature of the project because it allowed me to do this. +In other comparable projects, I haven't been able to apply programming at all, which I enjoyed greatly in this project. + +Additionally, this project allowed us to focus significantly more on novel, real-world technologies because of the course material. +Combinatorics is both concrete and applicable to technological and statistical questions much more than an abstract, continuous field like calculus. + +\sec{What did you learn from this project that was related to combinatorics?} + +In this project, I learned how the RSA algorithm works. +In abstract, I understood that there was a one-way function that could only be reversed by some NP-hard knowledge. +But implementing it required me to make specific that one-way function (a mixture of the totient function, modular arithmetic, and semiprimes) and the reason that it was fast---the Euclidean algorithm. +However, I learned that it is insufficient for a number of reasons: polynomial-time breaking in quantum computers and being too slow on conventional computers. +All of these secondary concepts relate directly to or are part of the course. + +Directly related to the course, I learned about a bridge-finding algorithm which is much more efficient than a naive one. +The naive ``remove-and-test'' algorithm is dwarfed by a greedy tree-based algorithm for determinining if a graph is 2-connected, in linear time as compared to quadratic. + +\sec{What did you learn from this project that was not related to combinatorics?} + +I learned how to use the {\tt ord()} and {\tt chr()} functions in Python for converting ASCII to integers and back as well as allowing me to include human-transmissible random data in the form of base64 encoded encrypted text. +Additionally, I expanded my knowledge on proper software structuring by including a discrete ``library'' for completing those tasks---meaning that the code describing the RSA encryption and decryption steps were focused solely on the mathematical components. + +In writing the paper, I learned how the internet developed---from a series of routing technologies and algorithms that were primarily theoretical in nature. +By ``developed,'' I don't mean how the culture or even applications developed, but the early scientific uses that relied on the now completely abstracted packet switching algorithms which, in many cases, have been mostly obsoleted because of highly centralized ISPs and direct fiber connections between servers +Additionally, the technology was developed by a small enough amount of people that they wrote a paper on how they did it. +Furthermore, I learned more about the technologies I talked about in the general description, like the TOR network and how three-component circuits are used to establish secure connections and obscure the user's identity. + +\sec{Overall, what challenges did you encounter on this project, if anything? Were you able to overcome them?} +\def\mod{\thinspace({\rm mod}\thinspace} + +In the actual construction of the RSA code, I faced a few issues with designing it. +Chief amongst them is an efficient algorithm for finding $d$ where $ed \equiv 1 \mod m)$. +The approach I and my partners attempted was the traditional one: a reverse Euclidean algorithm that finds the solution, recursively, for $(d,e {\thinspace\rm mod\thinspace} d)$, but we couldn't manage to determine a working code snippet. +Instead, we used a naive while loop to check all $0<d<m$. + +%[About 500 words] + +\bye diff --git a/tech-math/ws6.tex b/tech-math/ws6.tex new file mode 100644 index 0000000..5042920 --- /dev/null +++ b/tech-math/ws6.tex @@ -0,0 +1,29 @@ +\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} + +\noindent {\bf Q1)} %#14:2 + +Considering a flow from Source $S$ which is connected to all members of $V_1$ and a similar sink $T$ with respect to $V_2$, this can be solved by the Ford-Fulkerson algorithm. + +Let $V_{kj}$ be the $j^{th}$ member, from left to right of $V_k$. The optimum matching is $$\{V_11\to V_22, V_12\to V_27, V_13\to V_25, V_14\to V_21, V_15\to V_26, V_17\to V_24\}$$ because the Ford-Fulkerson algorithm halts, and Hall's theorem holds: there is a grouping of vertices in $V_1$ with a fewer number of neighbors than in the group. + +\noindent {\bf Q2)} %#14:8 + +$w=3$. + +Antichain: $\{x_1,x_2,x_3\}$. + +Chain Partition: $\{x_3,x_4,x_5\}\cup\{x_6,x_1\}\cup\{x_2\}$. + +\noindent {\bf Q3)} %#15:2 + +\let\sp\thinspace +$$\pi_1\pi_2 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6 \atop + 3\sp 6\sp 4\sp 2\sp 1\sp 5}\right)$$ +$$\pi_2\pi_1 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6 \atop + 3\sp 1\sp 4\sp 5\sp 6\sp 2}\right)$$ +$$\pi_3\pi_4 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6\sp 7\sp 8 \atop + 1\sp 3\sp 8\sp 5\sp 7\sp 4\sp 6\sp 2}\right)$$ +$$\pi_4\pi_3 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6\sp 7\sp 8 \atop + 5\sp 4\sp 3\sp 6\sp 7\sp 8\sp 1\sp 2}\right)$$ + +\bye |