Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I sat a lecture where a proposition is proven that states the following:

If computation of $(k!)_{k\in\mathbb{N}}$ is "easy", then integer numbers can be factored in non uniform polynomial time.

The proof picks a number $n$ and asserts right from the start that $n$ is square-free. My question is simply: Why does it suffice to consider square-free numbers?

share|improve this question
    
How does the proof continue? –  Berci Feb 27 '13 at 16:59
    
@Berci: Let $d=\gcd(k!,n)$; due to the assumption that $n$ is square free, one can show that we have found a proper divisor of $n$. One then computes $m=k!\bmod n$ and obtains $d=\gcd(m,n)$. –  user38451 Feb 27 '13 at 17:01
    
Aha, and $k$ goes from $1$ to $n-1$, or picked randomly, or what? –  Berci Feb 27 '13 at 17:15
2  
@Berci: Oh I am sorry, this is essential, you set $k:=\lfloor\sqrt n\rfloor$. If $n=p_1\cdots p_t$ with prime factors $p_1\le\cdots\le p_t$, you can now conclude $p_1\le k<p_1$. –  user38451 Feb 27 '13 at 17:53
add comment

1 Answer

Possibly, it might be because of the Moebius function:

$\mu(n)=0 \iff n\ $ is not square-free,

and $\mu$ can be calculated using the primitive $n$th roots of unity: see e.g. here.

share|improve this answer
    
Hm. That computation seems exponential in $\log(n)$, so that can't be it. Also, simply knowing that a number isn't square free doesn't give you a factorization. It would only help with determining primality, but we already have a polynomial algorithm for that. –  user38451 Mar 1 '13 at 8:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.