Is $\gcd(n, \lfloor\sqrt{n}\rfloor!)$ a solution to the factoring problem?

Question

The factoring problem:

Factor $n=pq$ given only $n$ where $p$ and $q$ are primes and $0<p<\sqrt{n}<q<n$

I found that $$\gcd(n, \lfloor\sqrt{n}\rfloor!) = p$$

Would this be considered a solution to the factoring problem? I have only tested it for small semiprimes e.g. $21=3*7$

$$\gcd(21, \lfloor\sqrt{21}\rfloor!)=\gcd(21,24) =3$$ but see no reason why it wouldn't work for all semiprimes. I know that calculating $\lfloor\sqrt{n}\rfloor!$ for large RSA numbers would be a computational nightmare, but just want to know if this "solution" works every time the above conditions are met.

Thanks and Happy $\pi$ Day 2014!

Answer 1

The divisors of $n$ are $1$, $p$, $q$, and $n$.

Because $p\leq \lfloor\sqrt{n}\rfloor<q$, we know that $p|(\lfloor\sqrt{n}\rfloor)!$ but not $q|(\lfloor\sqrt{n}\rfloor)!$ (because $q$ is a prime and $(\lfloor\sqrt{n}\rfloor)!$ is a product of numbers smaller than $q$).

Therefore, $p$ is but $q$ and $n$ aren't divisors of $(\lfloor\sqrt{n}\rfloor)!$.

Thus, the greatest common divisor of those numbers is $p$.

Answer 2

It works, but consider that producing $\lfloor \sqrt n \rfloor !$ is no quicker than trial division of $n$ by all numbers up to $\lfloor \sqrt n \rfloor .$