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

Revision as of 14:47, 9 July 2008

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\}$ (Error compiling LaTeX. Unknown error_msg) 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, 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}$ .

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) MATLAB

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) MATLAB

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/gov school"

Revision as of 14:47, 9 July 2008