How to factorize a number into prime numbers I have to compute the Legendre symbol $4307 \choose 7549$, so I have to factorize $4307$ into prime numbers. Is there any mathematical shortcut to do it?
 A: Of course, use the Jacobi symbol instead.  The Jacobi agrees with the Legendre symbol for prime values, and also satisfies similar reciprocity laws.  Specifically, for odd $m$ and $n$, we have $$\left(\frac{m}{n}\right)=(-1)^{\frac{(m-1)(n-1)}{4}}\left(\frac{n}{m}\right)$$and $$\left(\frac{2}{n}\right)=(-1)^{\frac{n^2-1}{8}}$$
Calculating $\left(\frac{4307}{7549}\right)$ becomes similar to the Euclidean Algorithm.  
$\left(\frac{4307}{7549}\right)=(-1)^{\frac{(4306)(7548)}{4}}\left(\frac{7549}{4307}\right)=\left(\frac{3242}{4307}\right)=\left(\frac{2}{4307}\right)\left(\frac{1621}{4307}\right)=(-1)^{\frac{4307^2-1}{8}}(-1)^{\frac{(1620)(4306)}{4}}\left(\frac{4307}{1621}\right)=$
$-\left(\frac{1065}{1621}\right)=-(-1)^{\frac{(1064)(1620)}{4}}\left(\frac{1621}{1065}\right)=-\left(\frac{556}{1065}\right)=-\left(\frac{4}{1065}\right)\left(\frac{139}{1065}\right)=-(-1)^{\frac{(138)(1064)}{4}}\left(\frac{1065}{139}\right)=-\left(\frac{92}{139}\right)=-\left(\frac{4}{139}\right)\left(\frac{23}{139}\right)=-(-1)^{\frac{(22)(138)}{4}}\left(\frac{139}{23}\right)=-(-1)\left(\frac{1}{23}\right)=1$
The advantage here is that $m$ and $n$ do not need to be prime, and it will still agree with the symbol when the original values were prime.  Also, the Euclidean algorithm is known to run very fast: $O(\log n)$
