I am trying to find the complexity of a factorization for big numbers. Which is the best algorithm and which is the complexity of finding a number's prime factors? Assume that the length of the number is n.
The best know algoritm for factoring integer larger than 100 digits is General number field sieve. It's complexity is explained on the page that the link links to.
Wikipedia has a nice article about other algoritms: http://en.wikipedia.org/wiki/Integer_factorization