Exercise 2.4.17* (Factorize $387058387$ by Pollard $p-1$ method)

Question

Find a proper divisor of $m = 387058387$ by evaluating $d_{100}$, in the notations of the preceding problem.

Richard Ganaye · Accepted Answer

\begin{proof} 
Since $2^{100!} - 1 > 2^{10^{157}}$ is far greater than the capacity of our computer, we must avoid this calculation to evaluate $d_{100}$.

If we define $r_n$ by 
$$r_n \equiv 2^{n!} \pmod m,\quad  0 \leq r_n < m,$$
then $r_1 = 2$ and $r_{n+1} \equiv r_n^{n+1} \pmod m$.

Moreover, $r_n = 2^{n!} + k m$ for some integer $k$, thus
$$(r_{n} -1) \wedge m = (2^{n!} - 1 + km ) \wedge m = (2^{n!} - 1) \wedge m =d_n.$$
This gives the following ipython code:

\begin{verbatim}
In [1]: from math import gcd
In [2]: m = 387058387
In [3]: r = 2
    ...: for n in range(2, 101):
    ...:     r = pow(r, n, m)
    ...:     print(n, '=>', gcd(r - 1, m))
    ...: 
\end{verbatim}
which gives
\begin{verbatim}
2 => 1
3 => 1
4 => 1
...
95 => 1
96 => 1
97 => 461333
98 => 461333
99 => 461333
100 => 461333
\end{verbatim}
This gives $d_{100} = 461333$, so $461333$ is a factor of $m =  387058387$

$$ 387058387 = 461333 	imes 839.$$
\end{proof}

Exercise 2.4.17* (Factorize $387058387$ by Pollard $p-1$ method)

Answers

Comments

Exercise 2.4.17* (Factorize $387058387$ by Pollard $p-1$ method)

Answers

Comments

Add answer