# User talk:Azjps/sandbox

1) Note that , so . It requires multiplications to find , and by repeatedly squaring, we can find and so forth. Each squaring requires one multiplication, and so we can achieve using multiplications. Substituting into , we find that our expression requires more multiplications. Thus, multiplications are sufficient.

2)

\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. ! Missing $ inserted.)Since each of are distinct (and consequently is a permutation of ), then both are generators with respect to the given modulos.

3) By the Euclidean Algorithm, .

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

By trial-and-error, we can easily find that satisfies these conditions, which must be the distinct solution due to the Chinese Remainder Theorem (and since ). Since this year we only have students at Governor's School, we will assume that is the desired answer, and that we let our counselors pose as students (just kidding).

Alternatively, we could note that and that using the Extended Euclidean Algorithm or by inspection, and thus the answer is .

5) Consider computing (this is not really necessary, since we could simply reduce if ). Assume that it is computationally easy to compute the product of two numbers, both . Notice then that it is computationally easy to find (which requires just one multiplication, and the numbers are not extremely large as ). Similarly, it is computationally easy to reduce . Suppose we express in binary form, with digits (for the given problem, ). Then . Each of these terms being multiplied together can be found by squaring , times (as established above, 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

Using the Chinese Remainder Theorem repeatedly, the answer comes out to be , which indeed fits the conditions (of course then is the desired answer). Work: solving the first two congruences, and then the second two (by trial-and-error), yields

Here we notice that happens to be , which helps us to quickly determine the inverses: and . Then by the Chinese Remainder Theorem, we have .

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 is a publically known one-way function, an observer could simply carry out on the previously generated bits (let , then given , the outsider can easily carry out ), and determine the next bit him/herself. Note that the observer does not need to know the value of the seed , while in the first construction the observer would still need to know .

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 , and sends to Blase (if desired, Andy can also send the length of his message, , to Blase). Blase then generates a one-time pad, , and sends back to Andy (squaring is computationally easy). Now Andy can use the Rabin decryption algorithm to find the value of .

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

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

\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. ! Missing $ inserted.)The numbers with asterisks are either trivially divisible by or . For the numbers that are denoted with , 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 , as Caleb only needs to send . By the statements of RSA, we know that Blase sent , where are public. Caleb then wants to send . It is computationally easy for Caleb to perform this exponentiation (just as it was for Blase) and multiplication, and he has sufficient information.

11) , as is odd.

12) .

13) The following code can factor the product of two primes (MATLAB's factoring function only works for numbers , so we scaled down all of the requested answers by )

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

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) can be rewritten as for some integer . We know that there are solutions to if , which indeed is the case here as . Thus exists.

To find it, we perform the Extended Euclidean Algorithm on :

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. ! Package amsmath Error: \begin{align*} allowed only in paragraph mode.)Thus .

15) For RSA, one step involves computing such that . The existence of such , from the previous question, requires that . This is a contradiction, and thus does not exist.