What is the running time of this algorithm of prime factorization?

Question

I recently figured out my own algorithm to factorize a number given we know it has $2$ distinct prime factors. Let:

$$ ab = c$$

Where, $a<b$

Then it isn't difficult to show that:

$$ \frac{c!}{c^a}= \text{integer}$$

In fact,

$$ \frac{c!}{c^{a+1}} \neq \text{integer}$$

So the idea is to first asymptotically calculate $c!$ and then keep dividing by $c$ until one does not get an integer anymore.

Edit

I just realized a better algorithm would be to first divide $c^{\lfloor \sqrt {c} /2\rfloor }$. If it is not an integer then divide by $c^{\lfloor \sqrt {c} /4\rfloor }$. However is it is an integer then divide by: $c^{3\lfloor \sqrt {c} /4 \rfloor }$ . And so on ...

Question

I was wondering if this already existed in the literature? And what is the running time of this algorithm? Can this algorithm be improved upon?

Answer 1

The best factoring algorithm currently available is the General Number Field Sieve. Numbers of more than 200 decimal digits have been factored using this method.

The factorial of such a number would have more than $10^{200}$ digits $-$ where on earth are you going to put them all? And that's even before you start your trial divisions. I'm afraid your method is completely impractical as a factoring algorithm.

Answer 2

Not sure about correctness, but since $c$ has a representation in $\log c$ bits, you have to make $\Theta(c)$ multiplications to do this naively, so this algorithm is expoential, not polynomial

UPDATE

The edit improves on the number of divisions, but not on the number of multiplications. Unless you find a way to compute $c!$ in an order less than $c$ (perhaps by considering the Gamma function, but not sure), the running time will stay exponential.

Answer 3

The basic algorithm takes about $p$ divisions to find the smallest prime factor $p$ of your number, which in the worst case is around $\sqrt{c}$. Each step requires dividing a huge number* by $c$, which takes about $c\log^2 c$ time, for a total runtime of about $cp\log^2c$. This is much worse than trial division!

Here is a straightforward implementation of your algorithm:

fac(c)=my(N=c!); for(a=0,sqrtint(c), N/=c; if(denominator(N)>1, return(a))); c

This uses a fast algorithm to compute the factorial and then simple division to find the factor. Finding a factor of a random number I generated, 924233, with this algorithm took about 1.5 seconds, an eternity for such a small number. I then tried to do the same with the larger number 107231893 which nearly crashed my machine -- the 814,536,627-digit factorial caused my memory to thrash.

Your variant algorithm won't help with the memory issue, but there is a fix. If you factor (!) $c$ first, then you can work with the exponents on $a$ and $b$ only. So instead of storing that huge number we can work with the much more manageable $$ a^{10980}b^{9767} $$ which you can do binary splitting as you propose. But you can improve on this by merely choosing the prime with the largest exponent which will of course be the smallest prime factor. So really all your algorithm needs to become efficient is to do a little bit of preprocessing beforehand with an efficient factorization algorithm.

* This can be done with Jebelean's bidirectional algorithm, which will save a factor of about 4 from the runtime.