I am trying to find factorization complexity for large numbers. What is the best algorithm and the difficulty of finding the number of simple factors? Suppose the length of the number is n.
The best algorithm for factoring integers in excess of 100 digits, General field sieve . This difficulty is explained on the page that the link links to.
Wikipedia has a good article on other algorithms: http://en.wikipedia.org/wiki/Integer_factorization
sqrt (n) log (n). n <= 19 ^ 7, , log (n). → http://codeforces.com/blog/entry/7262