What is the relation between RSA & Fermat's little theorem? I came across this while refreshing my cryptography brain cells.

From the RSA algorithm I understand that it somehow depends on the fact that, given a large number (A) it is computationally impossible to derive at the two prime numbers (B &amp; C) whose product it is.

But that isn't the Fermat Theorem, is it?
It's something on the lines of showing that there is no solution $n$ ($n > 2$) such that: $X^n + Y^n = Z^n$.

Can someone throw some light on this?
To walk you through RSA from start to end, here's how it works.


Choose two large distinct primes $p$, $q$. Calculate $n=pq$.
Calculate $\phi(pq)$. This happens to be $(p-1)(q-1)$.
Choose $e$ such that $gcd(e, \phi(pq)) = 1$ and $1 &lt; e &lt; \phi(pq)$.
Compute $d$ such that $de = 1 \mod \phi(pq)$.
Do some crypto; $c = t^e \mod n$ and $t = c^d \mod n$.


What you really want to know is why these statements hold. Fermat's little theorem states that $a^p = a \mod(p)$ An alternative, equivalent definition is that $a^{p-1} = 1 \mod(p)$.

Actually, for the purposes of RSA, that's insufficient. What you want is a generalisation called the Euler-Fermat generalisation, which states:

$$a^{\phi(n)} = 1 \mod{n}$$
Next up - what the hell is this $\phi(x)$ function? In plain English, it's the number of numbers less than or equal to $x$ which are also coprime to it. For any given prime $p$, every number less than itself is coprime to it, which means $\phi(p) = p-1$. If you're wondering about why $\phi(1) = 1$, well, $gcd(x, 1) = 1$ is the definition of coprimality, including for 1 itself.

Now, it's also possible to prove that $\phi(xy) = \phi(x)\phi(y)$. Unless someone really wants me to, I'll skip the details (see a textbook on number theory) but, this essentially means $n = pq \Rightarrow \phi(n)=\phi(p)\phi(q) \Rightarrow \phi(n)=(p-1)(q-1)$.

Now, a little group theory too. Multiplication for certain sets of positive integers forms a group under modulo provided all the elements you pick for it are coprime to the modulo you're using. It so happens we've picked $e$ to be co-prime to our modulo $\phi(pq)$. Group theory guarantees us the existence of an integer in the group that acts as an inverse uniquely for that integer and transforms, under multiplication, that integer to the identity. The identity element under multiplication is $1$ and the inverse here is $d$.

So, let's recap: we've got $e$ and we've got $d$. One is the inverse of the other under the group $\phi(n)$. What we need is a link back to the Euler Fermat generalisation showing this:

$$ t = ((t^e)^d) = t^{ed} \mod (n) $$

So, before we do that let's just review what we understand by congruences. If I have the number $4 \mod (9)$, are you happy that $13 = 4 \mod(9)$? And that $22 = 4 \mod 9$? And that $31 = 4 \mod (9)$? You should see a patter emerging here; in fact, your general representation in this case is $4 + 9k$ generates you the set of numbers that are equivalent to $4$ modulo $9$.

So, $de = 1 \mod \phi(pq)$ could be expressed as $de = 1 + k\phi(pq)$, yes? I.e. to 1, I can add multiples of $\phi(pq)$ then apply modulo $phi(pq)$ and it'll be equivalent to 1. 
This might take some getting your head around.

Once you've got there, $t^{ed} = t^{1+k\phi(pq)} \mod (pq)$. All I've done is substitute one expression for the other; no magic. Now a little re-arranging: $t^{1+k\phi(pq)} = t^1 t^{k\phi(pq)} \mod (pq)$ then $t^{1}t^{k\phi(pq)} = t^1 (t^{\phi(pq)})^k \mod (pq)$. 

Now, we use the Euler-Fermat generalisation. Notice we have $t^{\phi(pq)} \mod (pq)$. Being "under modulo", we can still evaluate this, since the power to the $k$ simply means multiplying $k$ lots of that expression together. So now, apply the theorem:

$$t^{\phi(pq)} = 1 \mod (pq)$$

and we're left with $t^1 (t^{\phi(pq)})^k = t^1 \times (1)^k \mod (pq)$, which as you probably know is just $t$.

So, that is how they relate. This isn't the only way to prove RSA either. The Chinese Remainder Theorem proof I think is nicer, but I also think it is harder to understand.