0
$\begingroup$

When I first started studying RSA, I found that I need to know Euler's theorem, to understand that I need Fermat's theorem, and to understand that, I need the order theorem of Lagrange which I am trying but don't understand as I never had mathematics as a subject. Everything I did is from my own.

I want to understand more visually rather than just maths.

I reckon from other posts, that to understand the relation of $N$ in RSA which is the composite prime of $pq$, with the Totient of $N$, I need to understand group and order. Which I don't. Other problems of RSA are for crypto.exchange. But this part of maths I want to understand first.

If you would be kind enough to explain, I would be so glad. Thanks :)

| cite | improve this question | | | | |
$\endgroup$
2
$\begingroup$

Lagrange's theorem is one of the most useful theorems in group theory. It just says that the order of any subgroup of a finite group $G$, divides the order of the group. That is, $H\le G\implies |H|||G|$.

Lagrange's theorem implies Fermat's little theorem, because the multiplicative group of the field of order $p$ has order $p-1$. Hence the order of any element $a$ such that $(a,p)=1$ must divide $p-1$. So $a^{p-1}\cong1\pmod p$.

You don't actually need Fermat's little theorem to understand Euler's theorem: more the other way around. The former is a special case of the latter. That is, Euler's theorem generalizes Fermat's little theorem to $(a,n)=1\implies a^{\varphi(n)}\cong1\pmod n$, where $\varphi$ is Euler's totient function. The totient function counts the number of relatiely prime numbers to n less than n, also called totatives. Thus $\varphi(p)=p-1$.

Not sure about the applications to cryptography. I have used these ideas in group theory and number theory more. Maybe you could ask a specific question from cryptography and we could try to answer it. For the applications I refer you to this answer: https://math.stackexchange.com/a/20193/403337.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.