What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?
Large numbers are factored with the General Number Field Sieve, which is, as of now, the fastest non-quantum algorithm. 
You can find the heuristic runtime in the linked Wikipedia-article.
Also in use is the Elliptic Curve Factorization, which needs longer runtime in the worst-case, but has the advantage that the runtime depends on the second-largest factor. Thus every now and then it's faster.
The largest "RSA"-number yet factored is a 768 bit number (RSA Factoring Challenge).