5
$\begingroup$

I want to factorize big numbers like 10^100. FactorInteger with no Automatic option can take a lot of time and as I know there is no way to show any progress. So I tried to make a custom function that ends in a short time and will return some result that can be used in future runs. For now I have this one:

FirstFactors[n_Integer, k_Integer, start_Integer : 1] :=
 Module[
  {p, lastP, factors, m, i},
  Monitor[
   p = NextPrime[start]; lastP = p; factors = {}; m = n; i = 0;
   Do[
    If[
     PrimeQ[m], factors = Append[factors, m]; m = 1; Break[],
      lastP = p; 
     If[Mod[m, p] == 0, factors = Append[factors, p]; m = m/p, 
      p = NextPrime[p]]
     ]; i++,
    k
    ];
   {factors, m, p},
   Grid[{{ProgressIndicator[i/k], ToString[N[i/k*100, 3]] <> "%"}}]
   ]
  ]

It implements simple algorithm and it work slooooowly. But I can run it for 10^6 steps and it will take about a minute (after 10^9 steps it will be more than mimute for next 10^6 steps). Then I can run it for 10^6 steps more and start from last checked prime.

There are two main problems:

  1. This algorithm can not be parallelized in simple way
  2. The algorithm itself has too big computational complexity

Any ideas to improve my solution? I need a function that will work for any number, so some methods (i.e. Pollard's p − 1) are not appropriate because they can find only factors having specific form.

Improve this question
$\endgroup$
10
  • $\begingroup$ Would Pollard Rho be general enough for your needs? If so then could you start parallel copies of this, from different starting values or using different polynomials, and let each of them run looking for a cycle. If each needs to stop then could you could save a subset of the history and the next run could begin checking against that history instead of starting from nothing? $\endgroup$
    – Bill
    Sep 13 at 3:59
  • $\begingroup$ @Bill I'm not good in math and I'm not sure Pollard Rho will find factors in finite time. As I know it uses random numbers and polynomials, so you might just miss $\endgroup$
    – Андрей Яндуганов
    Sep 13 at 4:20
  • $\begingroup$ For the size of numbers you are thinking of you could do one step of "divide by next prime" and one step of Pollard Rho and repeat both until you are done. If you have it show you which one found a factor first then that might give you some idea how this behaves. I am thinking the method you show will do approximately n/log(n) iterations before finding a prime factor n and pollard rho will do about sqrt(n) iterations before finding the prime factor n. But those are only approximations, please do some testing and average the results you get and see if these are close or not. I hope it works $\endgroup$
    – Bill
    Sep 13 at 5:16
  • $\begingroup$ BUT, as you pointed out, Pollard Rho is random and it won't necessarily find the smallest prime factor first and won't even guarantee to find prime factors, it might find composite factors. But if it works then it might be faster cracking big numbers and you can work from there. $\endgroup$
    – Bill
    Sep 13 at 5:23
  • 3
    $\begingroup$ Good luck if you want to beat Mathematica's FactorInteger with simple trial division algorithm :-D $\endgroup$
    – azerbajdzan
    Sep 13 at 11:00

2 Answers 2

Reset to default
4
$\begingroup$

Here is a function that takes an integer: m and calculates as many factors as the second arguments: n specifies. It returns a list of factors with their multiplicity and n divided by the factors:

fac[m0_, n_ : 10^3] := Module[{m = m0, facs = {}, tmp, t},
  f0[m_] := (t = FactorInteger[m, 2]; {t[[1]], 
     If[Length[t] == 1, 1, t[[2, 1]]]} );
  While[ tmp = f0[m]; AppendTo[facs, tmp[[1]]]; m = tmp[[2]];
   Length[facs] < n && tmp[[2]] =!= 1
   ];
  {facs, tmp[[2]]}
  ]

Here are some examples:

fac[2 3 5 5]

{{{5, 2}, {2, 1}, {3, 1}}, 1}

fac[2 3 5 5, 1]

{{{5, 2}}, 6}

fac[2 3 5 5, 2]

{{5, 2}, {2, 1}}, 3}

And an example with large numbers:

fac[Round[Pi 10^100], 3]

{{{40, 1}, {27829657397, 1}, {2037015353615688679, 
   1}}, 13854399896362668778324249883514046877923048364212536483950847\
175429409}
Improve this answer
$\endgroup$
2
  • $\begingroup$ As you use FactorInteger you can not be sure computations will end e.g. in an hour. I'm trying to find a way to stop computations at any point and continue from it next time. With FactorInteger if smallest factor is too complex to find it quickly I can not do it. $\endgroup$
    – Андрей Яндуганов
    Sep 13 at 11:33
  • 1
    $\begingroup$ Note that I using FactorInteger with a limit of 2 factors. $\endgroup$
    – Daniel Huber
    Sep 13 at 11:56
4
$\begingroup$

Making FactorInteger[] iterative and monitored:

PrintTemporary@Dynamic@{Clock[Infinity], current, tmp};
FixedPoint[
 (tmp = ReplaceAll[#,
     {p_ /; ! PrimeQ[p], n_} :>
      Sequence @@ (FactorInteger[current = p, 2] . 
         DiagonalMatrix[{1, n}])
     ]) &,
 {{Times @@ Table[2^k + 1, {k, 100, 105}], 1}}]
(*
{{61681, 1}, {26317, 1}, {13669, 1}, {5419, 1}, {3061, 1}, {953, 
  1}, {409, 1}, {401, 1}, {331, 1}, {281, 1}, {257, 1}, {211, 
  1}, {137, 1}, {43, 1}, {17, 1}, {13, 1}, {11, 1}, {3, 4}, {5, 
  1}, {86171, 1}, {2787601, 1}, {340801, 1}, {664441, 1}, {1564921, 
  1}, {3173389601, 1}, {1326700741, 1}, {415141630193, 
  1}, {8142767081771726171, 1}, {78919881726271091143763623681, 
  1}, {845100400152152934331135470251, 1}}
*)

Factoring is a bad candidate for parallelization (I believe), but since parallelization was asked for:

PrintTemporary@Dynamic@{Clock[Infinity], tmp};
FixedPoint[
  (tmp = ParallelMap[
      Replace[#,
        {{p_ /; ! PrimeQ[p], n_} :>
          Sequence @@ (FactorInteger[p, 2] . DiagonalMatrix[{1, n}]),
         {p_, n_} :> {p, n, False}}
        ] &,
      #
      ]) &,
  {{Times @@ Table[2^k + 1, {k, 100, 105}], 1}}] /. False -> Nothing
(*
{{61681, 1}, {26317, 1}, {13669, 1}, {5419, 1}, {3061, 1}, {953, 
  1}, {409, 1}, {401, 1}, {331, 1}, {281, 1}, {257, 1}, {211, 
  1}, {137, 1}, {43, 1}, {17, 1}, {13, 1}, {11, 1}, {3, 4}, {5, 
  1}, {86171, 1}, {2787601, 1}, {340801, 1}, {664441, 1}, {1564921, 
  1}, {3173389601, 1}, {1326700741, 1}, {415141630193, 
  1}, {8142767081771726171, 1}, {78919881726271091143763623681, 
  1}, {845100400152152934331135470251, 1}}
*)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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