5
$\begingroup$

What is the largest integer that can be factored by modern algorithm like Msieve and GGNFS in a time less than 5 hours with normal computers?

For example, can an integer like 6764305444023748746863375505235232356330698800019155741251564477831918942242883171154012150590008894127708940364431129

be factored in less than 5 hours?

$\endgroup$
  • $\begingroup$ "... in a time less than 5 hours" on what? $\;$ $\endgroup$ – user991 Apr 24 '15 at 9:34
  • $\begingroup$ @RickyDemer On regular computers, PC's ... $\endgroup$ – Lisbeth Apr 24 '15 at 9:39
  • 1
    $\begingroup$ I'm pretty sure the answer is either a prime or a power of two, since those are really easy to factor. $\hspace{.5 in}$ $\endgroup$ – user991 Apr 24 '15 at 9:49
  • 2
    $\begingroup$ @tylo GNFS depends on the size of the number. But some other algorithms like ECM depend on the size of the smallest factor. If your factors are small enough so that ECM is faster, then the cost will depend on the size of the factors. If all the factors are big enough so that GNFS is faster, the size of the factors doesn't matter. $\endgroup$ – CodesInChaos Apr 24 '15 at 10:41
  • 1
    $\begingroup$ I can factor $2^n$ for arbitrary $n$. You might want to clarify the question to ask for the factorization of a random semiprime with $p$ and $q$ of a given size. $\endgroup$ – Stephen Touset Jun 26 '15 at 23:48
2
$\begingroup$

What is the largest integer that can be factored in 5 hours with a normal computer?

That depends on a number of points.

What do you consider a "normal" computer?
A 2015 Gamer-PC with a high-end quad (4) or octo (8) core CPU and more than one graphics card?
A 2010 Gamer-PC with a back-then modern CPU and a modern GPU?
A 2012 Multimedia-PC with a "weak" GPU and a moderate CPU (i5 class)?
A 2014 Workstation with two 18-core Intel Xeons and 4 deep-learning GPUs?
A standard office PC for the IT-department (featuring Gaming CPUs without dedicated GPUs)?
A standard office PC for non-IT people (having a starter-class CPU (=i3) and no dedicated GPU)?
A 2011 Ultrabook for 1k USD back then?
The term "normal" computer can't be quantified, however in the rest of the answer I'll explain how to calculate the upper limit on your PC, provided you measure one data-point.

Now to the general methodology to get the desired bitlength on any PC you can run a test on.
Find a program or library that offers the mentioned factoring algorithm and construct a composite number with the required properties. Note the bitlength of the main run-time affecting variable (length of composite number, length of smallest prime, etc.) and then measure the actual run-time (in seconds or whatever you like). Now if the algorithm has running time $\mathcal O(f(x))$, build the equation $\frac{f(x)}{f(x_{test})}=\frac{runtime}{runtime_{test}}$ and solve the equation $f(x)=f(x_{test})*\frac{runtime}{runtime_{test}}$ using your desired maximal run-time as $runtime$ (e.g. 5h).
If the run-time is given as $L_x[\alpha,c]:=\exp((c+o(1))(\ln\ln x)^{1-\alpha}(\ln x)^\alpha)$, then you need to calculate the $o(1)=\frac{\ln runtime}{(\ln\ln x)^{1-\alpha}(\ln x)^\alpha}-c$ and then you can solve the equation $L_x[\alpha,c]=runtime$ for either $runtime$ or $x$, depending on your needs.

Now a list of algorithms that need to be considered before asking for an upper limit. Each of them has their proper upper limit.

  1. The most generic and best algorithm: The general number field sieve (GNFS), it's run-time only depends on the size of the modulus $n$ ($n$ is the actual modulus). The run-time is $L_n[1/3,(64/9)^{\frac{1}{3}}]$.
  2. The next interesting algorithm is the special number field sieve (SNFS) with a running-time of $L_n[1/3,(32/9)^{\frac{1}{3}}]$. The drawback is that it only works against few composite numbers, see Wikipedia for the details.
  3. The elliptic curve factorization method (ECM) has a run-time of $L_p[1/2,\sqrt{2}]$ with $p$ being the smallest prime-factor of the number to be factored.
  4. It is possible to check (and factor) for a number $n$ to be a perfect power using $\mathcal O((\ln n)^2)$ operations (= run-time).
  5. Pollard-rho factoring can find a prime factor $p$ in $\mathcal O(\sqrt{p})$ time, so it's a good choice if moduli are made of several medium-sized primes (150-bits).
  6. The Pollard p-1 factoring allows to factor a number $n=p*(n/p)$ in $\mathcal O(B*\ln n / \ln B)$ if the prime factorization of $p-1$ only contains primes smaller than $B$. Williams $p+1$ algorithm does the same for $p+1$.
$\endgroup$
  • $\begingroup$ @fgrieu, thank you, after your comment I noticed that $\mathcal O(\exp(c*...))\neq \exp((c+o(1))*(...))$. I'll fix the answer accordingly $\endgroup$ – SEJPM Jun 27 '15 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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