Exam 2 review
Jump to Section
- All-Slides after the first exam.
- All Topics
RSA Public Key Cryptosystem
Extended GCD to compute private key
- \(\varphi(n) = (p-1)(q-1)\)
- \(se + t\varphi(n) = g = 1 = gcd(e, \varphi(n))\)
- \(se \equiv 1(\mod \varphi (n))\)
- \(s = e^{-1}(\mod \varphi(n))\)
R implementation of GCD
This is an implementation of Eculid’s recursive GCD algorithm. Should be easy to convert to python.
euclid <- function(a, b) {
print(c(a, b))
if (b == 0) {
return(a)
}
euclid(b, a %% b)
}
Intro to Graph Theory, Euler’s Degree Formula
- A Graph is a series of vertices (nodes) that are connected by edges
- Degree (in this class) is equal to the number of edges that a node is connected to
- Complete graph is a graph where every node is connected to every other node.
- A subgraph is a graph made from a subset of nodes in another graph
- An induced subgraph must have the same edges that the parent graph had.