this is for holding javascript data
Francesco Romeo added section_Pollard_mathbf_p_1__.tex
about 8 years ago
Commit id: 486db751e475f7987ce10f49b27210940d94be7f
deletions | additions
diff --git a/section_Pollard_mathbf_p_1__.tex b/section_Pollard_mathbf_p_1__.tex
new file mode 100644
index 0000000..ff37f14
--- /dev/null
+++ b/section_Pollard_mathbf_p_1__.tex
...
\section*{Pollard $\mathbf{p-1}$}
To find $p$ and $q$, the two prime factors of $N$, we could use the \textbf{Pollard $\mathbf{p-1}$} method.
We consider this fact:\\
if exists a number $L$ such that $$(p-1) | L \ \ \ and \ \ \ (q-1) \not\vert L $$ then
$$a^{L} \ \ mod \ N \ \ \Rightarrow \begin{cases} a^{L} \equiv_{p} a^{k \cdot (p-1)} \equiv_{p} 1 \\ a^{L} \equiv_{q} a^{h \cdot (q-1)+r}
\equiv_{q} a^{r} \not \equiv_{q} 1
\end{cases}$$
and from the first one we get
$$a^{L}-1 \equiv 0 \ \ mod \ p$$
that implies
$$gcd(a^{L}-1,N)=p$$
so we find one of the two factors!!
In the practice, we take $a=2$ and to execute the algorithm faster, we take the 2 powers of the form $2^{k!} $ with $k \in \mathbb{N}$.
The prime numbers used today in RSA Cryptosystems are the \textbf{Safe Primes}: they have form $p=2q+1$ with $q$ large prime. Taking two large safe primes, the factorization of $N$ using the method above is computationally infeasible.
