Exercise 2.4.18* (Difficulties with Pollard $p-1$ method)

Proof.

a)

I we use the same instructions than in Problem 17 for $m=1891$, we obtain

     In [1]: from math import gcd
     
     In [2]: m = 1891
     
     In [3]: r = 2
        ...: for n in range(2,8):
        ...:     r = pow(r,n,m)
        ...:     print(n, ’=>’, gcd(r-1,m))
        ...:
     2 => 1
     3 => 1
     4 => 1
     5 => 1891
     6 => 1891
     7 => 1891

This gives not a proper divisor of $m=1891$, because the two factors $p=31$ and $q=61$ of $1891=31\times 61$ are such that

$$\begin{array}{llll}\hfill & p-1\nmid 4!,p-1\mid 5!,& \hfill & \\ \hfill & q-1\nmid 4!,q-1\mid 5!.& \hfill & \end{array}$$

Therefore $31\times 61\mid d_5=(2^{5!}-1)\wedge m$, but $31\nmid d_4,61\nmid d_4$.

b)

These difficulties might be overcome if we change the initial value of $r$ (or if we use another algorithm!). For $r=5$, $d_n=(5^{n!}-1)\wedge m$.

     In [4]: r = 5
     
     In [5]: for n in range(2,8):
        ...:     r = pow(r,n,m)
        ...:     print(n, ’=>’, gcd(r-1,m))
        ...:
     2 => 1
     3 => 31
     4 => 31
     5 => 1891
     6 => 1891
     7 => 1891

We obtain the non trivial factor $d_3=31$, because $31\mid 5^{3!}-1=15624=2^3\cdot 3^2\cdot 7\cdot 31$.

c)

We give a more convenient program, with an optional parameter $r$:

     In [1]: from math import gcd
     
     In [2]: def pollard(m, r=2):
        ...:     n = 2
        ...:     while gcd(r - 1, m) == 1:
        ...:         r = pow(r, n, m)
        ...:         n += 1
        ...:     return gcd(r - 1, m)
        ...:
     
     In [3]: pollard(199934971)
     Out[3]: 16193
     
     In [4]: pollard(1891)
     Out[4]: 1891
     
     In [5]: pollard(1891, 5)
     Out[5]: 31
     
     In [6]: pollard(7081)
     Out[6]: 7081
     
     In [7]: pollard(7081, 5)
     Out[7]: 73
     
     In [8]: pollard(7081, 6)
     Out[8]: 97
     
     In [9]: 73 * 97
     Out[9]: 7081
     
     In [10]: F6 = 2 ** (2 ** 6) + 1
     
     In [11]: pollard(F6, 3)
     Out[11]: 274177

So

$$F_6=2^{2^6}+1=18446744073709551617=274177\times 67280421310721.$$