Can $\sigma(n)$ be computed in polynomial time?

48 Views Asked by At

If $\sigma(n)$ is the sum of the divisors of $n$, can $\sigma(n)$ be computed in the polynomial time no matter how large $n$ is?

If so, then by computing $\sigma(n)$ and $\phi(n)$, Euler totient function, using the discrete Fourier transform of the gcd evaluated at 1, one can easily get $p$ and $q$ such that $n=pq$ from: enter image description here from the link https://en.wikipedia.org/wiki/Divisor_function

And this should solve RSA encryption problem.