Difference between revisions of "User talk:Azjps/sandbox"

Latest revision as of 21:11, 15 July 2008

User talk:Azjps/sandbox/gov school

1) Note that $311_{10} = 100110111_2$ , so $2^{311} = 2^{2^8 + 2^5 + 2^4 + 2^2 + 2^1 + 2^0} = 2^{2^8} \times 2^{2^{5}} \times 2^{2^{4}} \times 2^{2^{2}} \times 2^{2^{1}} \times 2^{2^{0}} \quad (*)$ . It requires $0$ multiplications to find $2^0, 2^1$ , and by repeatedly squaring, we can find $\left(2^1\right)^2 = 2^2,\quad \left(2^2\right)^2 = 2^{2^2},\quad \left(2^{2^2}\right)^2 = 2^{2^2\times 2} = 2^{2^3}$ and so forth. Each squaring requires one multiplication, and so we can achieve $\left\{2^{2^0}, \ldots, 2^{2^8}\right\}$ using $8$ multiplications. Substituting into $(*)$ , we find that our expression requires $5$ more multiplications. Thus, $8+5 = \boxed{13}$ multiplications are sufficient.

2)

$\begin{tabular}{|r||r|r|r|r|r|r|r|r|r|r|}

\hline (a,n) & a^0 \mod{n} & a^1 \mod{n} & a^2 \mod{n} & a^3 \mod{n}& \cdots&&&&& a^{10} \mod{n} \\ (3,5) & 1 & 3 & 4 & 2 &&&&&& \\ (2,11) & 1&2&4&8&5&10&9&7&3&6 \\ \hline

\end{tabular}$ (Error compiling LaTeX. Unknown error_msg)

Since each of $\left\{a^{0}, a^{1}, \cdots, a^{n-2}\right\}$ are distinct (and consequently is a permutation of $\{1,2,\ldots,n-1\}$ ), then both are generators with respect to the given modulos.

3) By the Euclidean Algorithm, $\text{gcd}\,(288,84) = \text{gcd}\,(288 - 3\times 84,84)$ $= \text{gcd}\,(36,84) = \text{gcd}\,(36,84-2\times 36)$ $= \text{gcd}\,(36,12) = \boxed{12}$ .

4) Let the number of students be $n$ . Then the given conditions yield that

$\begin{align*}n &\equiv 11 \pmod{13} \\ n &\equiv 5 \pmod{12} \end{align*}$ (Error compiling LaTeX. Unknown error_msg)

By trial-and-error, we can easily find that $n \equiv 89 \pmod{156}$ satisfies these conditions, which must be the distinct solution due to the Chinese Remainder Theorem (and since $\text{gcd}\,(12,13)=1$ ). Since this year we only have $78$ students at Governor's School, we will assume that $\boxed{89}$ is the desired answer, and that we let our counselors pose as students (just kidding).

Alternatively, we could note that $12^{-1} \equiv 12 \pmod{13}$ and that $13^{-1} \equiv 1 \pmod{12}$ using the Extended Euclidean Algorithm or by inspection, and thus the answer is $11 \times 12 \times 12 + 5 \times 1 \times 13 \equiv 89 \pmod{156}$ .

5) Consider computing $a^m \pmod{n},\ a<n$ (this is not really necessary, since we could simply reduce if $a>n$ ). Assume that it is computationally easy to compute the product of two numbers, both $<n$ . Notice then that it is computationally easy to find $a^2$ (which requires just one multiplication, and the numbers are not extremely large as $a<n$ ). Similarly, it is computationally easy to reduce $a^2 \pmod{n}$ . Suppose we express $m = b_kb_{k-1}\cdots b_{1_2}$ in binary form, with $k=\left\lfloor \log_2 m\right\rfloor$ digits (for the given problem, $\left\lfloor \log_2 532452 \right\rfloor = 19$ ). Then $a^m \equiv a^{2^{b_k} + 2^{b_{k-1}} + \cdots + 2^{b_1}} \equiv a^{2^{b_k}} \times a^{2^{b_{k-1}}} \times \cdots \times a^{2^{b_1}} \pmod{n}$ . Each of these terms being multiplied together can be found by squaring $a$ , $k$ times (as established above, $k$ is not very large). Additionally, the multiplications are also assumed to be easy from above. Thus, that the exponent yields a huge number does not pose a computational difficulty.

