# Relation between $N = P \times Q$, and $\Phi(N)$

When studying RSA, and proving simple concepts to myself, I went and understood groups and rings, but I failed to understand Lagrange's theorem.

I did understand how from invertible finite groups I could derive Euler's theorem and Fermat's little theorem, etc. But one point remained...

When extracting the invertibles from $$N \rightarrow U(N)$$, we get the elements which form a group. I also saw that the order of any element in that belongs to $$U(N)$$, which is the order of $$U(N)$$. For example, if the number $$10$$ is $$N$$, $$1,3,7,9$$, it forms a group under multiplication $$\bmod 10$$. Now any element $$a$$, let it be $$7$$, the order of $$7$$, is $$4$$, which is also the sum total of the co-primes or the order of $$U(N)$$. This proves Euler's theorem, and thus, Fermat's as well. But when doing RSA, we do the same thing; however, during key generation, we choose a number that is a co-prime to the order of $$U(N)$$, which also does from an invertible group $$1$$ and $$4$$.

Therein lies the rub, which I don't understand at this moment. What does the order of $$U(N)$$ have to do with key generation?

I have been unable to find a direct visual link. Ultimately, we are not choosing an element $$E$$ that belongs to $$U(N)$$, but an element that forms a group under $$U|U(N)|$$. And again, when encrypting, we are doing $$M^{ed} \bmod N$$.

I am not getting the relation between $$U(N)$$ and the number of elements in $$U(N)$$ when we are not using the order as an exponent to any element within $$U(N)$$ to get $$1$$ or something like that. Why are we generating the key from the number of elements in $$U(N)$$, and why does it work? What's the relation?

• It is not proving Euler's theorem, it just justifies it. – kelalaka Mar 12 at 15:33

What does the order of $$U(N)$$ has to do with RSA key generation?

The usual notation is $$\Bbb Z_N^*$$ for the multiplicative group modulo $$N$$, that the question names $$U(N)$$, and $$\Phi(N)$$ or equivalently $$\varphi(N)$$ for its order (number of elements), as given by Euler's totient function.

$$\forall x\in\Bbb Z_N^*$$, it holds $$x^{\Phi(N)}\equiv1\pmod N$$. This implies: $$\forall x\in\Bbb Z_N^*,\ \forall k\in\Bbb N,\ \text{ it holds }\ x^{(k\,\Phi(N)+1)}\equiv x\pmod N\tag{1}\label{eq1}$$

We want the RSA encryption exponent $$e$$ and decryption exponent $$d$$ (both strictly positive integers) to be such that textbook RSA encryption of a plaintext $$m$$ followed by decryption consistently returns the original plaintext. That is, we want that $$\forall m\in[0,N)$$, it holds $$((m^e)\bmod N)^d\bmod N=m$$. We can write this goal as: $$\forall m\in[0,N),\ \text{ it holds }\ m^{(e\,d)}\bmod N=m\tag{2}\label{eq2}$$

We can now see what $$\Phi(N)$$ has to do with RSA key generation: if $$e\,d\equiv 1\bmod\Phi(N)\tag{3}\label{eq3}$$ then by definition of that, and given that $$e$$ and $$d$$ are strictly positive integers, $$\exists k\in N$$ such that $$e\,d=k\,\Phi(N)+1$$, and we nearly can use $$\eqref{eq1}$$ to prove that $$\eqref{eq2}$$ holds. The one gap is that we only prove the weaker $$\forall m\in[0,N),\ \text{ if }\ \gcd(m,N)=1\ \text{ then }\ m^{(e\,d)}\bmod N=m\tag{2'}\label{eq2'}$$

We have proven that condition $$\eqref{eq3}$$ is sufficient to insure that textbook RSA encryption of a plaintext $$m$$ followed by decryption returns the original plaintext, at least when $$\gcd(m,N)=1$$. Since $$N$$ is the product of large primes, $$\gcd(m,N)=1$$ holds for most $$m$$.

Further, under the extra condition that $$N$$ is squarefree (including $$N=p\,q$$ with $$p$$ and $$q$$ distinct primes), it can be proven that for all $$m$$ textbook RSA encryption followed by decryption returns the original plaintext.

Otherwise said: one way to see RSA is as working with message and ciphertext in the group $$(\Bbb Z_N^*,*)$$, but that restricts the message space. It can be extended to $$(\Bbb Z_N,*)$$ when $$N$$ is squarefree, that is when $$N$$ is not divisible by the square of any prime.

