| | |
Solve the following system of congruences:
$$\begin{array}{rcl} x &\equiv& 8\pmod{11}\\ x &\equiv& 3\pmod{9} \end{array}$$The first congruence tells us that $x = 11k+8$ for some integer $k$. So we substitute this into the second congruence:
$$11k + 8 \equiv 3\pmod{9}$$Now, we can solve for $k$...
$$11k \equiv -5\pmod{9}$$We'll need to find $11^{-1}\pmod{9}$ using the Euclidean Algorithm and "back-solving". Doing this yields $11^{-1} \equiv 5\pmod{9}$. Then, we multiply both sides by this value to eliminate the $11$:
$$k \equiv -25\pmod{9}$$Adding three nines to the right side doesn't violate the congruence, but allows us to work with a positive value less than the modulus (which in general is desirable).
$$k \equiv 2\pmod{9}$$This means that there is some integer $k_2$ such that
$$k = 9k_2 + 2$$Recall, $x = 11k + 8$, so substitute the value for $k$ into this equation to find:
$$x = 11(9k_2+2)+8$$Equivalently,
$$x = (11\cdot9)k_2 + 30$$In congruence form, we then have:
$$x \equiv 30\pmod{99}$$Find all $x$ that satisfy both $x \equiv 8 \pmod{23}$ and $x \equiv 15 \pmod{17}$
The first congruence gives us $x = 23k + 8$ for some integer $k$.
Substituting this into the second congruence, we have $23k + 8 \equiv 15\pmod{17}$, or more simply $23k \equiv 7\pmod{17}$.
Finding $23^{-1} \equiv 3\pmod{17}$ either by inspection or the Euclidean Algorithm, we solve for $k$ to discover $k \equiv 3 \cdot 7 \equiv 4\pmod{17}$
So $k = 17m + 4$ for some integer $m$. Substituting this back into the earlier expression given for $x$, we have $$\begin{array}{rcl} x &=& 23(17m + 4) + 8\\ &=& 391m + 100 \end{array}$$
Thus, $x \equiv 100\pmod{391}$
Find $\phi(67375)$, knowing that $67375 = 5^3 \cdot 7^2 \cdot 11$.
Note that $$\begin{array}{rcl} \phi(67375) &=& \phi(5^3 \cdot 7^2 \cdot 11)\\ &=& \phi(5^3) \cdot \phi(7^2) \cdot \phi(11)\\ &=& (5^3-5^2)(7^2-7)(11-1)\\ &=& 100 \cdot 42 \cdot 10\\ &=& 42000 \end{array}$$
Describe how to arrange the integers (positive, zero, and negative) in a single list so that every integer is guaranteed to appear. (Recall, this establishes a "pairing" between the integers and the natural numbers, which in turn establishes these two sets have the same cardinality.)
$0,-1,1,-2,2,-3,3,-4,4,\ldots$
Prove that the cardinality of the power set of a given set is never equal to the cardinality of the set itself.
(For a metaphorical context for the below argument, consult the notes on the cardinality of the power set.)
We argue indirectly.
Suppose we assume that the cardinality of a set $S$ and its power set $P(S)$ are equal.
As such, there must exist some function $f: S \rightarrow P(S)$ which is a bijection.
Let us define the following subsets of $S$:
$$C = \{x \in S \;|\; x \in f(x) \}$$ $$H = \{x \in S \;|\; x \not\in f(x) \}$$Note, $H$ is a subset of $S$, so it must be an element of the power set $P(S)$.
Since $f$ is a bijection, there must exist some $a \in S$ such that $f(a) = H$
Clearly, any element of $S$ must be in either $H$ or $C$, but never both. With this in mind, consider the implications for the aforementioned element $a$...
If $a \in H$, then $a \not\in f(a)$. As $f(a)=H$, this implies $a \not\in H$. Contradiction.
If $a \in C$, then $a \in f(a)$. As $f(a) = H$, this implies $a \in H$, which requires $a \not\in C$. Contradiction.
So $a$ is not an element of $H$ or $C$.
However, we argued just moments before that every element of $S$ (which includes $a$) must be in one of these two sets.
This gives us the contradiction needed to reject our original assumption that the cardinality of a set $S$ and its power set $P(S)$ are equal.
It must then be the case that the cardinality of a set $S$ and its power set $P(S)$ are not equal. QED.
Suppose a message is RSA-encrypted with modulus $N=323$ and encrypting key $e=49$. Find the decrypting key $d$.
Recall that the relationship between the encrypting key $e$, the decrypting key $d$, and the modulus $N$ is given by
$$ed \equiv 1 \pmod{\phi(N)}$$Noting that $\phi(323) = \phi(17 \cdot 19) = \phi(17) \cdot \phi(19) = 16 \cdot 18 = 288$, it remains to solve
$$49d \equiv 1 \pmod{288}$$We can find $d$ from the above in the usual way.
First we use the Euclidean algorithm to ensure that $49$ and $288$ are indeed relatively prime [so that we know $d = 49^{-1}\pmod{288}$ exists.]
288 = 5 * 49 + 43
49 = 1 * 43 + 6
43 = 7 * 6 + 1 <-- note: the remainder tells us gcd(49,288) = 1,
so the multiplicative inverse of 49 (mod 288) exists
Then, we "back-solve" the calculations above to find a linear combination of 49 and 288 that produces 1. This will reveal the value of $49^{-1}\pmod{288}$:
1 = 1 * 43 - 7 * 6 1 = 1 * 43 - 7 * (49 - 1 * 43) 1 = -7 * 49 + 8 * 43 1 = -7 * 49 + 8 * (288 - 5 * 49) 1 = 8 * 288 - 47 * 49Note the multiplier on $49$ of $(-47)$. This is the value of $49^{-1}\pmod{288}$. Of course, adding the modulus of $288$ won't change its value$\pmod{288}$, but does make it positive (which is always nice). So we have $$d \equiv -47 + 288 \equiv 241 \pmod{288}$$
Note that $1452$ is the product of more than two primes ($1452 = 2^2 \cdot 3 \cdot 11^2)$. Then find a $169^{th}$ root of $119\pmod{1452}$ by supposing $x \equiv 119^u\pmod{1452}$ is a solution and noting this implies $$119^{169u} \equiv 119\pmod{1452}$$
That is to say, solve $119^{169u} \equiv 119\pmod{1452}$ for $u$ first, then find $x \equiv 119^u\pmod{1452}$.
(Hint: the calculations involved here are very similar to those used in decrypting RSA messages.)
Note, we can calculate $\phi(1452)$ from its prime factorization:
$$\begin{array}{rcl} \phi(1452) &=& \phi(2^2 \cdot 3 \cdot 11^2)\\ &=& \phi(2^2) \cdot \phi(3) \cdot \phi(11^2)\\ &=& (2^2 - 2)(3-1)(11^2 - 11)\\ &=& 2 \cdot 2 \cdot 110\\ &=& 440 \end{array}$$With this value in hand, we check if $gcd(1452,119) = gcd(\phi(1452),169) = 1$, using the Euclidean Algorithm.
1452 = 12 * 119 + 24 119 = 4 * 24 + 23 24 = 1 * 23 + 1 <-- so gcd(1452,119) = 1 440 = 2 * 169 + 102 169 = 1 * 102 + 67 102 = 1 * 67 + 35 67 = 1 * 35 + 32 35 = 1 * 32 + 3 32 = 10 * 3 + 2 3 = 1 * 2 + 1 <-- so gcd(440,169) = 1
We seek to solve the following:
$$119^{169u} \equiv 119 \pmod{1452}$$Since $\gcd(119,1452) = 1$, we are free to "divide" both sides by $119$ (recall our above calculation to find $gcd(1452,119)$) to obtain
$$119^{169u-1} \equiv 1 \pmod{1452}$$Recall, we know by Euler's Theorem that
$$119^{\phi(1452)} \equiv 1 \pmod{1452}$$Consequently, we know that for any positive integer $c$,
$$119^{440c} \equiv 1 \pmod{1452}$$So we search for a $u$ and $c$ such that
$$169u-1 = 440c$$Equivalently, we solve
$$169u \equiv 1 \pmod{440}$$Solving such congruences should be routine by now -- so we omit the details -- other than to say we know we can do this given our earlier calculation to find $gcd(440,169)$.
This leads to
$$u \equiv 289 \pmod{440}$$So $x \equiv 119^{289} \pmod{1452}$ should solve the congruence with which we started. To find this large power, we appeal to the process of successive squaring...
Breaking the exponent into a sum of powers of two, we find $289 = 256 + 32 + 1$, so we compute $123^n \pmod{1452}$ for all $n$ that are powers of $2$ less than or equal to $256$.
$$\begin{array}{rcl} 119^{1} &\equiv& \fbox{119} \\ 119^{2} &\equiv& 1093\\ 119^{4} &\equiv& 1105\\ 119^{8} &\equiv& 1345\\ 119^{16} &\equiv& 1285\\ 119^{32} &\equiv& \fbox{301}\\ 119^{64} &\equiv& 577\\ 119^{128} &\equiv& 421\\ 119^{256} &\equiv& \fbox{97} \end{array}$$Finally, multiplying the boxed values together, we arrive at the solution we seek
$$x \equiv 119 \cdot 301 \cdot 97 \equiv 1259 \pmod{1452}$$Suppose $N=175951$ and you know that $\phi(N) = 175000$ and $N$ is the product of two primes. Show how to use your knowledge of $\phi(N)$ to factor $N$
Suppose $N=pq$ where $p$ and $q$ are both prime. Then $\phi(N) = (p-1)(q-1)$. This can of course be rewritten as $\phi(N) = N+1 - (p+q)$.
Solving for $(p+q)$ in this last equation and combining the result with $pq = N$ and replacing the known values in each gives the following system of two equations in two unknowns: $$\begin{array}{rcl} p+q &=& 175951 - 175000 + 1\\ pq &=& 175951 \end{array}$$ Equivalently, $$\begin{array}{rcl} p+q &=& 952\\ q &=& \cfrac{175951}{p} \end{array}$$ Combining these via substitution, we arrive at the single equation $$p + \cfrac{175951}{p} = 952$$ Which upon multiplying by $p$ becomes quadratic: $$p^2 - 952p + 175951 = 0$$ This of course, we can solve with the quadratic equation to find $$p = \frac{952 \pm \sqrt{952^2 - 4\cdot 175951}}{2}$$ Equivalently: $$p = 701 \quad \textrm{ or } \quad p = 251$$ Finding the two $q$ values for these two $p$ values is trivial -- both, of course, yield the same factorization: $$N = 701 \cdot 251$$
Find all solutions to $x^2 \equiv 17\pmod{43}$
Note that the modulus, $43$, is a prime congruent to $3$ modulo $4$.
Consequently, if we have solutions, they will take the form $x = \pm17^{(43+1)/4}\pmod{43}$.
Evaluating these powers via successive squaring$\pmod{43}$, we have $$\begin{array}{rcl} 17^{1} &\equiv& \fbox{17} \\ 17 ^{2} &\equiv& \fbox{31}\\ 17 ^{4} &\equiv& 15\\ 17 ^{8} &\equiv& \fbox{10}\\ \end{array}$$ Which tells us that $17^{11} \equiv 17^8 \cdot 17^2 \cdot 17^1 \equiv 10 \cdot 31 \cdot 17 \equiv 5270 \equiv 24\pmod{43}$.
So,
$x \equiv \pm24\pmod{43}$.To guard against the possibility that there were actually no solutions to the congruence given, we verify these values squared are congruent to $17$ module $43$ - which they are.
Find all solutions to $x^2 \equiv 607\pmod{713}$, noting that $713 = 23 \cdot 31$
We note that $x^2 \equiv 607 \equiv 9\pmod{23}$ and $x^2 \equiv 607 \equiv 18\pmod{31}$. In each case, we note the modulus is a prime congruent to $3$ modulo $4$.
Consequently, we check if $x \equiv \pm 9^{(23+1)/4} \equiv \pm 3 \pmod{23}$ and $x \equiv \pm 18^{(31+1)/4} \equiv \pm7 \pmod{31}$ are the respective solutions to these last two congruences - which they are.
(Note, we could have reduced these powers with successive squaring as in the previous problem, but $9^{6} = 531441 \equiv 3\pmod{23}$ and $18^{8} = (18^4)^2 = 104976^2 \equiv 10^2 \equiv 7\pmod{31}$ is faster.)
So one of the following four cases must hold for any $x$ that solves $x^2 = 607\pmod{713}$: $$\begin{array}{c} x \equiv 3\pmod{23}\\ x \equiv 7\pmod{31}\\\\ x \equiv -3\pmod{23}\\ x \equiv -7\pmod{31}\\\\ x \equiv 3\pmod{23}\\ x \equiv -7\pmod{31}\\\\ x \equiv -3\pmod{23}\\ x \equiv 7\pmod{31}\\\\ \end{array}$$
Let's deal with the first case first -- that is to say, let us solve for the $x$ that satisfies $x \equiv 3\pmod{23}$ and $x \equiv 7\pmod{31}$ by applying the algorithm associated with Chinese Remainder Theorem:
$x \equiv 3\pmod{23}$ tells us that for some integer $k$, we have $x = 23k+3$.
Substituting this for $x$ in the second congruence, we have $$23k+3 \equiv 7\pmod{31}$$ Solving for $k$ we subtract 3 from both sides to obtain $$23k \equiv 4\pmod{31}$$ We might solve this by inspection, but it will actually prove advantageous to go ahead and find the multiplicative inverse of $23\pmod{31}$ instead. Doing so, of course involves the Euclidean Algorithm:
31 = 1 * 23 + 8
23 = 2 * 8 + 7
8 = 1 * 7 + 1 <-- so gcd(31,23) = 1 i
(as expected, since these are both primes)
1 = 1 * 8 - 1 * 7
1 = 1 * 8 - 1 * (23 - 2 * 8)
1 = -1 * 23 + 3 * 8
1 = -1 * 23 + 3 * (31 - 1 * 23)
1 = 3 * 31 - 4 * 23 <-- so the multiplicative inverse of 23 is (-4)
Knowing $23^{-1} \equiv -4\pmod{31}$, we multiply both sides of our congruence by this value to find $k$ (and adding the modulus 31 to keep things positive, which doesn't violate the congruence). $$\begin{array}{rcl} (-4) \cdot 23k \equiv (-4) \cdot 4\pmod{31}\\ k \equiv -16\pmod{31}\\ k \equiv 15\pmod{31} \end{array}$$ Written another way, we have $k = 31k_2 + 15$ for some integer $k_2$.
Recalling that $x = 23k+3$ and replacing this $k$ with $(31k_2 + 15)$, we have $$x = 23(31k_2 + 15) + 3 = 713k_2 + 348$$
Thus, we have $x \equiv 348\pmod{713}$.
Of course, now the second case where $$\begin{array}{c} x \equiv -3\pmod{23}\\ x \equiv -7\pmod{31}\\\\ \end{array}$$ is now immediately solved with $x \equiv -348\pmod{713}$.
So now, we proceed to the third case where $$\begin{array}{c} x \equiv 3\pmod{23}\\ x \equiv -7\pmod{31}\\\\ \end{array}$$ Following the same algorithm, the first note that the top congruence tells us $x = 23k+3$ for some integer $k$.
Substituting this into the bottom congruence gives $$23k+3 \equiv -7\pmod{31}$$ Subtracting $3$ from both sides yields $$23k \equiv -10\pmod{31}$$ We previously found $23^{-1}\pmod{31} = -4$, so we multiply both sides by this multiplicative inverse to find $k$: $$(-4)\cdot 23k \equiv (-4)(-10)\pmod{31}$$ Which tells us $$k \equiv 40 \equiv 9\pmod{31}$$ Equivalently, $k = 31k_2 + 9$ for some integer $k_2$. Substituting this into $x = 23k+3$ from earlier above, we have $$x = 23(31k_2 + 9)+3$$ Simplifying, we have $$x = 713k_2 + 210$$ and consequently, our third case is solved by $$x \equiv 210\pmod{713}$$ Just as the first case solution led immediately to the second case's solution -- so too does this solution to the third case lead immediately to the solution of the fourth case (i.e., $x \equiv -3\pmod{23}$ and $x \equiv 7\pmod{31}$): $$x \equiv -210\pmod{713}$$
Putting all of this together, we have $$x \equiv \pm 348, \pm 210\pmod{713}$$
Alice and the hitman Dave decide to flip a coin over the phone. Alice pics some large modulus $N=pq$ where $p$ and $q$ are large primes both congruent to $3\pmod{4}$. Dave picks a value $x=a$, and sends its square $y=x^2$ to Alice. Alice is able to find 4 distinct square roots of $y$ since she knows the factorization of $N$ (which Dave does not). She picks one of these 4 square roots at random and sends it to Dave. If she sends $(-a)$, who wins the toss? Explain why.
Dave already knows $\pm a$ are both square roots of $y$, so he has no new information. Without $4$ distinct square roots of $y$, he remains unable to factor the modulus $N$. Thus, Dave loses the toss.