0
$\begingroup$

I am trying to factorize large prime numbers with the code bellow. The code works properly for values like 1927 and 69527 (results), but gives no result for larger values like 655051. The code goes as follows:

myfunction[n_, B_] :=Module[{a, g, i},
    a=2;
    i=2;
    g=1;
    While[i<B && g==1,
        a=PowerMod[a,i,n];
        g=GCD[a-1,n];
        If[g>1&&g<n,Return[g]];
        i=i+1];
]

This works myfunction[69527,11] But this doesn't myfunction[655051,100] Any idea what might be the problem?

$\endgroup$
9
  • 3
    $\begingroup$ Maybe a trivial question, but why factorize prime numbers? $\endgroup$
    – A.G.
    May 1 at 18:13
  • 1
    $\begingroup$ Is pollard the same as myfunction? $\endgroup$
    – Michael E2
    May 1 at 18:17
  • 1
    $\begingroup$ Consider that myfunction[69527, 9] fails and myfunction[864109, 55] succeeds. $\endgroup$
    – Michael E2
    May 1 at 18:21
  • 1
    $\begingroup$ B must be big enough that the Pollard algorithm can run to its end. IIs it really necessary to have this constrain on i ? $\endgroup$ May 1 at 18:49
  • 1
    $\begingroup$ Perhaps instead of PowerMod, you could use the more traditional a = Mod[a^2 + 1, n]. $\endgroup$
    – Michael E2
    May 2 at 2:01
2
$\begingroup$

Note that the Pollard algorithm may fail because it is based on a pseudo random sequence. In this case you may start with a different value from 2. See e.g.: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

Here is a working example where you may specify the start value:

pollard[n_, start_ : 2] := Module[{x, y, d = 1, g, gg},
  x = y = start;
  g[x_] = Mod[x^2 + 1, n];
  gg[x_] = g[g[x]];
  While[d == 1,
   x = g[x];
   y = gg[x];
   d = GCD[x - y, n]
   ];
  If[d == n, "Not found", d]
  ]

With this: "pollard[655051]" does not work or it takes too long, but the following will:

pollard[655051, 3]
(* 661 *)

Further, note, faster than Pollard is the quadratic sieve algorithm.

$\endgroup$

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