Comment Re:graph isomorphism is not hard! (Score 1) 45
No it is not. While integer factorization is not known to be NPcomplete, there is no known expected polynomial time algorithm to solve it (polynomial in the number of digits (not in the magnitude of the integer).
To my knowledge the best result is exp[(1+o(1))sqrt(log n)(sqrt(log log n)], where n in the number to be factorized and consequently log n is the number of digits.