1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @Salem would it be better if I edited my question again or should I answer my own question? $\endgroup$ – drewdles Aug 2 '16 at 11:48
  • $\begingroup$ The running time of calculating $c!$ alone would be $O(c\cdot2^{n})$, where $n=\log_2c$ (i.e., the length of the input), which means that your algorithm is (at least) exponential in the length of the input. $\endgroup$ – barak manos Aug 2 '16 at 12:44
  • $\begingroup$ I am confused about the edit. Please clarify what you do before checking the divisibility! $\endgroup$ – Peter Aug 2 '16 at 12:58
  • $\begingroup$ If $m!$ modulo $n$ for large $m$ and $n$ could be efficiently calculated, we would have an efficient algorithm for factoring. But no efficient algorithm to do that is known. $\endgroup$ – Peter Aug 2 '16 at 12:59
  • 2
    $\begingroup$ Maybe, I got your idea. Do you mean the binary search method to squeeze the factor ? Still you have to calculate $m!$ modulo $n$ which large $m$. ($m$ will have a maginitude comparable to $\sqrt{n}$). If $n$ has $100$ digits, $m$ can have about $50$ digits, and $m!$ gets huge. $\endgroup$ – Peter Aug 2 '16 at 13:21
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I added an improved version of the algorithm. I would love to know your thoughts on that... Thanks $\endgroup$ – drewdles Aug 2 '16 at 11:45
  • $\begingroup$ @AnantSaxena see update $\endgroup$ – gt6989b Aug 2 '16 at 15:35
  • $\begingroup$ But doesnt Stirling's formula enable me to calculate $c!$ (if sufficient number of terms are taken?) $\endgroup$ – drewdles Aug 2 '16 at 15:41
  • $\begingroup$ @AnantSaxena just an approximation, not exact, and also very complex to compute $\endgroup$ – gt6989b Aug 2 '16 at 15:43
  • $\begingroup$ Yes, but if one approximates to first decimal place: en.wikipedia.org/wiki/… (actually even that is not required as we can estimate the number of $0$'s it ends with) and then uses the floor function. Then I believe $c!$ can be easily calculated $\endgroup$ – drewdles Aug 2 '16 at 15:54

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.