this is for holding javascript data
Francesco Romeo added section_On_Fermat_s_Little__.tex
about 8 years ago
Commit id: 8e0a073691ab4a38f81b70b37baf46bd3dfd7a43
deletions | additions
diff --git a/section_On_Fermat_s_Little__.tex b/section_On_Fermat_s_Little__.tex
new file mode 100644
index 0000000..fe7245f
--- /dev/null
+++ b/section_On_Fermat_s_Little__.tex
...
\section*{On Fermat's Little Theorem}
We said that if we take a prime number $p$, $\forall a \in \mathbb{F}_{p}^{*}$, the Fermat's Little Theorem says us
$$a^{p-1} \equiv 1 \ \ mod \ p $$
It's easy to verify that if we take two primes $p$ and $q$, then
$$a^{(p-1)(q-1)} \equiv 1 \ \ mod \ pq $$
because
$$a^{(p-1)(q-1)} \ mod \ pq \ \ \Rightarrow \begin{cases}
a^{(p-1)(q-1)} \ \ mod \ p \ \ \Rightarrow (a^{p-1})^{q-1} \equiv_{p} 1 \\
a^{(p-1)(q-1)} \ \ mod \ q \ \ \Rightarrow (a^{q-1})^{p-1} \equiv_{q} 1
\end{cases}$$
Then we could present this preposition:
\begin{pps}
Let $p,q$ be primes, $N=p \cdot q$ and $e \geq 1$ such that $gcd(e,(p-1)(q-1))$; we consider $d$ such that
$$ed \equiv 1 \ mod \ (p-1)(q-1) $$
$$THEN$$
the equation $$x^{e} \equiv c \ mod \ N \ \ \ c \in \mathbb{Z}_{N}$$
admitts a unique solution
$$x \equiv c^{d} \ mod \ N $$
\end{pps}
\begin{proof}
We could quickly observe that considering
$$x^{e} \equiv c \ mod \ N$$
and we power it by $d$
$$x^{ed} \equiv c^{d} \ mod \ N $$
then we use the fact that
$$ed \equiv 1 \ mod \ (p-1)(q-1) \ \ \Rightarrow ed= 1 + k(p-1)(p-1)$$
and substituting in the equation above we get:
$$x^{ed} \equiv_{N} x^{1 + k(p-1)(p-1)} \equiv_{N} x \cdot (x^{(p-1)(q-1)})^{k} \equiv_{N} x $$
\end{proof}
This result will be important to set up the RSA Cryptosystem.