6) The given conditions yield that

$\begin{align*}n &\equiv 2 \pmod{11} \\ n &\equiv 1 \pmod{13} \\ n &\equiv 3 \pmod{15} \\ n &\equiv 5 \pmod{19} \end{align*}$ (Error compiling LaTeX. Unknown error_msg)

Using the Chinese Remainder Theorem repeatedly, the answer comes out to be $\boxed{16953} \pmod{11 \times 13 \times 15 \times 19 = 40755}$ , which indeed fits the conditions (of course then $16953$ is the desired answer). Work: solving the first two congruences, and then the second two (by trial-and-error), yields

$\begin{align*}n &\equiv 79 \pmod{143} \\ n &\equiv 138 \pmod{285}\end{align*}$ (Error compiling LaTeX. Unknown error_msg)

Here we notice that $285$ happens to be $2 \times 143 - 1$ , which helps us to quickly determine the inverses: $285^{-1} \equiv -1 \pmod{143}$ and $143^{-1} \equiv 2 \pmod{285}$ . Then by the Chinese Remainder Theorem, we have $n \equiv 2 \times 143 \times 138 -1 \times 285 \times 79 \equiv 16953 \pmod{40755}$ .

7) For a pseudorandom construction, it would not be desirable for an external observer to predict a bit given the previous bits. However, with the given construction, and since $DES$ is a publically known one-way function, an observer could simply carry out $DES$ on the previously generated bits (let $DES_{n}(s) = \underbrace{DES(DES(\cdots(DES(s))\cdots)}_{n\ \text{times}}$ , then given $DES_n(s)$ , the outsider can easily carry out $DES(DES_n(s)) = DES_{n+1}(s)$ ), and determine the next bit him/herself. Note that the observer does not need to know the value of the seed $s$ , while in the first construction the observer would still need to know $s$ .

8) Let Andy want to send a secret message to Blase, but Blase only has a cell-phone. We assume that the limits imposed by Blase's computational restrictions do not apply to Andy. Then Andy computes two large prime numbers $p,q$ , and sends $n = p\times q$ to Blase (if desired, Andy can also send the length of his message, $|M|$ , to Blase). Blase then generates a one-time pad, $K$ , and sends $K^2 \pmod{n}$ back to Andy (squaring is computationally easy). Now Andy can use the Rabin decryption algorithm to find the value of $K$ .

Let the binary operation $XOR(a,b)$ be denoted as $a \oplus b$ . We note some basic properties of $XOR:$ $a \oplus b = b \oplus a$ (commutative), $a \oplus (b \oplus c) = (a \oplus b) \oplus c$ (associative), $a \oplus 0 = a$ , $a \oplus a = 0$ . Since it is assumed that an outside attacker could not determine the value of $K$ (performing the Rabin decryption without knowing $p,q$ being a difficult problem), Andy now sends $M \oplus K$ back to Blase. By the given, this is also cryptographically secure. To find the message, Blase performs $(M \oplus K) \oplus K = M \oplus (K \oplus K) = M$ , as desired.

9) We programmed on Excel because MATLAB was unable to handle the huge exponents. Using $a = 3,5,7$ for simplicity of calculations, we find that

$\begin{tabular}{|r||r|r|r||r|}

\hline n & 3^{n-1} \pmod{n} & 5^{n-1} \pmod{n} & 7^{n-1} \pmod{n} & \text{Prime\ or\ Composite?} \\ \hline 6173 & 1 & 1 & 1 & P \\ 6179 & & & 4547 & C \\ 8415* & & & & C \\ 4113* & & & & C \\ 4691 & 1 & 1 & 1 & P \\ 5109* & & & & C \\ 7543 & 4466 & & & C \\ 7907 & 1 & 1 & 1 & P \\ \hline

\end{tabular}$ (Error compiling LaTeX. Unknown error_msg)

