How would you compute $10^{221}$ mod $13$ by repeated squaring? I just started studying discrete mathematics and I think this would help me in the future. I looked at this example Computing large modular numbers but it kind of didn't make sense to me. Also how could you use Fermat's Little Theorem for this question. Note that I made this questions up myself so I hope it works.
[Math] Arithmetic with Large modular exponent and repeated squaring, such as $10^{221}$ (mod $13$).
discrete mathematicselementary-number-theorymodular arithmetic
Related Solutions
Fermat's Little Theorem: If $p$ is prime and $a$ is an integer, then $a^{p-1}\equiv 1 \pmod p$.
Say we're given a number $a$ and some big exponent $N$ and we want to compute $$a^N\mod p.$$ We know that $a^{p-1}\equiv 1 \pmod p$. In general, if $a_1\equiv x_1\pmod{n}$ and $a_2\equiv x_2\pmod{n}$, then $a_1a_2\equiv x_1x_2\pmod{n}$. Therefore, we have that $$a^{k(p-1)}=\underbrace{a^{p-1}\cdot a^{p-1}\cdot \cdots \cdot a^{p-1}}_{k\text{ times}}\equiv \underbrace{1\cdot 1 \cdot \cdots \cdot 1}_{k\text{ times}}\pmod p\equiv 1 \pmod p. $$ Thus we can ignore the part of $N$ which is the biggest multiple of $p-1$. Writing $N=m(p-1)+r$ where $0\leq r < p-1$, we have $$\begin{eqnarray*}a^N &=& a^{m(p-1)+r}\\&=&\left(a^{p-1}\right)^ma^r\\ &\equiv& 1^ma^r\pmod p\\ &\equiv& a^r\pmod p.\end{eqnarray*}$$ Thus we have reduced this to the much easier problem of computing $a^r\mod p$. If this is still too hard to work out with pen and paper, you might try using the method of repeat squaring.
Recall how RSA works: we have a modulus $n = pq$, and an exponentiation exponent $e$ and a decryption exponent $d$. And $d$ is chosen such that it is the inverse of $e$ modulo $\phi(n) = (p-1)(q-1)$.
( This means that $ed \equiv 1 \mod \phi(n)$, or equivalently $ed = 1 + k\phi(n)$ for some $k \in \mathbb{Z}$. And then Fermat says that $x^{\phi(n)} \equiv 1 \mod n$ and so $(x^e)^d = x^{ed} = x^{1+ k\phi(n)} = x^1 (x^{\phi(n)})^k \equiv x 1^k = x \mod n$, so that exponentiation with $e$ and $d$, modulo $n$, are each other's inverse. )
So you know that $ed - 1$, which you can compute when $e$ and $d$ are known, is a multiple of $\phi(n)$, which is a multiple of 4 (as $p-1$ and $q-1$ are both even). So we can write $ed -1$ as $2^s r$, where $r$ is odd (just divide out factors of 2, $s$ many times, till we are left with an odd number).
You also know that $x^{ed-1} = 1 \mod n$, when $(x,n) = 1$. (If $(x,n) \neq 1$, $(x,n) = p$ or $(x,n) = q$ and we factored $n$; the probability that this happens is of course very small for large enough $p,q$). So picking random such $x$ (or $w$, as in your link) and then computing $x^r \mod n$, $x^{2r} \mod n$, etc., we are sure to get to $1$ eventually (when we have done it $s$ times, we are at $2^s r = ed -1$ and this power gives 1).
Now look at the number $m$ in the sequence of powers starting from $x^r$ and then squaring till we get $1$. We could start with $x^r \equiv 1$ (so no previous) or the power before we get $1$ is equal to $-1$ modulo $n$: we then have found a trivial square root of $1$ (the next squaring gives $1$, and we try another $x$. But if this is not the case (and the probability of this is more than half, as the slide says) we have found a non trivial square root $m$ of $1$, and that number $m$ is $+1$ modulo one prime and $-1$ modulo the other prime (see slide 6 of the linked presentation), so $m+1$ has a non-trivial factor with $n$ and gives us one (and thus both) of the primes.
You might have to try a few different $x$, but in a few tries you'll factor $n$ this way.
Best Answer
First, find $10^2 \pmod{13}=9$. Find $10^4=(10^2)^2\equiv 9^2\equiv 3 \pmod{9}$. Find $10^8=(10^4)^2\equiv 3^2\equiv 9 \pmod{13}$. Find $10^{16}, 10^{32}, 10^{64}, 10^{128}$ by continuing in this fashion. Lastly, write $221$ in base $2$ as $221=128+64+16+8+4+1$. Hence, we can find $10^{221}=10^{128}10^{64}10^{16}10^{8}10^410^210^1$, and we take the whole thing mod $13$ to get $4$.