Factoring semiprimes cost estimation

Question

I have two problems that are the following. The first problem is the following: I need to estimate the cost of factorizing a given semiprime based on previous estimations. For example I have the time it takes to estimate 187 and 33, if I receive 106 to factorize how could I estimate its cost based on the 187 and 33 estimations?

The second problem is the following, when I have no information, how I could I estimate the cost with no previous information?

The algorithm we are using are the following:

public ArrayList<BigInteger> calcPrimeFactors(BigInteger num) 
{                
    if (num.compareTo(one)==0) {
      return factors;
    }

    while(num.remainder(divisor).compareTo(zero)!=0) {
      divisor = divisor.add(one);
      //System.out.println("Divisor " + divisor);
      //count++;
    }
    factors.add(divisor);
    return calcPrimeFactors(num.divide(divisor));
 }

Thanks

Answer 1

If you write your algorithm out in English, it is something like the following: while the number is not 1, try dividing it by every number in order, beginning with 1. Every time we find a factor, divide the original number by the factor, then continue on.

To take 187 as an example, you first try all divisors less than 11 unsuccessfully, then find that 11 is a factor, so divide by 11 and are left with 17, with "divisor" still equal to 11. Then in the recursive call, you check 17 for divisors from 12 to 16 unsuccessfully, before finding that 17 is a divisor. So in total, you checked 17 potential divisors.

Hopefully it is clear from the above example that the number of divisors you check will always be equal to the larger of the two prime factors. This means that the number of divisors you have to check varies a lot depending on the factorization of the number in question. If $n = p^2$ for some $p$, then you will only need about $p = \sqrt{n}$ checks, whereas if $n = 2p$ for some $p$, then you will need about $p = \frac{n}{2}$ checks.

This makes it difficult to predict the time needed based on previous results. Say $m = 2p$ and took $t$ time to factor, and we want to know how much time it will take to factor $n$. Factoring $m$ took $p$ steps, so we can estimate each step to take about $\frac{t}{p}$ time. If $n = 2q$, then $n$ will take $q$ steps to factor, so should take about $q \frac{t}{p} = \frac{n}{2} \frac{t}{m/2} = \frac{nt}{m}$ time. If, on the other hand, $n = q^2$, we would instead expect $q \frac{t}{p} = \sqrt{n} \frac{t}{m/2} = \frac{2t \sqrt{n}}{m}$ time. Of course, we are making a lot of simplifying assumptions here; for one thing, each "step" doesn't take the exact same amount of time, since it will be slower to try dividing by a larger number than by a smaller number. If you care about accuracy beyond a very rough estimate, likely the best thing to do is find a library that can time functions, and time examples of different size to see how the time actually grows. In general there are too many complicated interactions (hardware, compiler, etc.) that affect the amount of time code takes to run to accurately predict runtimes based on calculations alone.

I also feel compelled to point out that if you are interested in factoring larger numbers quickly, your algorithm is VERY slow. There are many well-known, complicated algorithms for factoring, but even some simple changes will speed your algorithm up by a lot. Notice that in the worst case your algorithm takes about $\frac{n}{2}$ steps, but since factors occur in pairs whose product is $n$, one of the numbers in the pair must be at most $\sqrt{n}$. Thus if you have checked every factor up to $\sqrt{n}$, you know whatever is left is prime. Furthermore, if you are only interested in semiprimes, you may as well just stop as soon as you find the first factor. This will bring the worst case down to only $\sqrt{n}$ steps instead of $\frac{n}{2}$. There will still be a similar complication with estimating the time, since the best case would now be only 2 steps instead of $\sqrt{n}$.