The numbers with asterisks are either trivially divisible by $3$ or $5$ . For the numbers that are denoted with $P$ , we can be reasonably sure that they are primes, which they indeed turn out to be. However, we cannot be completely sure that they are prime, due to our lack of randomness in choice of bases for the exponents, and because we only carried out a small number of tests.

10) Note that Caleb does not actually need to know Blase's bid $x$ , as Caleb only needs to send $E(2x)$ . By the statements of RSA, we know that Blase sent $E(x) \equiv x^e \pmod{n}$ , where $e,n, E(x)$ are public. Caleb then wants to send $E(2x) \equiv (2x)^e \equiv 2^ex^e \equiv \boxed{2^eE(x) \pmod{n}}$ . It is computationally easy for Caleb to perform this exponentiation (just as it was for Blase) and multiplication, and he has sufficient information.

11) $47^{1395} \equiv (-1)^{1395} \equiv -1 \equiv \boxed{47} \pmod{48}$ , as $1395$ is odd.

12) $4^{3207} \equiv 4^{5} \times 4^{3202} \equiv 1024 \times 4^{3202} \equiv 0 \times 4^{3202} \equiv \boxed{0} \pmod{1024}$ .

13) The following code can factor the product of two primes (MATLAB's factoring function only works for numbers $< 2^{32}$ , so we scaled down all of the requested answers by $2\times$ )

p = input('Enter prime 1: ')
q = input('Enter prime 2: ')
tic
factor(p * q)
toc

$\begin{tabular}{|r||r|r|r|} \hline \text{bits} & p & q & \text{time} \\ \hline 2 & 3 & 2 & 0.013334 \\ 4 & 11 & 13 & 0.013267 \\ 8 & 129 & 227 & 0.013529 \\ 10 & 803 & 937 & 0.012896 \\ 12 & 3203 & 3701 & 0.012944 \\ 16 & 33893 &47339 & 0.016408 \\ \hline \end{tabular}$

There is not a very strong correlation between the size of the primes because the used numbers are not particularily large. However, the quickest factoring algorithms (elliptic curve, quadratic sieve, and general number field sieve), run in sub-exponential time when it attempts to factor huge numbers.

14) $\left(x^{-1}\right)x \equiv 1 \pmod{n}$ can be rewritten as $\left(x^{-1}\right)x + kn = 1 \quad (*)$ for some integer $k$ . We know that there are solutions to $ax + by = c$ if $c = \text{gcd}\,(a,b)$ , which indeed is the case here as $\text{gcd}\,(41,167) = 1$ . Thus $x^{-1}$ exists.

To find it, we perform the Extended Euclidean Algorithm on $(*)$ :

$\begin{align*}

167 &= 4\times 41 + 3 \\ 41 &= 13 \times 3 + 2 \\ 3 &= 2\times 1 + 1 \\ \\ \Longrightarrow 1 &= 3 - 1\times 2 \\ &= 3 - 1 \times (41 - 13 \times 3) \\ &= (14) \times 3 + (-1) \times 41 \\ &= (14)(167-4\times 41) + (-1) \times 41 \\ &= 14 \times 167 - 57 \times 41

\end{align*}$ (Error compiling LaTeX. Unknown error_msg)

Thus $x^{-1} \equiv -57 \equiv \boxed{110} \pmod{167}$ .

15) For RSA, one step involves computing $d$ such that $d \times e \equiv 1 \pmod{\phi(n)}$ . The existence of such $d \equiv e^{-1}$ , from the previous question, requires that $1 = \text{gcd}\,(\phi(n),e) = \text{gcd}\,((p-1)(q-1),e) = \text{gcd}\, (10 \times 12, 8) = 8$ . This is a contradiction, and thus $d$ does not exist.

Page

Toolbox

Search

Difference between revisions of "User talk:Azjps/sandbox"

Latest revision as of 21:11, 15 July 2008