We first prove that $$\eqref{eq3}$$ implies that $$m^{(ed)}-m\equiv0\pmod{p_i}$$ for each prime $$p_i$$ dividing $$N$$, by treating separately the case $$m\equiv 0\pmod{p_i}$$. The integer $$m^{(ed)}-m$$ is thus divisible by each $$p_i$$, thus by their product, which is $$N$$ when $$N$$ is squarefree, thus $$m^{(ed)}-m\equiv0\pmod N$$.

Notice that the condition $$\eqref{eq3}$$ is sufficient, but not necessary. For a necessary and sufficient condition, we want $$e\,d\equiv 1\bmod\lambda(N)\tag{3'}\label{eq3'}$$ where $$\lambda$$ is the Carmichael function.

Notations:

• $$\forall$$ is read "for all". $$\in$$ is read "in". $$\exists$$ is read "exists".
• $$\Bbb N$$ is the set of natural numbers: $$\Bbb N=\{0,1,2,3,4,5,\ldots\}$$.
• $$\Bbb P$$ is the subset of $$\Bbb N$$ consisting of primes: $$\Bbb P=\{2,3,5,7,11,\ldots\}$$.
• $$\Bbb Z$$ is the set of (signed) integers: $$\Bbb Z=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$$.
$$(\Bbb Z,+)$$ is a group.
• $$x\equiv y\pmod n$$ is read "$$x$$ is equivalent to $$y$$ modulo $$n$$".
It means that $$n$$ exactly divides $$x-y$$ (for $$n$$ a strictly positive integer).
Alternative notations are $$x\equiv y\ \ [n]$$ or $$x=y\pmod n$$ or $$x=y\ \ [n]$$.
• $$x=y\bmod n$$ is read "$$x$$ is set to $$y$$ modulo $$n$$" or "$$x$$ equals $$y$$ modulo $$n$$".
It means that (after the setting, if any) $$0\le x and $$x\equiv y\pmod n$$ (see above for the meaning).
When $$y\ge0$$, the quantity $$y\bmod n$$ is the remainder of the Euclidean division of $$y$$ by $$n$$. The quantity $$y\bmod n$$ is $$0$$ when $$n$$ divides $$y$$ (and the C programmer writesx = y % n for a computation orx == y % n for a test). When $$y<0$$, we can compute $$y\bmod n$$ as $$n-1-((-y-1)\bmod n)$$.
Note: Textbook RSA encryption and decryption reduce their result $$\bmod N$$, ensuring that the ciphertext and the deciphered plaintext are in $$[0,N)$$.
• $$\Bbb Z_n$$ is the finite set of integers modulo $$n$$. That is, the elements of $$\Bbb Z$$ equivalent modulo $$n$$ are regrouped into a single element of $$\Bbb Z_n$$. Thus $$\Bbb Z_n$$ has $$n$$ elements.
$$(\Bbb Z_n,+)$$ is a group. With multiplication noted $$*$$ when not omitted, it becomes the ring $$(\Bbb Z_n,+,*)$$.
When the modulo $$n$$ is prime, $$(\Bbb Z_n,+,*)$$ is a field, because all elements except $$0$$ have a multiplicative inverse. As practice of notation: $$\forall p\in\Bbb P$$, $$\forall x\in\Bbb Z_p$$, if $$x\ne0$$ then $$\exists y\in\Bbb Z_p$$ such that $$x*y=1\pmod p$$ (also noted $$x\,y=1\pmod p$$ as a shortcut).
• $$\Bbb Z_n^*$$ is the set of the elements of $$\Bbb Z_n$$ that have an inverse under multiplication, that is the set of $$x$$ with $$n$$ and $$x$$ having no common positive divisor beyond $$1$$, that is $$\gcd(x,n)=1$$.
$$(\Bbb Z_n^*,*)$$ is a group including when $$n$$ is not prime. It has $$\Phi(n)$$ elements.
• I would love if I could understand it. Being a non mathematics guy, the signs confuse me too much :( – C0DEV3IL Mar 12 at 22:10
• @C0DEV3IL: notation helps a lot. I've added what you need for RSA. Try it, your question suggests that you understand the notions, and only have that little hurdle to pass. – fgrieu Mar 13 at 7:42
• @kelaka: I got that you suggest that I change how I reference equations, but how exactly? – fgrieu Mar 13 at 18:10
• I should change my nickname. I've checked that there is no direct support. However, this answer contains some nice tricks. Does MathJax really limited :) – kelalaka Mar 13 at 18:46