@@ Line 1: / Line 1: @@
-#REDIRECT [[User talk:Azjps/sandbox/gov school]]
+:''[[User talk:Azjps/sandbox/gov school]]''
+) Note that <math>311_{10} = 100110111_2</math>, so <math>2^{311} = 2^{2^8 + 2^5 + 2^4 + 2^2 + 2^1 + 2^0} = 2^{2^8} \times 2^{2^{5}} \times 2^{2^{4}} \times 2^{2^{2}} \times 2^{2^{1}} \times 2^{2^{0}} \quad (*)</math>. It requires <math>0</math> multiplications to find <math>2^0, 2^1</math>, and by repeatedly squaring, we can find <math>\left(2^1\right)^2 = 2^2,\quad \left(2^2\right)^2 = 2^{2^2},\quad \left(2^{2^2}\right)^2 = 2^{2^2\times 2} = 2^{2^3}</math> and so forth. Each squaring requires one multiplication, and so we can achieve <math>\left\{2^{2^0}, \ldots, 2^{2^8}\right\}</math> using <math>8</math> multiplications. Substituting into <math>(*)</math>, we find that our expression requires <math>5</math> more multiplications. Thus, <math>8+5 = \boxed{13}</math> multiplications are sufficient.
+)
+<center><math>
+\begin{tabular}{|r||r|r|r|r|r|r|r|r|r|r|}
+\hline
+(a,n) & a^0 \mod{n} & a^1 \mod{n} & a^2 \mod{n} & a^3 \mod{n}& \cdots&&&&& a^{10} \mod{n} \\
+(3,5) & 1 & 3 & 4 & 2 &&&&&& \\
+(2,11) & 1&2&4&8&5&10&9&7&3&6 \\
+\hline
+\end{tabular}
+</math></center>
+Since each of <math>\left\{a^{0}, a^{1}, \cdots, a^{n-2}\right\}</math> are distinct (and consequently is a permutation of <math>\{1,2,\ldots,n-1\}</math>), then both are generators with respect to the given modulos.
+) By the Euclidean Algorithm, <math>\text{gcd}\,(288,84) = \text{gcd}\,(288 - 3\times 84,84)</math> <math> = \text{gcd}\,(36,84) = \text{gcd}\,(36,84-2\times 36)</math> <math> = \text{gcd}\,(36,12) = \boxed{12}</math>.
+) Let the number of students be <math>n</math>. Then the given conditions yield that
+<center><math>\begin{align*}n &\equiv 11 \pmod{13} \\ n &\equiv 5 \pmod{12} \end{align*}</math></center>
+By trial-and-error, we can easily find that <math>n \equiv 89 \pmod{156}</math> satisfies these conditions, which must be the distinct solution due to the Chinese Remainder Theorem (and since <math>\text{gcd}\,(12,13)=1</math>). Since this year we only have <math>78</math> students at Governor's School, we will assume that <math>\boxed{89}</math> is the desired answer, and that we let our counselors pose as students (just kidding).
+Alternatively, we could note that <math>12^{-1} \equiv 12 \pmod{13}</math> and that <math>13^{-1} \equiv 1 \pmod{12}</math> using the Extended Euclidean Algorithm or by inspection, and thus the answer is <math>11 \times 12 \times 12 + 5 \times 1 \times 13 \equiv 89 \pmod{156}</math>.
+) Consider computing <math>a^m \pmod{n},\ a<n</math> (this is not really necessary, since we could simply reduce if <math>a>n</math>). Assume that it is computationally easy to compute the product of two numbers, both <math><n</math>. Notice then that it is computationally easy to find <math>a^2</math> (which requires just one multiplication, and the numbers are not extremely large as <math>a<n</math>). Similarly, it is computationally easy to reduce <math>a^2 \pmod{n}</math>. Suppose we express <math>m = b_kb_{k-1}\cdots b_{1_2}</math> in binary form, with <math>k=\left\lfloor \log_2 m\right\rfloor</math> digits (for the given problem, <math>\left\lfloor \log_2 532452 \right\rfloor = 19</math>). Then <math>a^m \equiv a^{2^{b_k} + 2^{b_{k-1}} + \cdots + 2^{b_1}} \equiv a^{2^{b_k}} \times a^{2^{b_{k-1}}} \times \cdots \times a^{2^{b_1}} \pmod{n}</math>. Each of these terms being multiplied together can be found by squaring <math>a</math>, <math>k</math> times (as established above, <math>k</math> is not very large). Additionally, the multiplications are also assumed to be easy from above. Thus, that the exponent yields a huge number does not pose a computational difficulty.
+) The given conditions yield that
+<center><math>\begin{align*}n &\equiv 2 \pmod{11} \\ n &\equiv 1 \pmod{13} \\ n &\equiv 3 \pmod{15} \\ n &\equiv 5 \pmod{19} \end{align*}</math></center>
+Using the Chinese Remainder Theorem repeatedly, the answer comes out to be <math>\boxed{16953} \pmod{11 \times 13 \times 15 \times 19 = 40755}</math>, which indeed fits the conditions (of course then <math>16953</math> is the desired answer). Work: solving the first two congruences, and then the second two (by trial-and-error), yields
+<center><math>
+\begin{align*}n &\equiv 79 \pmod{143} \\ n &\equiv 138 \pmod{285}\end{align*}
+</math></center>
+Here we notice that <math>285</math> happens to be <math>2 \times 143 - 1</math>, which helps us to quickly determine the inverses: <math>285^{-1} \equiv -1 \pmod{143}</math> and <math>143^{-1} \equiv 2 \pmod{285}</math>. Then by the Chinese Remainder Theorem, we have <math>n \equiv  2 \times 143 \times 138 -1 \times 285 \times 79 \equiv 16953 \pmod{40755}</math>.
+) For a pseudorandom construction, it would not be desirable for an external observer to predict a bit given the previous bits. However, with the given construction, and since <math>DES</math> is a publically known one-way function, an observer could simply carry out <math>DES</math> on the previously generated bits (let <math>DES_{n}(s) = \underbrace{DES(DES(\cdots(DES(s))\cdots)}_{n\ \text{times}}</math>, then given <math>DES_n(s)</math>, the outsider can easily carry out <math>DES(DES_n(s)) = DES_{n+1}(s)</math>), and determine the next bit him/herself. Note that the observer does not need to know the value of the seed <math>s</math>, while in the first construction the observer would still need to know <math>s</math>.
+) Let Andy want to send a secret message to Blase, but Blase only has a cell-phone. We assume that the limits imposed by Blase's computational restrictions do not apply to Andy. Then Andy computes two large prime numbers <math>p,q</math>, and sends <math>n = p\times q</math> to Blase (if desired, Andy can also send the length of his message, <math>|M|</math>, to Blase). Blase then generates a one-time pad, <math>K</math>, and sends <math>K^2 \pmod{n}</math> back to Andy (squaring is computationally easy). Now Andy can use the Rabin decryption algorithm to find the value of <math>K</math>.
+Let the binary operation <math>XOR(a,b)</math> be denoted as <math>a \oplus b</math>. We note some basic properties of <math>XOR:</math> <math>a \oplus b = b \oplus a</math> (commutative), <math>a \oplus (b \oplus c) = (a \oplus b) \oplus c</math> (associative), <math>a \oplus 0 = a</math>, <math>a \oplus a = 0</math>. Since it is assumed that an outside attacker could not determine the value of <math>K</math> (performing the Rabin decryption without knowing <math>p,q</math> being a difficult problem), Andy now sends <math>M \oplus K</math> back to Blase. By the given, this is also cryptographically secure. To find the message, Blase performs <math>(M \oplus K) \oplus K = M \oplus (K \oplus K) = M</math>, as desired.
+) We programmed on Excel because MATLAB was unable to handle the huge exponents. Using <math>a = 3,5,7</math> for simplicity of calculations, we find that
+<center><math>
+\begin{tabular}{|r||r|r|r||r|}
+\hline
+n & 3^{n-1} \pmod{n} & 5^{n-1} \pmod{n} & 7^{n-1} \pmod{n} & \text{Prime\ or\ Composite?} \\
+\hline
+& 1 & 1 & 1 & P \\
+&  &  & 4547 & C \\
+* & &  & & C \\
+* & & & & C \\
+& 1 & 1 & 1 & P \\
+* & & & & C \\
+& 4466 & & & C \\
+& 1 & 1 & 1 & P \\
+\hline
+\end{tabular}
+</math></center>
+The numbers with asterisks are either trivially divisible by <math>3</math> or <math>5</math>. For the numbers that are denoted with <math>P</math>, we can be reasonably sure that they are primes, which they indeed turn out to be. However, we cannot be completely sure that they are prime, due to our lack of randomness in choice of bases for the exponents, and because we only carried out a small number of tests.
+) Note that Caleb does not actually need to know Blase's bid <math>x</math>, as Caleb only needs to send <math>E(2x)</math>. By the statements of RSA, we know that Blase sent <math>E(x) \equiv x^e \pmod{n}</math>, where <math>e,n, E(x)</math> are public. Caleb then wants to send <math>E(2x) \equiv (2x)^e \equiv 2^ex^e \equiv \boxed{2^eE(x) \pmod{n}}</math>. It is computationally easy for Caleb to perform this exponentiation (just as it was for Blase) and multiplication, and he has sufficient information.
+) <math>47^{1395} \equiv (-1)^{1395} \equiv -1 \equiv \boxed{47} \pmod{48}</math>, as <math>1395</math> is odd.
+) <math>4^{3207} \equiv 4^{5} \times 4^{3202} \equiv 1024 \times 4^{3202} \equiv 0 \times 4^{3202} \equiv \boxed{0} \pmod{1024}</math>.
+) The following code can factor the product of two primes (MATLAB's factoring function only works for numbers <math>< 2^{32}</math>, so we scaled down all of the requested answers by <math>2\times</math>)
+<pre>
+p = input('Enter prime 1: ')
+q = input('Enter prime 2: ')
+tic
+factor(p * q)
+toc
+</pre>
+<center><math>
+\begin{tabular}{|r||r|r|r|}
+\hline
+\text{bits} & p & q & \text{time} \\
+\hline
+& 3 & 2 & 0.013334 \\
+& 11 & 13 & 0.013267 \\
+& 129 & 227 & 0.013529 \\
+& 803 & 937 & 0.012896 \\
+& 3203 & 3701 & 0.012944 \\
+& 33893 &47339 & 0.016408 \\
+\hline
+\end{tabular}
+</math></center>
+There is not a very strong correlation between the size of the primes because the used numbers are not particularily large. However, the quickest factoring algorithms (elliptic curve, quadratic sieve, and general number field sieve), run in sub-exponential time when it attempts to factor huge numbers.
+) <math>\left(x^{-1}\right)x \equiv 1 \pmod{n}</math> can be rewritten as <math>\left(x^{-1}\right)x + kn = 1 \quad (*)</math> for some integer <math>k</math>. We know that there are solutions to <math>ax + by = c</math> if <math>c = \text{gcd}\,(a,b)</math>, which indeed is the case here as <math>\text{gcd}\,(41,167) = 1</math>. Thus <math>x^{-1}</math> exists.
+To find it, we perform the Extended Euclidean Algorithm on <math>(*)</math>:
+<center><math>\begin{align*}
+&= 4\times 41 + 3 \\
+&= 13 \times 3 + 2 \\
+&= 2\times 1 + 1 \\ \\
+\Longrightarrow 1 &= 3 - 1\times 2 \\ &= 3 - 1 \times (41 - 13 \times 3) \\ &= (14) \times 3 + (-1) \times 41 \\ &= (14)(167-4\times 41) + (-1) \times 41 \\ &= 14 \times 167 - 57 \times 41
+\end{align*}</math></center>
+Thus <math>x^{-1} \equiv -57 \equiv \boxed{110} \pmod{167}</math>.
+) For RSA, one step involves computing <math>d</math> such that <math>d \times e \equiv 1 \pmod{\phi(n)}</math>. The existence of such <math>d \equiv e^{-1}</math>, from the previous question, requires that <math>1 = \text{gcd}\,(\phi(n),e) = \text{gcd}\,((p-1)(q-1),e) = \text{gcd}\, (10 \times 12, 8) = 8</math>. This is a contradiction, and thus <math>d</math> does not exist.